Fast reversible language recognition using cellular automata

DOI10.1016/j.ic.2008.03.015zbMath1154.68082MaRDI 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

zbMATH Keywords

cellular automata; closure properties; language recognition; decidability questions; real-time reversible computations

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q80: Cellular automata (computational aspects)

Related Items

Queue Automata: Foundations and Developments, Real-Time Reversible One-Way Cellular Automata, Language Recognition by Reversible Partitioned Cellular Automata, Real-time reversible iterative arrays, Reversible pushdown automata, Cellular automata with sparse communication, One-way reversible multi-head finite 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, One-Way Reversible Multi-head Finite Automata, Cellular Automata with Sparse Communication

Cites Work

• 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
• Unnamed Item