Reversal Hierarchies for Small 2DFAs

DOI10.1007/978-3-642-32589-2_49zbMATH Open1365.68306OpenAlexW138400891WikidataQ61677511 ScholiaQ61677511MaRDI QIDQ2912754FDOQ2912754

Authors Giovanni Pighizzini, Christos Kapoutsis 

Publication date 25 September 2012

Published in Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32589-2_49

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 7456055
• Reversible shrinking two-pushdown automata
• Reversible shrinking two-pushdown automata
• A logical characterization of small 2NFAs
• A logical characterization of small 2NFAs
• Reversal complexity revisited
• A hierarchy of fast reversible Turing machines
• Reversal Complexity Classes for Alternating Turing Machines
• Two-way reversible multi-head finite automata
• Concise representations of reversible automata

Cited In (2)

• Nondeterminism is essential in small 2FAs with few reversals
• Nondeterminism is essential in small two-way finite automata with few reversals

This page was built for publication: Reversal Hierarchies for Small 2DFAs

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