{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:28:55Z","timestamp":1725488935589},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540414568"},{"type":"electronic","value":"9783540445036"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44503-x_16","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T04:25:32Z","timestamp":1186892732000},"page":"234-247","source":"Crossref","is-referenced-by-count":1,"title":["The Dynamic Complexity of Transitive Closure Is in DynTC\u00b0"],"prefix":"10.1007","author":[{"given":"William","family":"Hesse","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,10,12]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Barrington, Immerman, and Straubing. On uniformity within NC 1. In SCT: Annual Conference on Structure in Complexity Theory, 1988.","DOI":"10.1109\/SCT.1988.5262"},{"issue":"4","key":"16_CR2","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1137\/0215070","volume":"15","author":"P. W. Beame","year":"1986","unstructured":"Paul W. Beame, Stephen A. Cook, and H. James Hoover. Log depth circuits for division and related problems. SIAM Journal on Computing, 15(4):994\u20131003, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"G. Dong, L. Libkin, and L. Wong. On impossibility of decremental recomputation of recursive queries in relational calculus and SQL. In International Workshop on Database Programming Languages, 1995.","DOI":"10.14236\/ewic\/DBPL1995.10"},{"issue":"1","key":"16_CR4","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1006\/inco.1995.1102","volume":"120","author":"G. Dong","year":"1995","unstructured":"Guozhu Dong and Jianwen Su. Incremental and decremental evaluation of transitive closure by first-order queries. Information and Computation, 120(1):101\u2013106, July 1995.","journal-title":"Information and Computation"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge and biconnectivity. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC-98), pages 79\u201389, New York, May 23-26 1998. ACM Press.","DOI":"10.1145\/276698.276715"},{"key":"16_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N. Immerman","year":"1999","unstructured":"Neil Immerman. Descriptive Complexity. Springer-Verlag, New York, 1999."},{"issue":"1","key":"16_CR7","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1006\/inco.1995.1007","volume":"116","author":"N. Immerman","year":"1995","unstructured":"Neil Immerman and Susan Landau. The complexity of iterated multiplication. Information and Computation, 116(1):103\u2013116, January 1995.","journal-title":"Information and Computation"},{"key":"16_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1007\/3-540-64823-2_13","volume-title":"Incremental recomputation of recursive queries with nested sets and aggregate functions","author":"L. Libkin","year":"1998","unstructured":"Leonid Libkin and Limsoon Wong. Incremental recomputation of recursive queries with nested sets and aggregate functions. In Proc. of Database Programming Languages (DBPL\u201997), pages 222\u2013238, Estes Park, CO, 1998. Springer-Verlag, Lecture Notes in Computer Science 1369."},{"issue":"2","key":"16_CR9","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1006\/jcss.1997.1520","volume":"55","author":"S. Patnaik","year":"1997","unstructured":"Sushant Patnaik and Neil Immerman. Dyn-FO: A parallel, dynamic complexity class. Journal of Computer and System Sciences, 55(2):199\u2013209, October 1997.","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"16_CR10","doi-asserted-by":"publisher","first-page":"896","DOI":"10.1137\/0221053","volume":"21","author":"J. H. Reif","year":"1992","unstructured":"John H. Reif and Stephen R. Tate. On threshold circuits and polynomial computation. SIAM Journal on Computing, 21(5):896\u2013908, October 1992.","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Database Theory \u2014 ICDT 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44503-X_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,25]],"date-time":"2020-04-25T20:17:52Z","timestamp":1587845872000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44503-X_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540414568","9783540445036"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-44503-x_16","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}