Reversible Ordered Restarting Automata

DOI10.1007/978-3-319-20860-2_4MaRDI QIDQ2822491zbMATH OpenOpenAlexFDO

Authors Friedrich Otto, Matthias Wendlandt, Kent Kwee

Publication date 30 September 2016

Published in Reversible Computation (Search for Journal in Brave)

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

zbMATH Keywords

descriptional complexityrestarting automatonreversibility

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Formal languages and automata (68Q45)

Recommendations

• Reversible pushdown automata
• Reversible pushdown automata
• Reversible limited automata
• Reversible limited automata
• Reversible nondeterministic finite automata
• Reversibility for stateless ordered RRWW-automata
• Deterministic ordered restarting automata that compute functions
• On deterministic ordered restart-delete automata
• On deterministic ordered restart-delete automata

Cites work

• Finite automata and unary languages
• Logical Reversibility of Computation
• On some decision problems for stateless deterministic ordered restarting automata
• On the descriptional complexity of deterministic ordered restarting automata
• On the maximal order in S_n and S*_n
• Ordered restarting automata for picture languages
• Restarting automata
• Reversible pushdown automata
• Weight-reducing Hennie machines and their descriptional complexity

Cited in

(12)

• On the descriptional complexity of stateless deterministic ordered restarting automata
• Reversibility for stateless ordered RRWW-automata
• A pumping lemma for ordered restarting automata
• On the effects of nondeterminism on ordered restarting automata
• Power of S-kR-RRWW-automata
• Nondeterministic ordered restarting automata
• Deterministic ordered restarting automata that compute functions
• On Stateless Deterministic Restarting Automata
• On the descriptional complexity of deterministic ordered restarting automata
• On some decision problems for stateless deterministic ordered restarting automata
• On stateless deterministic restarting automata
• Succinct description of regular languages by weak restarting automata

This page was built for publication: Reversible Ordered Restarting Automata

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