{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:42:46Z","timestamp":1725745366467},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403125"},{"type":"electronic","value":"9783642403132"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40313-2_73","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T14:36:43Z","timestamp":1376663803000},"page":"837-848","source":"Crossref","is-referenced-by-count":2,"title":["On the Quantifier-Free Dynamic Complexity of Reachability"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Zeume","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"73_CR1","unstructured":"Patnaik, S., Immerman, N.: Dyn-FO: A parallel, dynamic complexity class. In: PODS, pp. 210\u2013221. ACM Press (1994)"},{"key":"73_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/3-540-44503-X_16","volume-title":"Database Theory - ICDT 2001","author":"W. Hesse","year":"2000","unstructured":"Hesse, W.: The dynamic complexity of transitive closure is in DynTC0. In: Van den Bussche, J., Vianu, V. (eds.) ICDT 2001. LNCS, vol.\u00a01973, pp. 234\u2013247. Springer, Heidelberg (2000)"},{"issue":"3","key":"73_CR3","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1006\/jcss.1998.1565","volume":"57","author":"G. Dong","year":"1998","unstructured":"Dong, G., Su, J.: Arity bounds in first-order incremental evaluation and definition of polynomial time database queries. J. Comput. Syst. Sci.\u00a057(3), 289\u2013308 (1998)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"73_CR4","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. Inf. Comput.\u00a0181(2), 88\u201398 (2003)","journal-title":"Inf. Comput."},{"key":"73_CR5","unstructured":"Hesse, W.: Dynamic Computational Complexity. PhD thesis, University of Massachusetts Amherst (2003)"},{"key":"73_CR6","unstructured":"Gelade, W., Marquardt, M., Schwentick, T.: The dynamic complexity of formal languages. In: STACS, pp. 481\u2013492 (2009)"},{"key":"73_CR7","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del, E., Siebertz, S.: Dynamic definability. In: ICDT, 236\u2013248 (2012)","DOI":"10.1145\/2274576.2274601"},{"key":"73_CR8","doi-asserted-by":"crossref","unstructured":"Patrascu, M., Demaine, E.D.: Lower bounds for dynamic connectivity. In: Babai, L. (ed.) STOC, pp. 546\u2013553. ACM (2004)","DOI":"10.1145\/1007352.1007435"},{"key":"73_CR9","unstructured":"Zeume, T., Schwentick, T.: On the quantifier-free dynamic complexity of reachability. CoRR abs\/1306.3056 (2013), \n                  \n                    http:\/\/arxiv.org\/abs\/1306.3056"},{"issue":"4","key":"73_CR10","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s00224-006-1312-0","volume":"40","author":"V. Weber","year":"2007","unstructured":"Weber, V., Schwentick, T.: Dynamic complexity theory revisited. Theory Comput. Syst.\u00a040(4), 355\u2013377 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"73_CR11","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/2287718.2287719","volume":"13","author":"W. Gelade","year":"2012","unstructured":"Gelade, W., Marquardt, M., Schwentick, T.: The dynamic complexity of formal languages. ACM Trans. Comput. Log.\u00a013(3), 19 (2012)","journal-title":"ACM Trans. Comput. Log."},{"key":"73_CR12","doi-asserted-by":"crossref","unstructured":"Etessami, K.: Dynamic tree isomorphism via first-order updates. In: PODS, pp. 235\u2013243. ACM Press (1998)","DOI":"10.1145\/275487.275514"},{"key":"73_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/978-3-642-22012-8_35","volume-title":"Automata, Languages and Programming","author":"S. Schmitz","year":"2011","unstructured":"Schmitz, S., Schnoebelen, P.: Multiply-recursive upper bounds with Higman\u2019s lemma. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol.\u00a06756, pp. 441\u2013452. Springer, Heidelberg (2011)"},{"issue":"4","key":"73_CR14","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1142\/S0129054100000302","volume":"11","author":"G. Dong","year":"2000","unstructured":"Dong, G., Zhang, L.: Separating auxiliary arity hierarchy of first-order incremental evaluation systems using (3k+1)-ary input relations. Int. J. Found. Comput. Sci.\u00a011(4), 573\u2013578 (2000)","journal-title":"Int. J. Found. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2013"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40313-2_73","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T02:10:41Z","timestamp":1558318241000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40313-2_73"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403125","9783642403132"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40313-2_73","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}