{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:40:21Z","timestamp":1742596821681,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540577850"},{"type":"electronic","value":"9783540483328"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57785-8_136","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:18:57Z","timestamp":1330262337000},"page":"123-135","source":"Crossref","is-referenced-by-count":3,"title":["Reachability and the power of local ordering"],"prefix":"10.1007","author":[{"given":"Kousha","family":"Etessami","sequence":"first","affiliation":[]},{"given":"Neil","family":"Immerman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","first-page":"113","DOI":"10.2307\/2274958","volume":"55","author":"M. Ajtai","year":"1990","unstructured":"M. Ajtai and R. Fagin, \u201cReachability is Harder for Directed than for Undirected Graphs,\u201d J. Symb. Logic, 55 (1990), 113\u2013150.","journal-title":"J. Symb. Logic"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovasz, and C. Rackoff, \u201cRandom Walks, Universal Traversal Sequences, and the Complexity of the Maze Problem,\u201d Proceedings of the 20th annual IEEE Found. of Comp. Sci. Symp., pages 218\u2013223, October 1979.","DOI":"10.1109\/SFCS.1979.34"},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"P. Beame, A. Borodin, P. Raghavan, W. Ruzzo, and M. Tompa, \u201cTime-Space Tradeoffs for Undirected Graph Traversal,\u201d Proceedings of the 31st Annual IEEE Found. of Comp. Sci. Symp., pages 429\u2013438, St. Louis, MO, October 1990.","DOI":"10.1109\/FSCS.1990.89563"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"M. Blum and D. Kozen, \u201cOn the Power of the Compass,\u201d Proceedings of the 19th Annual IEEE Found. of Comp. Sci. Symp., pages 132\u2013142, Ann Arbor, MI, October 1978.","DOI":"10.1109\/SFCS.1978.30"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"M. Blum and W.J. Sakoda, \u201cOn the Capability of Finite Automata in 2 and 3 Dimensional Space,\u201d Proceedings of the 18th Annual IEEE Found. of Comp. Sci. Symp., pages 147\u2013161, October 1977.","DOI":"10.1109\/SFCS.1977.20"},{"issue":"4","key":"10_CR6","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J. Cai","year":"1992","unstructured":"J. Cai, M. F\u00fcrer, N. Immerman, \u201cAn Optimal Lower Bound on the Number of Variables for Graph Identification,\u201d Combinatorica 12 (4) (1992) 389\u2013410.","journal-title":"Combinatorica"},{"issue":"3","key":"10_CR7","doi-asserted-by":"crossref","first-page":"636","DOI":"10.1137\/0209048","volume":"9","author":"S. A. Cook","year":"1980","unstructured":"S. A. Cook and C. W. Rackoff, \u201cSpace Lower Bounds for Maze Threadability of Restricted Machines,\u201d SIAM J. Comput., 9(3):636\u2013652, Aug 1980.","journal-title":"SIAM J. Comput."},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"J. Edmonds, \u201cTime-Space Tradeoffs for Undirected ST-Connectivity on a JAG,\u201d Proceeding of the 25th Annual ACM Symp. Theory Of Comput., pages 718\u2013727, May 1993.","DOI":"10.1145\/167088.167272"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"H. Gaifman, \u201cOn Local and Non-Local Properties,\u201d Proc. Herbrand Logic Colloq., Marseille, 1981, pages 105\u2013135.","DOI":"10.1016\/S0049-237X(08)71879-2"},{"key":"10_CR10","unstructured":"E. Gr\u00e4del and G. McColm, \u201cDeterministic vs. Nondeterministic Transitive Closure Logic,\u201d In Proceedings of the 7th IEEE Conference on Logic in Computer Science, 1992."},{"issue":"No.1","key":"10_CR11","first-page":"76","volume":"25","author":"N. Immerman","year":"1982","unstructured":"N. Immerman, \u201cUpper and Lower Bounds for First Order Expressibility,\u201d JCSS 25, No. 1 (1982), 76\u201398.","journal-title":"JCSS"},{"issue":"4","key":"10_CR12","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman, \u201cLanguages that Capture Complexity Classes,\u201d SIAM J. Comput.16:4 (1987), 760\u2013778.","journal-title":"SIAM J. Comput."},{"issue":"5","key":"10_CR13","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman, \u201cNondeterministic Space is Closed Under Complementation,\u201d SIAM J. Comput. 17:5 (1988), 935\u2013938.","journal-title":"SIAM J. Comput."},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"N. Immerman, \u201cDescriptive and Computational Complexity,\u201d in Computational Complexity Theory, ed. J. Hartmanis, Proc. Symp. in Applied Math., 38, American Mathematical Society (1989), 75\u201391.","DOI":"10.1090\/psapm\/038\/1020810"},{"key":"10_CR15","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1137\/0218043","volume":"18","author":"N. Immerman","year":"1989","unstructured":"N. Immerman, \u201cExpressibility and Parallel Complexity,\u201d SIAM J. of Comput 18 (1989), 625\u2013638.","journal-title":"SIAM J. of Comput"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Neil Immerman and Eric S. Lander, \u201cDescribing Graphs: A First-Order Approach to Graph Canonization,\u201d in Complexity Theory Retrospective, Alan Selman, ed., Springer-Verlag (1990), 59\u201381.","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"Steven Lindell, \u201cA Logspace Algorithm for Tree Canonization,\u201d ACM Symp. Theory Of Comput.(1992), 400\u2013404.","DOI":"10.1145\/129712.129750"}],"container-title":["Lecture Notes in Computer Science","STACS 94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57785-8_136.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:12:32Z","timestamp":1742595152000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57785-8_136"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540577850","9783540483328"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-57785-8_136","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}