{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:49:11Z","timestamp":1780822151360,"version":"3.54.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,9,25]],"date-time":"2012-09-25T00:00:00Z","timestamp":1348531200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2012,12]]},"DOI":"10.1007\/s00037-012-0047-3","type":"journal-article","created":{"date-parts":[[2012,9,24]],"date-time":"2012-09-24T11:09:16Z","timestamp":1348484956000},"page":"643-670","source":"Crossref","is-referenced-by-count":5,"title":["On the power of unambiguity in log-space"],"prefix":"10.1007","volume":"21","author":[{"given":"A.","family":"Pavan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raghunath","family":"Tewari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,9,25]]},"reference":[{"key":"47_CR1","unstructured":"E. Allender & M. Ogihara (1994). Relationships among PL, #L, and the determinant. In Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual, 267\u2013278."},{"key":"47_CR2","doi-asserted-by":"crossref","unstructured":"Eric Allender (1986). The complexity of sparse sets in P. In Proc. of the conference on Structure in complexity theory, 1\u201311. ISBN 0-387-16486-3.","DOI":"10.1007\/3-540-16486-3_85"},{"issue":"2","key":"47_CR3","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/j.tcs.2006.01.005","volume":"355","author":"Allender Eric","year":"2006","unstructured":"Eric Allender (2006) NL-printable sets and nondeterministic Kolmogorov complexity. Theor. Comput. Sci. 355(2): 127\u2013138","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"47_CR4","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1007\/s00224-009-9172-z","volume":"45","author":"Allender Eric","year":"2009","unstructured":"Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy (2009) Planar and Grid Graph Reachability Problems. Theory Comput. Syst. 45(4): 675\u2013723","journal-title":"Theory Comput. Syst."},{"key":"47_CR5","doi-asserted-by":"crossref","unstructured":"Eric Allender, Robert Beals & Mitsunori Ogihara (1999a). The complexity of matrix rank and feasible systems of linear equations. Comput. Complex. 8, 99\u2013126. ISSN 1016-3328. http:\/\/portal.acm.org\/citation.cfm?id=329550.329552 .","DOI":"10.1007\/s000370050023"},{"key":"47_CR6","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1006\/jcss.1999.1646","volume":"59","author":"Allender Eric","year":"1999","unstructured":"Eric Allender, Klaus Reinhardt & Shiyu Zhou (1999b). Isolation, Matching, and Counting: Uniform and Nonuniform Upper Bounds. Journal of Computer and System Sciences 59, 164\u2013181.","journal-title":"Journal of Computer and System Sciences"},{"key":"47_CR7","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(93)90252-O","volume":"107","author":"\u00c0lvarez Carme","year":"1993","unstructured":"Carme \u00c0lvarez, Birgit Jenner (1993) A Very Hard Log-space Counting Class. Theoretical Computer Science 107: 3\u201330","journal-title":"Theoretical Computer Science"},{"key":"47_CR8","doi-asserted-by":"crossref","unstructured":"Chris Bourke, Raghunath Tewari & N. V. Vinodchandran (2009). Directed Planar Reachability Is in Unambiguous Log-Space. ACM Trans. Comput. Theory 1(1), 1\u201317. ISSN 1942-3454.","DOI":"10.1145\/1490270.1490274"},{"issue":"3","key":"47_CR9","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF01374526","volume":"25","author":"Buntrock Gerhard","year":"1992","unstructured":"Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel (1992) Structure and Importance of Logspace-MOD Class. Mathematical Systems Theory 25(3): 223\u2013237","journal-title":"Mathematical Systems Theory"},{"key":"47_CR10","doi-asserted-by":"crossref","unstructured":"Gerhard Buntrock, Lane A. Hemachandra & Dirk Siefkes (1993). Using Inductive Counting to Simulate Nondeterministic Computation. Information and Computation 102(1), 102\u2013117.","DOI":"10.1006\/inco.1993.1004"},{"key":"47_CR11","doi-asserted-by":"crossref","unstructured":"Gerhard Buntrock, Birgit Jenner, Klaus-J\u00f6rn Lange & Peter Rossmanith (1991). Unambiguity and fewness for logarithmic space. In Proceedings of the 8th International Conference on Fundamentals of Computation Theory (FCT\u201991), Volume 529 Lecture Notes in Computer Science, 168\u2013179. Springer-Verlag.","DOI":"10.1007\/3-540-54458-5_61"},{"key":"47_CR12","unstructured":"Jin-Yi Cai & Lane Hemachandra (1990). On the power of parity polynomial time. Mathematical Systems Theory."},{"key":"47_CR13","doi-asserted-by":"crossref","unstructured":"Michael L. Fredman, J\u00e1nos Koml\u00f3s & Endre Szemer\u00e9di (1984). Storing a Sparse Table with O(1) Worst Case Access Time. J. ACM 31(3), 538\u2013544.","DOI":"10.1145\/828.1884"},{"key":"47_CR14","doi-asserted-by":"crossref","unstructured":"Brady Garvin, Derrick Stolee, Raghunath Tewari & N. V. Vinodchandran (2011). ReachFewL=ReachUL. In 17th Annual International Computing and Combinatorics Conference.","DOI":"10.1007\/978-3-642-22685-4_23"},{"issue":"3","key":"47_CR15","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0022-0000(89)90025-1","volume":"39","author":"v Hemachandra","year":"1989","unstructured":"Hemachandra v (1989) The strong exponential hierarchy collapses. J. of Computer and System Sciences 39(3): 299\u2013322","journal-title":"J. of Computer and System Sciences"},{"key":"47_CR16","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"Krentel Mark","year":"1988","unstructured":"Mark Krentel (1988) The complexity of optimization problems. J. of Computer and System Sciences 36: 490\u2013509","journal-title":"J. of Computer and System Sciences"},{"key":"47_CR17","doi-asserted-by":"crossref","unstructured":"Jan Kyn\u010dl & Tom\u00e1 \u0161 Vysko\u010dil (2010). Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case. ACM Trans. Comput. Theory 1(3), 1\u201311. ISSN 1942-3454.","DOI":"10.1145\/1714450.1714451"},{"key":"47_CR18","doi-asserted-by":"crossref","unstructured":"Nutan Limaye, Meena Mahajan, Prajakta Nimbhorkar (2010). Longest Paths in Planar DAGs in Unambiguous Log-Space. Chicago Journal of Theoretical Computer Science 2010(8).","DOI":"10.4086\/cjtcs.2010.008"},{"key":"47_CR19","doi-asserted-by":"crossref","unstructured":"M. Ogihara (1995). Equivalence of NC k and AC k-1 Closures of NP and Other Classes. Information and Computation 120(1), 55\u201358. ISSN 0890-5401. http:\/\/www.sciencedirect.com\/science\/article\/B6WGK-45NJJWP-43\/2\/4fad4e8bff85772430de575c68b164aa","DOI":"10.1006\/inco.1995.1098"},{"key":"47_CR20","doi-asserted-by":"crossref","unstructured":"Omer Reingold (2008). Undirected connectivity in log-space. J. ACM 55(4), 1\u201324. ISSN 0004-5411.","DOI":"10.1145\/1391289.1391291"},{"key":"47_CR21","doi-asserted-by":"crossref","unstructured":"Klaus Reinhardt & Eric Allender (2000). Making nondeterminism unambiguous. SIAM Journal of Computing 29, 1118\u20131131. An earlier version appeared in FOCS 1997, pp. 244\u2013253.","DOI":"10.1137\/S0097539798339041"},{"key":"47_CR22","doi-asserted-by":"crossref","unstructured":"Uwe Sch\u00f6ning & Klaus Wagner (1988). Collapsing oracle hierarchies, census functions and logarithmically many queries. In STACS 88, Robert Cori & Martin Wirsing, editors, volume 294 of Lecture Notes in Computer Science, 91\u201397. Springer Berlin \/ Heidelberg. doi: 10.1007\/BFb0035835 .","DOI":"10.1007\/BFb0035835"},{"key":"47_CR23","unstructured":"Till Tantau (2003). Logspace Optimisation Problems and their Approximation Properties. Technical Report TR03-077, Electronic Colloquium on Computational Complexity."},{"key":"47_CR24","doi-asserted-by":"crossref","unstructured":"Thomas Thierauf & Fabian Wagner (2010). The Isomorphism Problem for Planar 3-Connected Graphs Is in Unambiguous Logspace. Theor. Comp. Sys. 47, 655\u2013673. ISSN 1432-4350. doi: 10.1007\/s00224-009-9188-4 .","DOI":"10.1007\/s00224-009-9188-4"},{"key":"47_CR25","unstructured":"Thomas Thierauf & Fabin Wagner (2009). Reachability in K 3,3-free Graphs and K 5-free Graphs is in Unambiguous Log-Space. In 17th International Conference on Foundations of Computation Theory (FCT), Lecture Notes in Computer Science 5699, 323\u2013334. Springer-Verlag."},{"key":"47_CR26","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"Valiant Leslie","year":"1976","unstructured":"Leslie Valiant (1976) The Relative Complexity of Checking and Evaluating. Information Processing Letters 5: 20\u201323","journal-title":"Information Processing Letters"},{"key":"47_CR27","doi-asserted-by":"crossref","unstructured":"Avi Wigderson (1994). NL\/poly $${{{\\rm NL\/poly} \\subseteq \\oplus{\\rm L\/poly}}}$$ . In Proceedings of the 9th Structures in Complexity conference, 59\u201362.","DOI":"10.1109\/SCT.1994.315817"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0047-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-012-0047-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0047-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,4]],"date-time":"2019-07-04T04:52:51Z","timestamp":1562215971000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-012-0047-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,25]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["47"],"URL":"https:\/\/doi.org\/10.1007\/s00037-012-0047-3","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9,25]]}}}