{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T19:40:01Z","timestamp":1748461201723,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476659"},{"type":"electronic","value":"9783662476666"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47666-6_13","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T07:46:47Z","timestamp":1434700007000},"page":"159-170","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Reachability is in DynFO"],"prefix":"10.1007","author":[{"given":"Samir","family":"Datta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raghav","family":"Kulkarni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anish","family":"Mukherjee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Zeume","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"issue":"2","key":"13_CR1","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1006\/jcss.1999.1646","volume":"59","author":"E Allender","year":"1999","unstructured":"Allender, E., Reinhardt, K., Zhou, S.: Isolation, matching, and counting uniform and nonuniform upper bounds. J. Comput. Syst. Sci. 59(2), 164\u2013181 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR2","unstructured":"Artin, M.: Algebra. Featured Titles for Abstract Algebra. Pearson (2010)"},{"key":"13_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1007\/978-3-662-43948-7_30","volume-title":"Automata, Languages, and Programming","author":"S Datta","year":"2014","unstructured":"Datta, S., Hesse, W., Kulkarni, R.: Dynamic Complexity of Directed Reachability and Other Problems. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 356\u2013367. Springer, Heidelberg (2014)"},{"issue":"1","key":"13_CR4","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1006\/inco.1995.1102","volume":"120","author":"G Dong","year":"1995","unstructured":"Dong, G., Jianwen, S.: Incremental and decremental evaluation of transitive closure by first-order queries. Information and Computation 120(1), 101\u2013106 (1995)","journal-title":"Information and Computation"},{"issue":"3","key":"13_CR5","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1006\/jcss.1998.1565","volume":"57","author":"G Dong","year":"1998","unstructured":"Dong, G., Jianwen, S.: Arity bounds in first-order incremental evaluation and definition of polynomial time database queries. J. Comput. Syst. Sci. 57(3), 289\u2013308 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Etessami, K.: Dynamic tree isomorphism via first-order updates. In: PODS, pp. 235\u2013243 (1998)","DOI":"10.1145\/275487.275514"},{"issue":"41","key":"13_CR7","doi-asserted-by":"publisher","first-page":"4085","DOI":"10.1016\/j.tcs.2009.06.012","volume":"410","author":"Gudmund Skovbjerg Frandsen and Peter Frands Frandsen","year":"2009","unstructured":"Gudmund Skovbjerg Frandsen and Peter Frands Frandsen: Dynamic matrix rank. Theor. Comput. Sci. 410(41), 4085\u20134093 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del, E., Siebertz, S.: Dynamic definability. In: ICDT, pp. 236\u2013248 (2012)","DOI":"10.1145\/2274576.2274601"},{"issue":"3","key":"13_CR9","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$$^{\\text{0}}$$. Theor. Comput. Sci. 296(3), 473\u2013485 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Hesse, W., Immerman, N.: Complete problems for dynamic complexity classes. In: LICS, p. 313 (2002)","DOI":"10.1109\/LICS.2002.1029839"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Hoang, T.M.: On the matching problem for special graph classes. In: IEEE Conference on Computational Complexity, pp. 139\u2013150 (2010)","DOI":"10.1109\/CCC.2010.21"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Horn, R.A., Johnson, C.R.: Matrix analysis. Cambridge University Press (2012)","DOI":"10.1017\/CBO9781139020411"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Immerman, N.: Descriptive complexity. Graduate texts in computer science. Springer (1999)","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"13_CR14","unstructured":"Laubner, B.: The structure of graphs and new logics for the characterization of Polynomial Time. PhD thesis, Humboldt University of Berlin (2011)"},{"issue":"1","key":"13_CR15","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica 7(1), 105\u2013113 (1987)","journal-title":"Combinatorica"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Patnaik, S., Immerman, N.: Dyn-FO: A parallel, dynamic complexityclass. Journal of Computer and System Sciences 55(2), 199\u2013209 (1997)","DOI":"10.1006\/jcss.1997.1520"},{"issue":"2","key":"13_CR17","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1006\/jagm.1995.0807","volume":"22","author":"JH Reif","year":"1997","unstructured":"Reif, J.H., Tate, S.R.: On dynamic algorithms for algebraic problems. J. Algorithms 22(2), 347\u2013371 (1997)","journal-title":"J. Algorithms"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Sankowski, P.: Dynamic transitive closure via dynamic matrix inverse (extended abstract). In: FOCS, pp. 509\u2013517 (2004)","DOI":"10.1109\/FOCS.2004.25"},{"key":"13_CR19","unstructured":"Sankowski, P.: Faster dynamic matchings and vertex connectivity. In: SODA, pp. 118\u2013126 (2007)"},{"key":"13_CR20","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.ic.2014.09.011","volume":"240","author":"T Zeume","year":"2015","unstructured":"Zeume, T., Schwentick, T.: On the quantifier-free dynamic complexity of reachability. Inf. Comput. 240, 108\u2013129 (2015)","journal-title":"Inf. Comput."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47666-6_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T19:03:25Z","timestamp":1748459005000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47666-6_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476659","9783662476666"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47666-6_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}