• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Reversible Two-Way Finite Automata Over a Unary Alphabet

Alexander Okhotin, Michal Kunc, Reversible Two-Way Finite Automata Over a Unary Alphabet. TUCS Technical Reports 1024, Turku Centre for Computer Science, 2011.

Abstract:

It is established that transforming an n-state two-way deterministic finite automaton over a one-letter alphabet to an equivalent two-way reversible automaton requires between 2n-2 and 2n+3 states.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tOkKu11a,
  title = {Reversible Two-Way Finite Automata Over a Unary Alphabet},
  author = {Okhotin, Alexander and Kunc, Michal},
  number = {1024},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2011},
  keywords = {Finite automata, two-way automata, reversible automata, unary languages, descriptional complexity, reversible computation},
  ISBN = {978-952-12-2661-8},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication