The Dynamic Complexity of Transitive Closure Is In DynTC⁰.

@inproceedings{DBLP:conf/icdt/Hesse01,
  author    = {William Hesse},
  editor    = {Jan Van den Bussche and
               Victor Vianu},
  title     = {The Dynamic Complexity of Transitive Closure Is In DynTC$^{\mbox{0}}$},
  booktitle = {Database Theory - ICDT 2001, 8th International Conference, London,
               UK, January 4-6, 2001, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1973},
  year      = {2001},
  isbn      = {3-540-41456-8},
  pages     = {234-247},
  ee        = {db/conf/icdt/Hesse01.html, http://link.springer.de/link/service/series/0558/bibs/1973/19730234.htm},
  crossref  = {DBLP:conf/icdt/2001},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Online Edition: Springer LINK

References

[1]

David A. Mix Barrington, Neil Immerman, Howard Straubing: On Uniformity within NC¹. J. Comput. Syst. Sci. 41(3): 274-306(1990) BibTeX

[2]

Paul Beame, Stephen A. Cook, H. James Hoover: Log Depth Circuits for Division and Related Problems. SIAM J. Comput. 15(4): 994-1003(1986) BibTeX

[3]

Guozhu Dong, Leonid Libkin, Limsoon Wong: On Impossibility of Decremental Recomputation of Recursive Queries in Relational Calculus and SQL. DBPL 1995: 7 BibTeX

[4]

Guozhu Dong, Jianwen Su: Incremental and Decremental Evaluation of Transitive Closure by First-Order Queries. Inf. Comput. 120(1): 101-106(1995) BibTeX

[5]

Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup: Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity. STOC 1998: 79-89 BibTeX

[6]

...

[7]

Neil Immerman, Susan Landau: The Complexity of Iterated Multiplication. Inf. Comput. 116(1): 103-116(1995) BibTeX

[8]

Leonid Libkin, Limsoon Wong: Incremental Recomputation of Recursive Queries with Nested Sets and Aggregate Functions. DBPL 1997: 222-238 BibTeX

[9]

Sushant Patnaik, Neil Immerman: Dyn-FO: A Parallel, Dynamic Complexity Class. J. Comput. Syst. Sci. 55(2): 199-209(1997) BibTeX

[10]

John H. Reif, Stephen R. Tate: On Threshold Circuits and Polynomial Computation. SIAM J. Comput. 21(5): 896-908(1992) BibTeX