{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:16:49Z","timestamp":1740097009880,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_30","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T12:10:36Z","timestamp":1402488636000},"page":"356-367","source":"Crossref","is-referenced-by-count":3,"title":["Dynamic Complexity of Directed Reachability and Other Problems"],"prefix":"10.1007","author":[{"given":"Samir","family":"Datta","sequence":"first","affiliation":[]},{"given":"William","family":"Hesse","sequence":"additional","affiliation":[]},{"given":"Raghav","family":"Kulkarni","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"30_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.\u00a059(2), 164\u2013181 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"Bourke, C., Tewari, R., Vinodchandran, N.V.: Directed planar reachability is in unambiguous log-space. TOCT\u00a01(1) (2009)","DOI":"10.1145\/1490270.1490274"},{"issue":"3","key":"30_CR3","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1007\/s00224-009-9204-8","volume":"47","author":"S. Datta","year":"2010","unstructured":"Datta, S., Kulkarni, R., Roy, S.: Deterministically isolating a perfect matching in bipartite planar graphs. Theory Comput. Syst.\u00a047(3), 737\u2013757 (2010)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"30_CR4","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"},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"Gr\u00e4del, E., Siebertz, S.: Dynamic definability. In: ICDT, pp. 236\u2013248 (2012)","DOI":"10.1145\/2274576.2274601"},{"key":"30_CR6","unstructured":"Hesse, W.: Dynamic computational complexity. Ph.D. thesis, U. Mass. (2003)"},{"issue":"3","key":"30_CR7","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 DynTC0. Theor. Comput. Sci.\u00a0296(3), 473\u2013485 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"30_CR8","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1016\/S0022-0000(02)00025-9","volume":"65","author":"W. Hesse","year":"2002","unstructured":"Hesse, W., Allender, E., Barrington, D.A.M.: Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci.\u00a065(4), 695\u2013716 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"30_CR9","unstructured":"Mahajan, M., Vinay, V.: Determinant: Combinatorics, algorithms, and complexity. Chicago J. Theor. Comput. Sci. 1997 (1997)"},{"key":"30_CR10","unstructured":"Mehta, J.C.: Dynamic Complexity of Planar 3-connected Graph Isomorphism. In: CSR (accepted, 2014)"},{"issue":"5","key":"30_CR11","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1137\/S0097539789162997","volume":"24","author":"G.L. Miller","year":"1995","unstructured":"Miller, G.L., Naor, J.: Flow in planar graphs with multiple sources and sinks. SIAM J. Comput.\u00a024(5), 1002\u20131017 (1995)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"30_CR12","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF02579205","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K.: A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica\u00a07(1), 101\u2013104 (1987)","journal-title":"Combinatorica"},{"issue":"1","key":"30_CR13","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\u00a07(1), 105\u2013113 (1987)","journal-title":"Combinatorica"},{"issue":"2","key":"30_CR14","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"},{"issue":"4","key":"30_CR15","doi-asserted-by":"publisher","first-page":"1118","DOI":"10.1137\/S0097539798339041","volume":"29","author":"K. Reinhardt","year":"2000","unstructured":"Reinhardt, K., Allender, E.: Making nondeterminism unambiguous. SIAM J. Comput.\u00a029(4), 1118\u20131131 (2000)","journal-title":"SIAM J. Comput."},{"key":"30_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-642-39992-3_6","volume-title":"Logic, Language, Information, and Computation","author":"T. Schwentick","year":"2013","unstructured":"Schwentick, T.: Perspectives of Dynamic Complexity. In: Libkin, L., Kohlenbach, U., de Queiroz, R. (eds.) WoLLIC 2013. LNCS, vol.\u00a08071, pp. 33\u201333. Springer, Heidelberg (2013), \n                    \n                      http:\/\/dx.doi.org\/10.1007\/978-3-642-39992-3-6"},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"Vollmer, H.: Introduction to circuit complexity - a uniform approach. Texts in theoretical computer science. Springer (1999)","DOI":"10.1007\/978-3-662-03927-4"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:19:38Z","timestamp":1558909178000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}