Intractable problems in reversible cellular automata

DOI10.1007/BF00669293MaRDI QIDQ1104752zbMATH OpenFDO

Authors Farrokh Vatan

Publication date 1988

Published in International Journal of Theoretical Physics (Search for Journal in Brave)

zbMATH Keywords

PSPACE-completereversible cellular automatonbilliard balldistribution of gas molecules

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80) Compressible fluids and gas dynamics (76N99)

Recommendations

• Reversibility and surjectivity problems of cellular automata
• scientific article; zbMATH DE number 4058875
• Reversibility of 2D cellular automata is undecidable
• scientific article; zbMATH DE number 1775519
• On the structure of the set of reversible cellular automata

Cites work

• scientific article; zbMATH DE number 3898247 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3692653 (Why is no real title available?)
• scientific article; zbMATH DE number 3761989 (Why is no real title available?)
• A Universal Four-State Cellular Computer
• Computation and construction universality of reversible cellular automata
• Conservative logic
• Irreversibility and Heat Generation in the Computing Process
• Logical Reversibility of Computation
• On reversibility in cellular automata
• Tesselations with local transformations

Cited in

(3)

• Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard
• scientific article; zbMATH DE number 1775519 (Why is no real title available?)
• A random NP-complete problem for inversion of 2D cellular automata

This page was built for publication: Intractable problems in reversible cellular automata

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