{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:48:07Z","timestamp":1770994087916,"version":"3.50.1"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319214993","type":"print"},{"value":"9783319215006","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-21500-6_9","type":"book-chapter","created":{"date-parts":[[2015,7,17]],"date-time":"2015-07-17T08:07:44Z","timestamp":1437120464000},"page":"120-131","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the Size of Two-Way Reasonable Automata for the Liveness Problem"],"prefix":"10.1007","author":[{"given":"Maria Paola","family":"Bianchi","sequence":"first","affiliation":[]},{"given":"Juraj","family":"Hromkovi\u010d","sequence":"additional","affiliation":[]},{"given":"Ivan","family":"Kov\u00e1\u010d","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,7,18]]},"reference":[{"key":"9_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/3-540-10003-2_62","volume-title":"Automata, Languages and Programming","author":"P Berman","year":"1980","unstructured":"Berman, P.: A note on sweeping automata. In: de Bakker, J., van Leeuwen, J. (eds.) ICALP. LNCS, vol. 85, pp. 91\u201397. Springer, Heidelberg (1980)"},{"key":"9_CR2","unstructured":"Berman, P., Lingas, A.: On complexity of regular languages in terms of finite automata. Technical report, Institute of Computer Science, Polish Academy of Sciences, Warsaw (1977)"},{"issue":"2","key":"9_CR3","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. Comp. Sci. 47(2), 149\u2013158 (1986)","journal-title":"Theor. Comp. Sci."},{"issue":"11","key":"9_CR4","doi-asserted-by":"publisher","first-page":"1652","DOI":"10.1016\/j.ic.2007.07.001","volume":"205","author":"V Geffert","year":"2007","unstructured":"Geffert, V.: Magic numbers in the state hierarchy of finite automata. Information and Computation 205(11), 1652\u20131670 (2007)","journal-title":"Information and Computation"},{"key":"9_CR5","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. Comp. Sci. 295, 189\u2013203 (2003)","journal-title":"Theor. Comp. Sci."},{"issue":"7","key":"9_CR6","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":"9_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/3-540-45061-0_36","volume-title":"Automata, Languages and Programming","author":"J Hromkovi\u010d","year":"2003","unstructured":"Hromkovi\u010d, J., Schnitger, G.: Nondeterminism versus determinism for two-way finite automata: generalizations of Sipser\u2019s separation. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 439\u2013451. Springer, Heidelberg (2003)"},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/11549345_47","volume-title":"Mathematical Foundations of Computer Science 2005","author":"CA Kapoutsis","year":"2005","unstructured":"Kapoutsis, C.A.: Removing bidirectionality from nondeterministic finite automata. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 544\u2013555. Springer, Heidelberg (2005)"},{"key":"9_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-642-02737-6_4","volume-title":"Developments in Language Theory","author":"CA Kapoutsis","year":"2009","unstructured":"Kapoutsis, C.A.: Size complexity of two-way finite automata. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol. 5583, pp. 47\u201366. Springer, Heidelberg (2009)"},{"key":"9_CR10","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/j.ic.2012.11.001","volume":"222","author":"CA Kapoutsis","year":"2013","unstructured":"Kapoutsis, C.A.: Nondeterminism is essential in small two-way finite automata with few reversals. Inf. Comput. 222, 208\u2013227 (2013)","journal-title":"Inf. Comput."},{"issue":"2","key":"9_CR11","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1016\/j.jcss.2011.06.004","volume":"78","author":"CA Kapoutsis","year":"2012","unstructured":"Kapoutsis, C.A., Kr\u00e1lovi\u010d, R., M\u00f6mke, T.: Size complexity of rotating and sweeping automata. Journal of Computer and System Sciences 78(2), 537\u2013558 (2012)","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"9_CR12","first-page":"778","volume":"10","author":"AN Kolodin","year":"1972","unstructured":"Kolodin, A.N.: Two-way nondeterministic automata. Cybernetics and Systems Analysis 10(5), 778\u2013785 (1972)","journal-title":"Cybernetics and Systems Analysis"},{"key":"#cr-split#-9_CR13.1","unstructured":"Lupanov, O.: A comparison of two types of finite automata. Problemy Kibernet 9, 321-326 (1993). (in Russian)"},{"key":"#cr-split#-9_CR13.2","unstructured":"German translation: \u00dcber den Vergleich zweier Typen endlicher Quellen. Probleme der Kybernetik 6, 329-335 (1966)"},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0020-0190(81)90012-0","volume":"12","author":"S Micali","year":"1981","unstructured":"Micali, S.: Two-way deterministic finite automata are exponentially more succinct than sweeping automata. Inf. Process. Lett. 12, 103\u2013105 (1981)","journal-title":"Inf. Process. Lett."},{"issue":"10","key":"9_CR15","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"C\u201320","author":"FR Moore","year":"1971","unstructured":"Moore, F.R.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Transactions on Computers C\u201320(10), 1211\u20131214 (1971)","journal-title":"IEEE Transactions on Computers"},{"issue":"2","key":"9_CR16","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(2), 114\u2013125 (1959)","journal-title":"IBM J. Res. Dev."},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two way finite automata. In: Proc. of the 10th Annual ACM Symposium on Theory of Computing (STOC 1978), pp. 275\u2013286. ACM Press, New York (1978)","DOI":"10.1145\/800133.804357"},{"key":"9_CR18","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. Journal of Computer and System Sciences 21, 195\u2013202 (1980)","journal-title":"Journal of Computer and System Sciences"},{"key":"9_CR19","unstructured":"\u0160tefanec, R.: Semantically restricted two-way automata. PhD Thesis, Comenius University in Bratislava (2014)"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21500-6_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T10:44:36Z","timestamp":1676025876000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21500-6_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319214993","9783319215006"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21500-6_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"18 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}