Reversible multi-head finite automata characterize reversible logarithmic space

DOI10.1007/978-3-642-28332-1_9MaRDI QIDQ2890183zbMATH OpenOpenAlexFDO

Authors Holger Bock Axelsen

Publication date 8 June 2012

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-28332-1_9

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Two-way reversible multi-head finite automata
• One-way reversible multi-head finite automata
• One-way reversible multi-head finite automata
• A deterministic two-way multi-head finite automaton can be converted into a reversible one with the same number of heads
• Reversible nondeterministic finite automata

Cited in

(11)

• Reversibility of computations in graph-walking automata
• One-way reversible multi-head finite automata
• When input-driven pushdown automata meet reversiblity
• Reversible limited automata
• Aspects of reversibility for classical automata
• Reversible parallel communicating finite automata systems
• Two-way reversible multi-head finite automata
• One-way reversible multi-head finite automata
• A deterministic two-way multi-head finite automaton can be converted into a reversible one with the same number of heads
• Reversible and irreversible computations of deterministic finite-state devices
• Minimal reversible deterministic finite automata

This page was built for publication: Reversible multi-head finite automata characterize reversible logarithmic space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2890183)