{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T10:25:26Z","timestamp":1780050326154,"version":"3.53.1"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662445211","type":"print"},{"value":"9783662445228","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44522-8_25","type":"book-chapter","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T10:12:23Z","timestamp":1407838343000},"page":"291-302","source":"Crossref","is-referenced-by-count":8,"title":["Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata"],"prefix":"10.1007","author":[{"given":"Viliam","family":"Geffert","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"25_CR1","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0304-3975(93)90160-U","volume":"119","author":"J.-C. Birget","year":"1993","unstructured":"Birget, J.-C.: Partial orders on words, minimal elements of regular languages, and state complexity. Theoretical Computer Science\u00a0119, 267\u2013291 (1993)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"25_CR2","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/BF01371727","volume":"26","author":"J.-C. Birget","year":"1993","unstructured":"Birget, J.-C.: State-complexity of finite-state devices, state compressibility and incompressibility. Mathematical Systems Theory\u00a026(3), 237\u2013269 (1993)","journal-title":"Mathematical Systems Theory"},{"key":"25_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2012.04.044","volume":"445","author":"V. Geffert","year":"2012","unstructured":"Geffert, V.: An alternating hierarchy for finite automata. Theoretical Computer Science\u00a0445, 1\u201324 (2012)","journal-title":"Theoretical Computer Science"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Geffert, V., Mereghetti, C., Pighizzini, G.: Converting two-way nondeterministic unary automata into simpler automata. Theoretical Computer Science\u00a0295(1-3), 189\u2013203 (2003)","DOI":"10.1016\/S0304-3975(02)00403-6"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"Geffert, V., Mereghetti, C., Pighizzini, G.: Complementing two-way finite automata. Information and Computation 205(8), 1173\u20131187 (2007)","DOI":"10.1016\/j.ic.2007.01.008"},{"key":"25_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.A. Kapoutsis","year":"2005","unstructured":"Kapoutsis, C.A.: Removing bidirectionality from nondeterministic finite automata. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 544\u2013555. Springer, Heidelberg (2005)"},{"key":"25_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/978-3-642-20712-9_28","volume-title":"Computer Science \u2013 Theory and Applications","author":"C.A. Kapoutsis","year":"2011","unstructured":"Kapoutsis, C.A.: Two-way automata versus logarithmic space. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 359\u2013372. Springer, Heidelberg (2011)"},{"key":"25_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/978-3-642-40313-2_53","volume-title":"Mathematical Foundations of Computer Science 2013","author":"M. Kunc","year":"2013","unstructured":"Kunc, M., Okhotin, A.: Reversibility of computations in graph-walking automata. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol.\u00a08087, pp. 595\u2013606. Springer, Heidelberg (2013)"},{"key":"25_CR9","doi-asserted-by":"crossref","unstructured":"Ladner, R., Lipton, R., Stockmeyer, L.: Alternating pushdown and stack automata. SIAM Journal on Computing 13(1), 135\u2013155 (1984)","DOI":"10.1137\/0213010"},{"issue":"5","key":"25_CR10","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0020-0190(89)90205-6","volume":"30","author":"M. Vardi","year":"1989","unstructured":"Vardi, M.: A note on the reduction of two-way automata to one-way automata. Information Processing Letters\u00a030(5), 261\u2013264 (1989)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44522-8_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T14:38:46Z","timestamp":1558967926000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44522-8_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662445211","9783662445228"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44522-8_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}