It is shown that an n-state two-way nondeterministic finite automaton (2NFA) over an alphabet Σ can be transformed to a one-way automaton (1NFA) with |Σ|·n12+1 states, where n12∼34πn3n is a trinomial coefficient. A close lower bound of n12 states is given for a four-symbol alphabet. To compare, for unrestricted alphabets, this transformation is known to require 2nn+1∼1πn4n states (Kapoutsis, “Removing bidirectionality from nondeterministic finite automata”, MFCS 2005).
Original languageEnglish
Title of host publicationImplementation and Application of Automata
Subtitle of host publication29th International Conference, CIAA 2025, Palermo, Italy, September 22–25, 2025, Proceedings
EditorsGiuseppa Castiglione, Sabrina Mantaci
PublisherSpringer Nature
Pages180–192
Number of pages13
ISBN (Print)9783032026019
DOIs
StatePublished - 22 Aug 2025
Event29th International Conference on Implementation and Application of Automata - Палермо, Italy
Duration: 22 Sep 202525 Sep 2025
Conference number: 29
https://ciaa2025.unipa.it/

Publication series

NameLecture Notes in Computer Science
Volume15981 LNCS

Conference

Conference29th International Conference on Implementation and Application of Automata
Abbreviated titleCIAA 2025
Country/TerritoryItaly
CityПалермо
Period22/09/2525/09/25
Internet address

    Research areas

  • Two-way finite automata, nondeterministic finite automata, state complexity

ID: 140132084