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

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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)