The reachability problem for finite cellular automata

DOI10.1016/0020-0190(94)00169-YzbMATH Open0875.68660MaRDI QIDQ674292FDOQ674292

Authors: Russell Impagliazzo, Andrea Clementi 

Publication date: 28 February 1997

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

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

zbMATH Keywords

Computational complexityCellular automataInteractive proofsReachability problems

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• The complexity of reversible cellular automata
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Does co-NP have short interactive proofs ?
• The Knowledge Complexity of Interactive Proof Systems
• Computation theory of cellular automata
• Title not available (Why is that?)
• Algebraic properties of cellular automata
• Invertible cellular automata: A review
• Title not available (Why is that?)
• Title not available (Why is that?)
• Exact results for deterministic cellular automata with additive rules

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)