DOI

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).
Язык оригиналаанглийский
Название основной публикацииImplementation and Application of Automata
Подзаголовок основной публикации29th International Conference, CIAA 2025, Palermo, Italy, September 22–25, 2025, Proceedings
РедакторыGiuseppa Castiglione, Sabrina Mantaci
ИздательSpringer Nature
Страницы180–192
Число страниц13
ISBN (печатное издание)9783032026019
DOI
СостояниеОпубликовано - 22 авг 2025
Событие29th International Conference on Implementation and Application of Automata - Палермо, Италия
Продолжительность: 22 сен 202525 сен 2025
Номер конференции: 29
https://ciaa2025.unipa.it/

Серия публикаций

НазваниеLecture Notes in Computer Science
Том15981 LNCS

конференция

конференция29th International Conference on Implementation and Application of Automata
Сокращенное названиеCIAA 2025
Страна/TерриторияИталия
ГородПалермо
Период22/09/2525/09/25
Сайт в сети Internet

ID: 140132084