Reversible multi-head finite automata characterize reversible logarithmic space

DOI10.1007/978-3-642-28332-1_9zbMATH Open1351.68132OpenAlexW1808022612MaRDI QIDQ2890183FDOQ2890183

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

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

Mathematics Subject Classification ID

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

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)