DOI

It is proved that every two-way reversible finite automaton (2RFA) with n states can be simulated by a partial one-way deterministic finite automaton (1DFA) with φ(n) states, where φ is a certain integer function of growth rate φ(n)=O((n2)n/2+3/2). Furthermore, it is shown that exactly φ(n) states are necessary in the worst case, with witness languages defined by sweeping reversible automata over a 4-symbol alphabet. The second result of the paper is a new lower bound 2n+2nlnn+o(1) on the complexity of transforming a deterministic two-way finite automaton (2DFA) to a 2RFA, cf. the known upper bound of 4n+3 states.
Язык оригиналаанглийский
Название основной публикации Implementation and Application of Automata
РедакторыTaylor J. Smith
ИздательSpringer Nature
Страницы138-150
Число страниц13
ISBN (электронное издание)978-3-032-35967-4
ISBN (печатное издание)978-3-032-31176-4
DOI
СостояниеОпубликовано - 5 авг 2026
Событие30th International Conference on Implementation and Application of Automata - Queen's University, Kingston, Канада
Продолжительность: 5 авг 2026 → 8 авг 2026
Номер конференции: 30
https://research.cs.queensu.ca/ciaa2026/

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

НазваниеLecture Notes in Computer Science
ИздательSpringer
Том16695
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция30th International Conference on Implementation and Application of Automata
Сокращенное названиеCIAA 2026
Страна/TерриторияКанада
ГородKingston
Период5/08/26 → 8/08/26
Сайт в сети Internet

ID: 159460557