Reversible pushdown automata

DOI10.1016/j.jcss.2011.12.004zbMath1250.68166MaRDI QIDQ1757838

Martin Kutrib, Andreas Malcher

Publication date: 6 November 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.12.004

zbMATH Keywords

formal languages; closure properties; pushdown automata; decidability questions; reversible computations

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

The Computing Power of Determinism and Reversibility in Chemical Reaction Automata, Queue Automata: Foundations and Developments, Diving into the queue, Real-Time Reversible One-Way Cellular Automata, Unnamed Item, Reversible pushdown transducers, How does adiabatic quantum computation fit into quantum automata theory?, Transducing reversibly with finite state machines, Transducing reversibly with finite state machines, Boosting Reversible Pushdown and Queue Machines by Preprocessing, Towards a taxonomy for reversible computation approaches, Reversible Top-Down Syntax Analysis, Reversible top-down syntax analysis, Theory of reaction automata: a survey, Reversible parallel communicating finite automata systems, An instruction set for reversible Turing machines, Reversibility for stateless ordered RRWW-automata, Detecting useless transitions in pushdown automata, Reversibility of computations in graph-walking automata, On entropy and reversibility of pushdown dynamical systems, One-way reversible multi-head finite automata, Reversible Watson-Crick automata, Reversible Ordered Restarting Automata, Aspects of Reversibility for Classical Automata, Reversible Limited Automata, Reversible and Irreversible Computations of Deterministic Finite-State Devices, When input-driven pushdown automata meet reversiblity, Boosting Reversible Pushdown Machines by Preprocessing, One-Way Reversible Multi-head Finite Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Real-time reversible iterative arrays
• Reversible computing and cellular automata -- a survey
• Fast reversible language recognition using cellular automata
• On the efficient construction of quasi-reversible automata for reversible languages
• On locally reversible languages
• Complete problems for deterministic polynomial time
• Learning approximately regular languages with reversible languages
• Properties of quantum languages
• Identification of birfsa languages.
• Optimization of LR(k) parsers
• Reversing algebraic process calculi
• Reversible Flowchart Languages and the Structured Reversible Program Theorem
• Irreversibility and Heat Generation in the Computing Process
• Inference of Reversible Languages
• Deterministic context free languages
• Logical Reversibility of Computation