{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T18:36:25Z","timestamp":1770921385768,"version":"3.50.1"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032178008","type":"print"},{"value":"9783032178015","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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-17801-5_8","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:52:58Z","timestamp":1770918778000},"page":"104-116","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Quadratic Lower Bound for 2dfas Against One-Way Liveness"],"prefix":"10.1007","author":[{"given":"Kehinde","family":"Adeogun","sequence":"first","affiliation":[]},{"given":"Christos","family":"Kapoutsis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Sakoda, W.J.,\u00a0Sipser, M.: Nondeterminism and the size of two-way finite automata. In: Proceedings of STOC, pp. 275\u2013286 (1978)","DOI":"10.1145\/800133.804357"},{"key":"8_CR2","unstructured":"Seiferas, J.I.: Untitled, manuscript communicated to M.\u00a0Sipser (1973)"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Guillon, B.,\u00a0Pighizzini, G.,\u00a0Prigioniero, L.,\u00a0Pr\u016f\u0161a, D.: Converting nondeterministic two-way automata into small deterministic linear-time machines. Inf. Comput. 289 (2022)","DOI":"10.1016\/j.ic.2022.104938"},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0304-3975(02)00403-6","volume":"295","author":"V Geffert","year":"2003","unstructured":"Geffert, V., Mereghetti, C., Pighizzini, G.: Converting two-way nondeterministic unary automata into simpler automata. Theor. Comput. Sci. 295, 189\u2013203 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Clerici, A.,\u00a0Pighizzini, G.,\u00a0Prigioniero, L.: Two-way automata and bounded languages. In: Proceedings of CIAA, pp. 73\u201385 (2025)","DOI":"10.1007\/978-3-032-02602-6_6"},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.ic.2014.08.009","volume":"239","author":"V Geffert","year":"2014","unstructured":"Geffert, V., Guillon, B., Pighizzini, G.: Two-way automata making choices only at the endmarkers. Inf. Comput. 239, 71\u201386 (2014)","journal-title":"Inf. Comput."},{"issue":"2","key":"8_CR7","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-0000(80)90034-3","volume":"21","author":"M Sipser","year":"1980","unstructured":"Sipser, M.: Lower bounds on the size of sweeping automata. J. Comput. Syst. Sci. 21(2), 195\u2013202 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Hromkovi\u010d, J.,\u00a0Schnitger, G.: Nondeterminism versus determinism for two-way finite automata: generalizations of Sipser\u2019s separation. In: Proceedings of ICALP, pp. 439\u2013451 (2003)","DOI":"10.1007\/3-540-45061-0_36"},{"key":"8_CR9","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/j.ic.2012.11.001","volume":"222","author":"C Kapoutsis","year":"2013","unstructured":"Kapoutsis, C.: Nondeterminism is essential in small two-way finite automata with few reversals. Inf. Comput. 222, 208\u2013227 (2013)","journal-title":"Inf. Comput."},{"issue":"7","key":"8_CR10","doi-asserted-by":"publisher","first-page":"955","DOI":"10.1142\/S012905411340025X","volume":"24","author":"J Hromkovi\u010d","year":"2013","unstructured":"Hromkovi\u010d, J., Kr\u00e1lovi\u010d, R., Kr\u00e1lovi\u010d, R., \u0160tefanec, R.: Determinism vs. nondeterminism for two-way automata: representing the meaning of states by logical formul\u00e6. Int. J. Found. Comput. Sci. 24(7), 955\u2013978 (2013)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Bianchi, M.P.,\u00a0Hromkovi\u010d, J.,\u00a0Kov\u00e1\u010d, I.: On the size of two-way reasonable automata for the liveness problem. In: Proceedings of DLT, pp. 120\u2013131 (2015)","DOI":"10.1007\/978-3-319-21500-6_9"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Raszyk, M.: On the size of logical automata. In: Proceedings of SOFSEM, pp. 447\u2013460 (2019)","DOI":"10.1007\/978-3-030-10801-4_35"},{"issue":"1\u20132","key":"8_CR13","first-page":"215","volume":"12","author":"C Kapoutsis","year":"2007","unstructured":"Kapoutsis, C.: Deterministic moles cannot solve liveness. J. Autom. Lang. Comb. 12(1\u20132), 215\u2013235 (2007)","journal-title":"J. Autom. Lang. Comb."},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","volume":"47","author":"M Chrobak","year":"1986","unstructured":"Chrobak, M.: Finite automata and unary languages. Theor. Comput. Sci. 47, 149\u2013158 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"1010","DOI":"10.1016\/j.ipl.2009.06.005","volume":"109","author":"AW To","year":"2009","unstructured":"To, A.W.: Unary finite automata vs. arithmetic progressions. Inf. Process. Lett. 109, 1010\u20131014 (2009)","journal-title":"Inf. Process. Lett."},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"Kapoutsis, C.: Optimal 2DFA algorithms for one-way liveness on two and three symbols. In: B\u00f6ckenhauer et\u00a0al. [23], pp. 33\u201348 (2018)","DOI":"10.1007\/978-3-319-98355-4_3"},{"key":"8_CR17","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"MO Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3, 114\u2013125 (1959)","journal-title":"IBM J. Res. Dev."},{"key":"8_CR18","unstructured":"Sipser, M.: Introduction to the Theory of Computation, 3rd edn. Cengage Learning (2012)"},{"key":"8_CR19","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0304-3975(80)90053-5","volume":"10","author":"M Sipser","year":"1980","unstructured":"Sipser, M.: Halting space-bounded computations. Theor. Comput. Sci. 10, 335\u2013338 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"Kapoutsis, C.: Small sweeping 2NFAs are not closed under complement. In: Proceedings of ICALP, pp. 144\u2013156 (2006)","DOI":"10.1007\/11786986_14"},{"issue":"2","key":"8_CR21","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1016\/j.jcss.2011.06.004","volume":"78","author":"C Kapoutsis","year":"2012","unstructured":"Kapoutsis, C., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: Size complexity of rotating and sweeping automata. J. Comput. Syst. Sci. 78(2), 537\u2013558 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Kapoutsis, C.,\u00a0Pighizzini, G.: Reversal hierarchies for small 2DFAs. In: Proceedings of MFCS, pp. 554\u2013565 (2012)","DOI":"10.1007\/978-3-642-32589-2_49"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"B\u00f6ckenhauer, H.-J.,\u00a0Komm, D.,\u00a0Unger, W. (eds.): Adventures between lower bounds and higher altitudes \u2013 Essays dedicated to Juraj Hromkovi\u010d on the occasion of his 60th birthday, vol. 11011 of Lecture Notes in Computer Science. Springer, Heidelberg (2018)","DOI":"10.1007\/978-3-319-98355-4"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2026: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-17801-5_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:01Z","timestamp":1770918781000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17801-5_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032178008","9783032178015"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17801-5_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Krakow","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":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 February 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sofsem.uj.edu.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}