The Dynamic Complexity of Transitive Closure Is In DynTC0.

William Hesse: The Dynamic Complexity of Transitive Closure Is In DynTC0. ICDT 2001: 234-247
  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,},
  crossref  = {DBLP:conf/icdt/2001},
  bibsource = {DBLP,}

Online Edition: Springer LINK

Citation Page BibTeX


David A. Mix Barrington, Neil Immerman, Howard Straubing: On Uniformity within NC¹. J. Comput. Syst. Sci. 41(3): 274-306(1990) BibTeX
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
Guozhu Dong, Leonid Libkin, Limsoon Wong: On Impossibility of Decremental Recomputation of Recursive Queries in Relational Calculus and SQL. DBPL 1995: 7 BibTeX
Guozhu Dong, Jianwen Su: Incremental and Decremental Evaluation of Transitive Closure by First-Order Queries. Inf. Comput. 120(1): 101-106(1995) BibTeX
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
Neil Immerman, Susan Landau: The Complexity of Iterated Multiplication. Inf. Comput. 116(1): 103-116(1995) BibTeX
Leonid Libkin, Limsoon Wong: Incremental Recomputation of Recursive Queries with Nested Sets and Aggregate Functions. DBPL 1997: 222-238 BibTeX
Sushant Patnaik, Neil Immerman: Dyn-FO: A Parallel, Dynamic Complexity Class. J. Comput. Syst. Sci. 55(2): 199-209(1997) BibTeX
John H. Reif, Stephen R. Tate: On Threshold Circuits and Polynomial Computation. SIAM J. Comput. 21(5): 896-908(1992) BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
Lecture Notes in Computer Science: Copyright © by Springer
Digitization of EDBT/ICDT/MFDBS proceedings was supported by the EDBT Endowment.
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:19:17 2009