{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:08:59Z","timestamp":1725548939672},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540249986"},{"type":"electronic","value":"9783540318569"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31856-9_21","type":"book-chapter","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T13:06:19Z","timestamp":1267535179000},"page":"256-268","source":"Crossref","is-referenced-by-count":4,"title":["Dynamic Complexity Theory Revisited"],"prefix":"10.1007","author":[{"given":"Volker","family":"Weber","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"21_CR1","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/S0890-5401(03)00017-8","volume":"181","author":"G. Dong","year":"2003","unstructured":"Dong, G., Libkin, L., Wong, L.: Incremental recomputation in local languages. Information and Computation\u00a0181(2), 88\u201398 (2003)","journal-title":"Information and Computation"},{"key":"21_CR2","first-page":"295","volume-title":"Proc. of DBPL-4, Workshops in Computing","author":"G. Dong","year":"1993","unstructured":"Dong, G., Su, J.: First-order incremental evaluation of datalog queries. In: Proc. of DBPL-4, Workshops in Computing, pp. 295\u2013308. Springer, Heidelberg (1993)"},{"issue":"1","key":"21_CR3","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1006\/inco.1995.1102","volume":"120","author":"G. Dong","year":"1995","unstructured":"Dong, G., Su, J.: Incremental and decremental evaluation of transitive closure by first-order queries. Information and Computation\u00a0120(1), 101\u2013106 (1995)","journal-title":"Information and Computation"},{"issue":"1-2","key":"21_CR4","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1023\/A:1018951521198","volume":"19","author":"G. Dong","year":"1997","unstructured":"Dong, G., Su, J.: Deterministic FOIES are strictly weaker. Annals of Mathematics and Artificial Intelligence\u00a019(1-2), 127\u2013146 (1997)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"3","key":"21_CR5","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1006\/jcss.1998.1565","volume":"557","author":"G. Dong","year":"1998","unstructured":"Dong, G., Su, J.: Arity bounds in first-order incremental evaluation and definition of polynomial time database queries. Journal of Computer and System Sciences\u00a0557(3), 289\u2013308 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"21_CR6","first-page":"235","volume-title":"Proc. of the 17th PODS","author":"K. Etessami","year":"1998","unstructured":"Etessami, K.: Dynamic tree isomorphism via first-order updates to a relational database. In: Proc. of the 17th PODS, pp. 235\u2013243. ACM Press, New York (1998)"},{"key":"21_CR7","series-title":"Lecture Notes in Computer Science","volume-title":"Online Algorithms","year":"1998","unstructured":"Fiat, A., Woeginger, G.J. (eds.): Online Algorithms. LNCS, vol.\u00a01442. Springer, Heidelberg (1998)"},{"issue":"1-2","key":"21_CR8","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1016\/S0304-3975(01)00108-6","volume":"270","author":"G. Gottlob","year":"2002","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Computing LOGCFL certificates. Theoretical Computer Science\u00a0270(1-2), 761\u2013777 (2002)","journal-title":"Theoretical Computer Science"},{"key":"21_CR9","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to Parallel Computation: P-Completeness Theory","author":"R. Greenlaw","year":"1995","unstructured":"Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, Oxford (1995)"},{"issue":"3","key":"21_CR10","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1016\/S0304-3975(02)00740-5","volume":"296","author":"W. Hesse","year":"2003","unstructured":"Hesse, W.: The dynamic complexity of transitive closure is in DynTC 0. Theoretical Computer Science\u00a0296(3), 473\u2013485 (2003)","journal-title":"Theoretical Computer Science"},{"key":"21_CR11","first-page":"313","volume-title":"Proc. of the 17th LICS","author":"W. Hesse","year":"2002","unstructured":"Hesse, W., Immerman, N.: Complete problems for dynamic complexity classes. In: Proc. of the 17th LICS, p. 313. IEEE Computer Society, Los Alamitos (2002)"},{"key":"21_CR12","first-page":"79","volume-title":"Proc. of the 30th STOC","author":"J. Holm","year":"1998","unstructured":"Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. In: Proc. of the 30th STOC, pp. 79\u201389. ACM, New York (1998)"},{"issue":"4","key":"21_CR13","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"Immerman, N.: Languages that capture complexity classes. SIAM Journal on Computing\u00a016(4), 760\u2013778 (1987)","journal-title":"SIAM Journal on Computing"},{"key":"21_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1007\/3-540-64823-2_13","volume-title":"Database Programming Languages","author":"L. Libkin","year":"1998","unstructured":"Libkin, L., Wong, L.: Incremental recomputation of recursive queries with nested sets and aggregate functions. In: Cluet, S., Hull, R. (eds.) DBPL 1997. LNCS, vol.\u00a01369, pp. 222\u2013238. Springer, Heidelberg (1998)"},{"key":"21_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/3-540-44543-9_2","volume-title":"Research Issues in Structured and Semistructured Database Programming","author":"L. Libkin","year":"2000","unstructured":"Libkin, L., Wong, L.: On the power of incremental evaluation in SQL-like languages. In: Connor, R.C.H., Mendelzon, A.O. (eds.) DBPL 1999. LNCS, vol.\u00a01949, pp. 17\u201330. Springer, Heidelberg (2000)"},{"issue":"1","key":"21_CR16","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0304-3975(94)90159-7","volume":"130","author":"P.B. Miltersen","year":"1994","unstructured":"Miltersen, P.B., Subramanian, S., Vitter, J.S., Tamassia, R.: Complexity models for incremental computation. Theoretical Computer Science\u00a0130(1), 203\u2013236 (1994)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"21_CR17","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1006\/jcss.1997.1520","volume":"55","author":"S. Patnaik","year":"1997","unstructured":"Patnaik, S., Immerman, N.: Dyn-FO: A parallel, dynamic complexity class. Journal of Computer and System Sciences\u00a055(2), 199\u2013209 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"21_CR18","first-page":"184","volume-title":"Proc. of the 36th STOC","author":"L. Roditty","year":"2004","unstructured":"Roditty, L., Zwick, U.: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In: Proc. of the 36th STOC, pp. 184\u2013191. ACM, New York (2004)"}],"container-title":["Lecture Notes in Computer Science","STACS 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31856-9_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,24]],"date-time":"2021-10-24T03:39:24Z","timestamp":1635046764000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31856-9_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540249986","9783540318569"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31856-9_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}