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.
Original languageEnglish
Title of host publication Implementation and Application of Automata
EditorsTaylor J. Smith
PublisherSpringer Nature
Pages138-150
Number of pages13
ISBN (Electronic)978-3-032-35967-4
ISBN (Print)978-3-032-31176-4
DOIs
StatePublished - 5 Aug 2026
Event30th International Conference on Implementation and Application of Automata - Queen's University, Kingston, Canada
Duration: 5 Aug 2026 → 8 Aug 2026
Conference number: 30
https://research.cs.queensu.ca/ciaa2026/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume16695
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference30th International Conference on Implementation and Application of Automata
Abbreviated titleCIAA 2026
Country/TerritoryCanada
CityKingston
Period5/08/26 → 8/08/26
Internet address

    Research areas

  • Finite automata, Reversibility, Reversible automata, State complexity, Sweeping automata, Two-way automata

ID: 159460557