Reversible pushdown automata
From MaRDI portal
Publication:1757838
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
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
