A Deterministic Two-Way Multi-head Finite Automaton Can Be Converted into a Reversible One with the Same Number of Heads

DOI10.1007/978-3-642-36315-3_3zbMath1451.68156OpenAlexW2115130389MaRDI QIDQ3453732

Kenichi Morita

Publication date: 30 November 2015

Published in: Reversible Computation (Search for Journal in Brave)

Full work available at URL: http://ir.lib.hiroshima-u.ac.jp/files/public/3/33875/20141016200227293372/Morita_RC2012.pdf

zbMATH Keywords

reversible computingreversible Turing machinemulti-head finite automatongarbage-less computation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (7)

Reversible Limited Automata ⋮ State complexity of transforming graph-walking automata to halting, returning and reversible ⋮ Minimal Reversible Deterministic Finite Automata ⋮ Reversibility of computations in graph-walking automata ⋮ An instruction set for reversible Turing machines ⋮ On the power of two-way multihead quantum finite automata ⋮ Language Recognition by Reversible Partitioned Cellular Automata

Cites Work

• Complexity of multi-head finite automata: origins and directions
• Halting space-bounded computations
• Reversible space equals deterministic space
• Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space
• Two-Way Reversible Multi-Head Finite Automata
• Logical Reversibility of Computation

This page was built for publication: A Deterministic Two-Way Multi-head Finite Automaton Can Be Converted into a Reversible One with the Same Number of Heads