Reversible limited automata

DOI10.1007/978-3-319-23111-2_8MaRDI QIDQ2945882zbMATH OpenOpenAlexFDO

Authors Martin Kutrib, Matthias Wendlandt

Publication date 15 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-23111-2_8

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Reversible limited automata
• Limited automata and context-free languages
• Limited automata: properties, complexity and variants
• Strongly Limited Automata
• Reversible pushdown automata

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• A deterministic two-way multi-head finite automaton can be converted into a reversible one with the same number of heads
• Aspects of reversibility for classical automata
• Complexities for Generalized Models of Self-Assembly
• Computational Complexity of One-Tape Turing Machine Computations
• Degrees of reversibility for DFA and DPDA
• Fast reversible language recognition using cellular automata
• Inference of Reversible Languages
• Limited automata and context-free languages
• Limited automata and regular languages
• Logical Reversibility of Computation
• Minimal reversible deterministic finite automata
• Non-Turing computations via Malament--Hogarth space-times
• On simulation cost of unary limited automata
• On stateless two-pushdown automata and restarting automata
• One-tape, off-line Turing machine computations
• One-way reversible multi-head finite automata
• Pisot substitutions and Rauzy fractals
• Quantum mechanical ground state of hydrogen obtained from classical electrodynamics
• Reversible computing and cellular automata -- a survey
• Reversible multi-head finite automata characterize reversible logarithmic space
• Reversible pushdown automata
• Reversible queue automata
• Reversible space equals deterministic space
• The nature of explosive percolation phase transition
• Weight-reducing Hennie machines and their descriptional complexity
• When Church-Rosser becomes context free

Cited in

(11)

• Reversible Ordered Restarting Automata
• Join inverse categories as models of reversible recursion
• Minimal and Reduced Reversible Automata
• Reversible effects as inverse arrows
• Deterministic stack transducers
• A lower bound for reversible automata
• Behavioral strengths and weaknesses of various models of limited automata
• Deterministic stack transducers
• Join inverse categories and reversible recursion
• Reversible and irreversible computations of deterministic finite-state devices
• Reversible limited automata

This page was built for publication: Reversible limited automata

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