When input-driven pushdown automata meet reversiblity

DOI10.1051/ita/2016016zbMath1362.68149OpenAlexW2519069132MaRDI QIDQ2969982

Martin Kutrib, Andreas Malcher, Matthias Wendlandt

Publication date: 24 March 2017

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1051/ita/2016016

zbMATH Keywords

formal languagesclosure propertiesreversible computationinput-driven pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Reversible parallel communicating finite automata systems ⋮ Boosting Reversible Pushdown and Queue Machines by Preprocessing

Cites Work

• Unnamed Item
• Unnamed Item
• Reversible simulation of one-dimensional irreversible cellular automata
• Real-time reversible iterative arrays
• Reversible computing and cellular automata -- a survey
• Fast reversible language recognition using cellular automata
• Reversible space equals deterministic space
• Reversible pushdown automata
• Operator precedence and the visibly pushdown property
• Nondeterministic state complexity of nested word automata
• Operational state complexity of nested word automata
• Deterministic input-driven queue automata: finite turns, decidability, and closure properties
• Reversible Multi-head Finite Automata Characterize Reversible Logarithmic Space
• Input-Driven Stack Automata
• Aspects of Reversibility for Classical Automata
• Tinput-Driven Pushdown Automata
• A Simple and Efficient Universal Reversible Turing Machine
• State Complexity of Operations on Input-Driven Pushdown Automata
• Two-Way Reversible Multi-Head Finite Automata
• WHEN CHURCH-ROSSER BECOMES CONTEXT FREE
• Adding nesting structure to words
• One-Way Reversible Multi-head Finite Automata
• Minimizing Variants of Visibly Pushdown Automata
• Visibly pushdown languages
• Irreversibility and Heat Generation in the Computing Process
• The tree width of auxiliary storage
• Developments in Language Theory
• Real-Time Reversible One-Way Cellular Automata
• Logical Reversibility of Computation

This page was built for publication: When input-driven pushdown automata meet reversiblity