{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T00:10:12Z","timestamp":1758586212692,"version":"3.44.0"},"publisher-location":"Cham","reference-count":12,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032046994","type":"print"},{"value":"9783032047007","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T00:00:00Z","timestamp":1757548800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T00:00:00Z","timestamp":1757548800000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-04700-7_5","type":"book-chapter","created":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T23:45:34Z","timestamp":1758498334000},"page":"57-67","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Inductive Tracing and\u00a0the\u00a0Complexity of\u00a0Finding Hamiltonian Path in\u00a0DAGs"],"prefix":"10.1007","author":[{"given":"Ronak","family":"Bhadra","sequence":"first","affiliation":[]},{"given":"Raghunath","family":"Tewari","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,11]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","unstructured":"Bourke, C., Tewari, R., Vinodchandran, N.V.: Directed planar reachability is in unambiguous log-space. In: 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 13\u201316 June 2007, San Diego, California, USA, pp. 217\u2013221 (2007). https:\/\/doi.org\/10.1109\/CCC.2007.9","DOI":"10.1109\/CCC.2007.9"},{"key":"5_CR2","doi-asserted-by":"publisher","unstructured":"Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976). https:\/\/doi.org\/10.1016\/0304-3975(76)90059-1, https:\/\/www.sciencedirect.com\/science\/article\/pii\/0304397576900591","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"5_CR3","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 complement. SIAM J. Comput. 17, 935\u2013938 (1988)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"5_CR4","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A Itai","year":"1982","unstructured":"Itai, A., Papadimitriou, C.H., Szwarcfiter, J.L.: Hamilton paths in grid graphs. SIAM J. Comput. 11(4), 676\u2013686 (1982). https:\/\/doi.org\/10.1137\/0211056","journal-title":"SIAM J. Comput."},{"issue":"11","key":"5_CR5","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/368996.369025","volume":"5","author":"AB Kahn","year":"1962","unstructured":"Kahn, A.B.: Topological sorting of large networks. Commun. ACM 5(11), 558\u2013562 (1962). https:\/\/doi.org\/10.1145\/368996.369025","journal-title":"Commun. ACM"},{"key":"5_CR6","doi-asserted-by":"publisher","unstructured":"Kallampally, V.A.T., Tewari, R.: Trading determinism for time in space bounded computations. In: 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, 22\u201326 August 2016 - Krak\u00f3w, Poland, pp. 10:1\u201310:13 (2016). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2016.10","DOI":"10.4230\/LIPIcs.MFCS.2016.10"},{"key":"5_CR7","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a symposium on the Complexity of Computer Computations, held March 20\u201322, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, pp. 85\u2013103. Plenum Press, New York (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"5_CR8","unstructured":"Limaye, N., Mahajan, M., Nimbhorkar, P.: Longest paths in planar dags in unambiguous logspace. In: Proceedings of the Fifteenth Australasian Symposium on Computing: The Australasian Theory - Volume 94, pp. 101\u2013108. Australian Computer Society, Inc. (2009)"},{"issue":"3","key":"5_CR9","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1137\/17M1130538","volume":"48","author":"D van Melkebeek","year":"2019","unstructured":"van Melkebeek, D., Prakriya, G.: Derandomizing isolation in space-bounded settings. SIAM J. Comput. 48(3), 979\u20131021 (2019). https:\/\/doi.org\/10.1137\/17M1130538","journal-title":"SIAM J. Comput."},{"issue":"4","key":"5_CR10","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. 29(4), 1118\u20131131 (2000). https:\/\/doi.org\/10.1137\/S0097539798339041","journal-title":"SIAM J. Comput."},{"key":"5_CR11","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 26, 279\u2013284 (1988)","journal-title":"Acta Informatica"},{"key":"5_CR12","doi-asserted-by":"publisher","unstructured":"Thierauf, T., Wagner, F.: The isomorphism problem for planar 3-connected graphs is in unambiguous logspace. In: Albers, S., Weil, P. (eds.) STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, 21\u201323 February 2008, Proceedings, vol.\u00a01, pp. 633\u2013644. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Germany (2008). https:\/\/doi.org\/10.4230\/LIPICS.STACS.2008.1327","DOI":"10.4230\/LIPICS.STACS.2008.1327"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-04700-7_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,21]],"date-time":"2025-09-21T23:45:35Z","timestamp":1758498335000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-04700-7_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,11]]},"ISBN":["9783032046994","9783032047007"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-04700-7_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,9,11]]},"assertion":[{"value":"11 September 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FCT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Fundamentals of Computation Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Wroc\u0142aw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fct2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/fct.ii.uni.wroc.pl","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}