{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:08:35Z","timestamp":1763467715297},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540304951"},{"type":"electronic","value":"9783540324195"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11590156_19","type":"book-chapter","created":{"date-parts":[[2005,12,5]],"date-time":"2005-12-05T10:43:16Z","timestamp":1133779396000},"page":"238-249","source":"Crossref","is-referenced-by-count":14,"title":["The Directed Planar Reachability Problem"],"prefix":"10.1007","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[]},{"given":"Samir","family":"Datta","sequence":"additional","affiliation":[]},{"given":"Sambuddha","family":"Roy","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.ic.2003.09.002","volume":"189","author":"E. Allender","year":"2004","unstructured":"Allender, E., Mahajan, M.: The complexity of planarity testing. Information and Computation\u00a0189, 117\u2013134 (2004)","journal-title":"Information and Computation"},{"issue":"2","key":"19_CR2","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. Journal of Computer and System Sciences\u00a059(2), 164\u2013181 (1999)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR3","unstructured":"Barrington, D.A.M.: Grid graph reachability problems. Talk presented at Dagstuhl Seminar on Complexity of Boolean Functions, Seminar number 02121 (2002)"},{"issue":"1","key":"19_CR4","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0890-5401(91)90075-D","volume":"91","author":"S.R. Buss","year":"1991","unstructured":"Buss, S.R., Hay, L.: On truth-table reducibility to SAT. Inf. Comput.\u00a091(1), 86\u2013102 (1991)","journal-title":"Inf. Comput."},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"Blum, M., Kozen, D.: On the power of the compass (or, why mazes are easier to search than graphs). In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 132\u2013142 (1978)","DOI":"10.1109\/SFCS.1978.30"},{"key":"19_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BFb0028550","volume-title":"STACS 98","author":"D.A.M. Barrington","year":"1998","unstructured":"Barrington, D.A.M., Lu, C.-J., Miltersen, P.B., Skyum, S.: Searching constant width mazes captures the AC0 hierarchy. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 73\u201383. Springer, Heidelberg (1998)"},{"key":"19_CR7","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/BF01271369","volume":"3","author":"H. Buhrman","year":"1993","unstructured":"Buhrman, H., Spaan, E., Torenvliet, L.: The relative power of logspace and polynomial time reductions. Computational Complexity\u00a03, 231\u2013244 (1993)","journal-title":"Computational Complexity"},{"issue":"3","key":"19_CR8","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jcss.1997.1485","volume":"54","author":"K. Etessami","year":"1997","unstructured":"Etessami, K.: Counting quantifiers, successor relations, and logarithmic space. Journal of Computer and System Sciences\u00a054(3), 400\u2013411 (1997)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR9","volume-title":"Topological Graph Theory","author":"J. Gross","year":"1987","unstructured":"Gross, J., Tucker, T.: Topological Graph Theory, 1st edn. John Wiley and Sons, Chichester (1987)","edition":"1"},{"key":"19_CR10","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complementation. SIAM Journal on Computing\u00a017, 935\u2013938 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/3-540-44693-1_30","volume-title":"STACS 2001","author":"A. Jakoby","year":"2001","unstructured":"Jakoby, A., Liskiewicz, M., Reischuk, R.: Space efficient algorithms for seriesparalle graphs. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 339\u2013352. Springer, Heidelberg (2001) (to appear in J. Algorithms)"},{"key":"19_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/BFb0023471","volume-title":"STACS 97","author":"K.-J. Lange","year":"1997","unstructured":"Lange, K.-J.: An unambiguous class possessing a complete set. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol.\u00a01200, pp. 339\u2013350. Springer, Heidelberg (1997)"},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF01683260","volume":"10","author":"R. Ladner","year":"1976","unstructured":"Ladner, R., Lynch, N.: Relativization of questions about log space reducibility. Mathematical Systems Theory\u00a010, 19\u201332 (1976)","journal-title":"Mathematical Systems Theory"},{"key":"19_CR14","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on surfaces","author":"B. Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on surfaces, 1st edn. John Hopkins University Press, Maryland (2001)","edition":"1"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Mahajan, M., Varadarajan, K.R.: A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs. In: ACM Symposium on Theory of Computing (STOC), pp. 351\u2013357 (2000)","DOI":"10.1145\/335305.335346"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"Nisan, N., Ta-Shma, A.: Symmetric Logspace is closed under complement. Chicago Journal of Theoretical Computer Science (1995)","DOI":"10.4086\/cjtcs.1995.001"},{"key":"19_CR17","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 Journal of Computing\u00a029, 1118\u20131131 (2000)","journal-title":"SIAM Journal of Computing"},{"key":"19_CR18","first-page":"376","volume-title":"Proceedings 37th Symposium on Foundations of Computer Science","author":"O. Reingold","year":"2005","unstructured":"Reingold, O.: Undirected st-connectivity in log-space. In: Proceedings 37th Symposium on Foundations of Computer Science, pp. 376\u2013385. IEEE Computer Society Press, Los Alamitos (2005)"},{"key":"19_CR19","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"Szelepcs\u00e9nyi, R.: The method of forced enumeration for nondeterministic automata. Acta Informatica\u00a026, 279\u2013284 (1988)","journal-title":"Acta Informatica"},{"issue":"2","key":"19_CR20","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/0095-8956(90)90115-G","volume":"48","author":"C. Thomassen","year":"1990","unstructured":"Thomassen, C.: Embeddings of graphs with no short noncontractible cycles. J. Comb. Theory Ser. B\u00a048(2), 155\u2013177 (1990)","journal-title":"J. Comb. Theory Ser. B"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11590156_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T15:09:23Z","timestamp":1683299363000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11590156_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540304951","9783540324195"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11590156_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}