The reachability problem for finite cellular automata

DOI10.1016/0020-0190(94)00169-YMaRDI QIDQ674292zbMATH OpenFDO

Authors Russell Impagliazzo, Andrea Clementi

Publication date 28 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

Computational complexityCellular automataInteractive proofsReachability problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80)

Recommendations

• Reachability problem in non-uniform cellular automata
• On the computational complexity of finite cellular automata
• Reversibility and surjectivity problems of cellular automata
• scientific article; zbMATH DE number 17562

Cites work

• scientific article; zbMATH DE number 4211534 (Why is no real title available?)
• scientific article; zbMATH DE number 4058875 (Why is no real title available?)
• scientific article; zbMATH DE number 4074492 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• Algebraic properties of cellular automata
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Computation theory of cellular automata
• Does co-NP have short interactive proofs ?
• Exact results for deterministic cellular automata with additive rules
• Invertible cellular automata: A review
• The Knowledge Complexity of Interactive Proof Systems
• The complexity of reversible cellular automata

Cited in

(3)

• Reachability problem in non-uniform cellular automata
• A study of chaos in cellular automata
• On the computational complexity of finite cellular automata

This page was built for publication: The reachability problem for finite cellular automata

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