Reversible shrinking two-pushdown automata

MaRDI QIDQ5867516zbMATH OpenFDO

Authors Holger Bock Axelsen, Martin Kutrib, Andreas Malcher

Publication date 14 September 2022

Full work available at URL http://www.jalc.de/issues/2022/issue_27_1-3/jalc-2022-047-077.php

zbMATH Keywords

reversible computingunconventional models of computationChurch-Rosser languagesshrinking two-pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Reversible shrinking two-pushdown automata
• Fundamentals of Computation Theory
• Reversible pushdown automata
• Reversible pushdown automata
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• A hierarchy of fast reversible Turing machines
• Church-Rosser Thue systems and formal languages
• Growing context-sensitive languages and Church-Rosser languages
• One-way reversible multi-head finite automata
• Reversible pushdown automata
• Reversible shrinking two-pushdown automata
• Reversible space equals deterministic space
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• Two-way reversible multi-head finite automata
• Universality of a reversible two-counter machine
• What do reversible programs compute?

Cited in

(1)

• Reversal Hierarchies for Small 2DFAs

This page was built for publication: Reversible shrinking two-pushdown automata

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