{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,27]],"date-time":"2026-07-27T20:04:51Z","timestamp":1785182691932,"version":"3.55.0"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032014740","type":"print"},{"value":"9783032014757","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,8,17]],"date-time":"2025-08-17T00:00:00Z","timestamp":1755388800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,17]],"date-time":"2025-08-17T00:00:00Z","timestamp":1755388800000},"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-01475-7_8","type":"book-chapter","created":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T17:39:19Z","timestamp":1755365959000},"page":"107-122","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the\u00a0Transformation of\u00a0Two-Way Nondeterministic Finite Automata to\u00a0Unambiguous Finite Automata"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2053-3731","authenticated-orcid":false,"given":"Semyon","family":"Petrov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1615-2725","authenticated-orcid":false,"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,8,17]]},"reference":[{"issue":"3","key":"8_CR1","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/BF01371727","volume":"26","author":"J Birget","year":"1993","unstructured":"Birget, J.: State-complexity of finite-state devices, state compressibility and incompressibility. Math. Syst. Theory 26(3), 237\u2013269 (1993). https:\/\/doi.org\/10.1007\/BF01371727","journal-title":"Math. Syst. Theory"},{"issue":"3","key":"8_CR2","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(3), 149\u2013158 (1986). https:\/\/doi.org\/10.1016\/0304-3975(86)90142-8","journal-title":"Theor. Comput. Sci."},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"103634","DOI":"10.1016\/J.JCSS.2025.103634","volume":"151","author":"W Czerwinski","year":"2025","unstructured":"Czerwinski, W., et al.: Languages given by finite automata over the unary alphabet. J. Comput. Syst. Sci. 151, 103634 (2025). https:\/\/doi.org\/10.1016\/J.JCSS.2025.103634","journal-title":"J. Comput. Syst. Sci."},{"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). https:\/\/doi.org\/10.1016\/S0304-3975(02)00403-6","journal-title":"Theor. Comput. Sci."},{"issue":"8","key":"8_CR5","doi-asserted-by":"publisher","first-page":"1173","DOI":"10.1016\/J.IC.2007.01.008","volume":"205","author":"V Geffert","year":"2007","unstructured":"Geffert, V., Mereghetti, C., Pighizzini, G.: Complementing two-way finite automata. Inf. Comput. 205(8), 1173\u20131187 (2007). https:\/\/doi.org\/10.1016\/J.IC.2007.01.008","journal-title":"Inf. Comput."},{"key":"8_CR6","unstructured":"Geffert, V., Okhotin, A.: One-way simulation of two-way finite automata over small alphabets. In: Bensch, S., Drewes, F., Freund, R., Otto, F. (eds.) Fifth Workshop on Non-Classical Models for Automata and Applications - NCMA 2013, Ume\u00e5, Sweden, August 13\u201314, 2013, Proceedings. books@ocg.at, vol.\u00a0294, pp. 151\u2013162. \u00d6sterreichische Computer Gesellschaft (2013)"},{"key":"8_CR7","doi-asserted-by":"publisher","unstructured":"Geffert, V., Okhotin, A.: Transforming two-way alternating finite automata to one-way nondeterministic automata. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25\u201329, 2014. Proceedings, Part I. LNCS, vol.\u00a08634, pp. 291\u2013302. Springer (2014).https:\/\/doi.org\/10.1007\/978-3-662-44522-8_25","DOI":"10.1007\/978-3-662-44522-8_25"},{"key":"8_CR8","doi-asserted-by":"publisher","unstructured":"Geffert, V., Okhotin, A.: Deterministic one-way simulation of two-way deterministic finite automata over small alphabets. In: Han, Y., Ko, S. (eds.) Descriptional Complexity of Formal Systems - 23rd IFIP WG 1.02 International Conference, DCFS 2021, Virtual Event, September 5, 2021, Proceedings. LNCS, vol. 13037, pp. 26\u201337. Springer (2021). https:\/\/doi.org\/10.1007\/978-3-030-93489-7_3","DOI":"10.1007\/978-3-030-93489-7_3"},{"key":"8_CR9","doi-asserted-by":"publisher","unstructured":"G\u00f6\u00f6s, M., Kiefer, S., Yuan, W.: Lower bounds for unambiguous automata via communication complexity. In: Bojanczyk, M., Merelli, E., Woodruff, D.P. (eds.) 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4\u20138, 2022, Paris, France. LIPIcs, vol.\u00a0229, pp. 126:1\u2013126:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022). https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2022.126","DOI":"10.4230\/LIPICS.ICALP.2022.126"},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"106270","DOI":"10.1016\/J.IPL.2022.106270","volume":"177","author":"E Indzhev","year":"2022","unstructured":"Indzhev, E., Kiefer, S.: On complementing unambiguous automata and graphs with many cliques and cocliques. Inf. Process. Lett. 177, 106270 (2022). https:\/\/doi.org\/10.1016\/J.IPL.2022.106270","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"8_CR11","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1142\/S012905411842008X","volume":"29","author":"J Jir\u00e1sek Jr","year":"2018","unstructured":"Jir\u00e1sek, J., Jr., Jir\u00e1skov\u00e1, G., Sebej, J.: Operations on unambiguous finite automata. Int. J. Found. Comput. Sci. 29(5), 861\u2013876 (2018). https:\/\/doi.org\/10.1142\/S012905411842008X","journal-title":"Int. J. Found. Comput. Sci."},{"key":"8_CR12","doi-asserted-by":"publisher","unstructured":"Kapoutsis, C.A.: Removing bidirectionality from nondeterministic finite automata. In: Jedrzejowicz, J., Szepietowski, A. (eds.) Mathematical Foundations of Computer Science 2005, 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29 - September 2, 2005, Proceedings. LNCS, vol.\u00a03618, pp. 544\u2013555. Springer (2005). https:\/\/doi.org\/10.1007\/11549345_47","DOI":"10.1007\/11549345_47"},{"key":"8_CR13","unstructured":"D Kapoutsis, C.A.: Algorithms and lower bounds in finite automata size complexity, Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA, USA (2006). https:\/\/hdl.handle.net\/1721.1\/37891"},{"issue":"2","key":"8_CR14","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/S00224-013-9465-0","volume":"55","author":"CA Kapoutsis","year":"2014","unstructured":"Kapoutsis, C.A.: Two-way automata versus logarithmic space. Theory Comput. Syst. 55(2), 421\u2013447 (2014). https:\/\/doi.org\/10.1007\/S00224-013-9465-0","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"8_CR15","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1007\/s00224-014-9560-x","volume":"56","author":"CA Kapoutsis","year":"2014","unstructured":"Kapoutsis, C.A., Pighizzini, G.: Two-way automata characterizations of L\/poly versus NL. Theory Comput. Syst. 56(4), 662\u2013685 (2014). https:\/\/doi.org\/10.1007\/s00224-014-9560-x","journal-title":"Theory Comput. Syst."},{"key":"8_CR16","doi-asserted-by":"publisher","unstructured":"Kunc, M., Okhotin, A.: Describing periodicity in two-way deterministic finite automata using transformation semigroups. In: Mauri, G., Leporati, A. (eds.) Developments in Language Theory - 15th International Conference, DLT 2011, Milan, Italy, July 19\u201322, 2011. Proceedings. LNCS, vol.\u00a06795, pp. 324\u2013336. Springer (2011). https:\/\/doi.org\/10.1007\/978-3-642-22321-1_28","DOI":"10.1007\/978-3-642-22321-1_28"},{"issue":"4","key":"8_CR17","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/S0097539793252092","volume":"27","author":"H Leung","year":"1998","unstructured":"Leung, H.: Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata. SIAM J. Comput. 27(4), 1073\u20131082 (1998). https:\/\/doi.org\/10.1137\/S0097539793252092","journal-title":"SIAM J. Comput."},{"issue":"5","key":"8_CR18","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1142\/S0129054105003418","volume":"16","author":"H Leung","year":"2005","unstructured":"Leung, H.: Descriptional complexity of NFA of different ambiguity. Int. J. Found. Comput. Sci. 16(5), 975\u2013984 (2005). https:\/\/doi.org\/10.1142\/S0129054105003418","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"6","key":"8_CR19","doi-asserted-by":"publisher","first-page":"1976","DOI":"10.1137\/S009753979935431X","volume":"30","author":"C Mereghetti","year":"2001","unstructured":"Mereghetti, C., Pighizzini, G.: Optimal simulations between unary automata. SIAM J. Comput. 30(6), 1976\u20131992 (2001). https:\/\/doi.org\/10.1137\/S009753979935431X","journal-title":"SIAM J. Comput."},{"key":"8_CR20","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/J.IC.2012.01.003","volume":"212","author":"A Okhotin","year":"2012","unstructured":"Okhotin, A.: Unambiguous finite automata over a unary alphabet. Inf. Comput. 212, 15\u201336 (2012). https:\/\/doi.org\/10.1016\/J.IC.2012.01.003","journal-title":"Inf. Comput."},{"issue":"1","key":"8_CR21","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/s10474-023-01299-6","volume":"169","author":"F Petrov","year":"2023","unstructured":"Petrov, F.: Logarithmic asymptotics of Landau-Okhotin function. Acta Math. Hungar. 169(1), 272\u2013276 (2023). https:\/\/doi.org\/10.1007\/s10474-023-01299-6","journal-title":"Acta Math. Hungar."},{"issue":"Part A","key":"8_CR22","doi-asserted-by":"publisher","first-page":"104956","DOI":"10.1016\/J.IC.2022.104956","volume":"295","author":"S Petrov","year":"2023","unstructured":"Petrov, S., Okhotin, A.: On the transformation of two-way finite automata to unambiguous finite automata. Inf. Comput. 295(Part A), 104956 (2023). https:\/\/doi.org\/10.1016\/J.IC.2022.104956","journal-title":"Inf. Comput."},{"key":"8_CR23","unstructured":"Petrov, S., Petrov, F., Okhotin, A.: On the rank of the communication matrix for deterministic two-way finite automata. arXiv preprint arXiv:2312.05909 (2023)"},{"key":"8_CR24","doi-asserted-by":"publisher","unstructured":"Radionova, M., Okhotin, A.: Sweeping permutation automata. In: Nagy, B., Freund, R. (eds.) Proceedings of the 13th International Workshop on Non-Classical Models of Automata and Applications, NCMA 2023, Famagusta, North Cyprus, 18th\u201319th September, 2023. EPTCS, vol.\u00a0388, pp. 110\u2013124 (2023). https:\/\/doi.org\/10.4204\/EPTCS.388.11","DOI":"10.4204\/EPTCS.388.11"},{"issue":"4","key":"8_CR25","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1007\/BF01192528","volume":"15","author":"R Raz","year":"1995","unstructured":"Raz, R., Spieker, B.: On the log rank-conjecture in communication complexity. Combinatorica 15(4), 567\u2013588 (1995). https:\/\/doi.org\/10.1007\/BF01192528","journal-title":"Combinatorica"},{"key":"8_CR26","doi-asserted-by":"crossref","unstructured":"Schmidt, E.M.: Succinctness of descriptions of context-free, regular and finite languages, Ph.D. thesis, Cornell University, Ithaca, New York (1977)","DOI":"10.7146\/dpb.v7i84.6500"},{"issue":"2","key":"8_CR27","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1147\/RD.32.0198","volume":"3","author":"JC Shepherdson","year":"1959","unstructured":"Shepherdson, J.C.: The reduction of two-way automata to one-way automata. IBM J. Res. Dev. 3(2), 198\u2013200 (1959). https:\/\/doi.org\/10.1147\/RD.32.0198","journal-title":"IBM J. Res. Dev."},{"issue":"5","key":"8_CR28","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0020-0190(89)90205-6","volume":"30","author":"MY Vardi","year":"1989","unstructured":"Vardi, M.Y.: A note on the reduction of two-way automata to one-way automata. Inf. Process. Lett. 30(5), 261\u2013264 (1989). https:\/\/doi.org\/10.1016\/0020-0190(89)90205-6","journal-title":"Inf. Process. Lett."}],"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-032-01475-7_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,27]],"date-time":"2026-07-27T19:28:33Z","timestamp":1785180513000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-01475-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,17]]},"ISBN":["9783032014740","9783032014757"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-01475-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,17]]},"assertion":[{"value":"17 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DLT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Developments in Language Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Seoul","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Korea (Republic of)","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":"19 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dlt2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/cida.uos.ac.kr\/dlt2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}