{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:14:10Z","timestamp":1767237250751,"version":"3.40.3"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030681944"},{"type":"electronic","value":"9783030681951"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-68195-1_7","type":"book-chapter","created":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T00:04:27Z","timestamp":1613952267000},"page":"81-93","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Transformation of Two-Way Deterministic Finite Automata to Unambiguous 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":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1615-2725","authenticated-orcid":false,"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,22]]},"reference":[{"key":"7_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, 237\u2013269 (1993). https:\/\/doi.org\/10.1007\/BF01371727","journal-title":"Math. Syst. Theory"},{"key":"7_CR2","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":"7_CR3","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, 1173\u20131187 (2007)","journal-title":"Inf. Comput."},{"key":"7_CR4","unstructured":"Geffert, V., Okhotin, A.: One-way simulation of two-way finite automata over small alphabets. In: NCMA (2013)"},{"key":"7_CR5","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1142\/S012905411842008X","volume":"29","author":"J Jir\u00e1sek","year":"2018","unstructured":"Jir\u00e1sek, J., Jir\u00e1skov\u00e1, G., Sebej, J.: Operations on unambiguous finite automata. Int. J. Found. Comput. Sci. 29, 861\u2013876 (2018)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"7_CR6","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":"C Kapoutsis","year":"2005","unstructured":"Kapoutsis, C.: Removing bidirectionality from nondeterministic finite automata. In: J\u0229jowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 544\u2013555. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11549345_47"},{"key":"7_CR7","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/s00224-013-9465-0","volume":"55","author":"CA Kapoutsis","year":"2013","unstructured":"Kapoutsis, C.A.: Two-way automata versus logarithmic space. Theory Comput. Syst. 55, 421\u2013447 (2013). https:\/\/doi.org\/10.1007\/s00224-013-9465-0","journal-title":"Theory Comput. Syst."},{"key":"7_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/978-3-642-22321-1_28","volume-title":"Developments in Language Theory","author":"M Kunc","year":"2011","unstructured":"Kunc, M., Okhotin, A.: Describing periodicity in two-way deterministic finite automata using transformation semigroups. In: Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol. 6795, pp. 324\u2013336. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22321-1_28"},{"key":"7_CR9","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, 975\u2013984 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"7_CR10","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, 1976\u20131992 (2001)","journal-title":"SIAM J. Comput."},{"key":"7_CR11","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 Trans. Comput. C\u201320, 1211\u20131214 (1971)","journal-title":"IEEE Trans. Comput."},{"key":"7_CR12","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)","journal-title":"Inf. Comput."},{"key":"7_CR13","unstructured":"Raskin, M.: A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton. In: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 107, pp. 138:1\u2013138:11 (2018)"},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1137\/0218083","volume":"18","author":"B Ravikumar","year":"1989","unstructured":"Ravikumar, B., Ibarra, O.: Relating the type of ambiguity of finite automata to the succinctness of their representation. SIAM J. Comput. 18, 1263\u20131282 (1989)","journal-title":"SIAM J. Comput."},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two way finite automata. In: STOC 1978 (1978)","DOI":"10.1145\/800133.804357"},{"key":"7_CR16","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"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1147\/rd.32.0198","volume":"3","author":"J Shepherdson","year":"1959","unstructured":"Shepherdson, J.: The reduction of two-way automata to one-way automata. IBM J. Res. Dev. 3, 198\u2013200 (1959)","journal-title":"IBM J. Res. Dev."},{"key":"7_CR18","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, 261\u2013264 (1989)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-68195-1_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,10]],"date-time":"2021-03-10T09:06:57Z","timestamp":1615367217000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-68195-1_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030681944","9783030681951"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-68195-1_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"22 February 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Language and Automata Theory and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Milan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 March 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 March 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"lata2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/irdta.eu\/lata2020&2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"52","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"50% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}