Fast reversible language recognition using cellular automata
From MaRDI portal
Publication:948083
DOI10.1016/j.ic.2008.03.015zbMath1154.68082OpenAlexW1981094023MaRDI QIDQ948083
Andreas Malcher, Martin Kutrib
Publication date: 8 October 2008
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2008.03.015
cellular automataclosure propertieslanguage recognitiondecidability questionsreal-time reversible computations
Related Items (15)
One-way reversible multi-head finite automata ⋮ Reversible top-down syntax analysis ⋮ One-Way Reversible Multi-head Finite Automata ⋮ Real-time reversible iterative arrays ⋮ Aspects of Reversibility for Classical Automata ⋮ Reversible Limited Automata ⋮ Reversible and Irreversible Computations of Deterministic Finite-State Devices ⋮ Queue Automata: Foundations and Developments ⋮ Reversible Top-Down Syntax Analysis ⋮ When input-driven pushdown automata meet reversiblity ⋮ Cellular automata with sparse communication ⋮ Reversible pushdown automata ⋮ Cellular Automata with Sparse Communication ⋮ Real-Time Reversible One-Way Cellular Automata ⋮ Language Recognition by Reversible Partitioned Cellular Automata
Cites Work
- Unnamed Item
- Firing squad synchronization problem in reversible cellular automata
- Reversible simulation of one-dimensional irreversible cellular automata
- Invertible cellular automata: A review
- Computation-universality of one-dimensional one-way reversible cellular automata
- Computation and construction universality of reversible cellular automata
- Reversibility and surjectivity problems of cellular automata
- Theory of cellular automata: a survey
- Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
- Inference of Reversible Languages
- Logical Reversibility of Computation
- Automata, Languages and Programming
This page was built for publication: Fast reversible language recognition using cellular automata
