Reversible pushdown automata

DOI10.1016/j.jcss.2011.12.004zbMath1250.68166OpenAlexW2023439061MaRDI 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 languagesclosure propertiespushdown automatadecidability questionsreversible computations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

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

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