Fast reversible language recognition using cellular automata

DOI10.1016/J.IC.2008.03.015MaRDI QIDQ948083zbMATH OpenOpenAlexFDO

Authors Martin Kutrib, Andreas Malcher

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 automataclosure propertieslanguage recognitiondecidability questionsreal-time reversible computations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80)

Recommendations

• Real-time reversible one-way cellular automata
• Fast one-way cellular automata with reversible Mealy cells
• Language recognition by reversible partitioned cellular automata and iterative arrays
• Fast parallel language recognition by cellular automata
• Language recognition by reversible partitioned cellular automata

Cites work

• scientific article; zbMATH DE number 1836417 (Why is no real title available?)
• Automata, Languages and Programming
• Computation and construction universality of reversible cellular automata
• Computation-universality of one-dimensional one-way reversible cellular automata
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• Firing squad synchronization problem in reversible cellular automata
• Inference of Reversible Languages
• Invertible cellular automata: A review
• Logical Reversibility of Computation
• Reversibility and surjectivity problems of cellular automata
• Reversible simulation of one-dimensional irreversible cellular automata
• Theory of cellular automata: a survey

Cited in

(25)

• Languages not recognizable in real time by one-dimensional cellular automata
• Reversible top-down syntax analysis
• Real-time reversible iterative arrays
• One-way reversible multi-head finite automata
• Language recognition by reversible partitioned cellular automata
• Language recognition by reversible partitioned cellular automata and iterative arrays
• When input-driven pushdown automata meet reversiblity
• Reversible limited automata
• Cellular Automata with Sparse Communication
• Reversible pushdown automata
• Aspects of reversibility for classical automata
• Real-time reversible one-way cellular automata
• scientific article; zbMATH DE number 2068878 (Why is no real title available?)
• Reversible Top-Down Syntax Analysis
• String generation by cellular automata
• Cellular automata with sparse communication
• Fast parallel language recognition by cellular automata
• scientific article; zbMATH DE number 769370 (Why is no real title available?)
• Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata
• scientific article; zbMATH DE number 572172 (Why is no real title available?)
• scientific article; zbMATH DE number 1759473 (Why is no real title available?)
• One-way reversible multi-head finite automata
• Fast one-way cellular automata with reversible Mealy cells
• Queue Automata: Foundations and Developments
• Reversible and irreversible computations of deterministic finite-state devices

This page was built for publication: Fast reversible language recognition using cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q948083)