The reachability problem for finite cellular automata

DOI10.1016/0020-0190(94)00169-YzbMath0875.68660MaRDI QIDQ674292

Russell Impagliazzo, Andrea E. F. Clementi

Publication date: 28 February 1997

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

zbMATH Keywords

Cellular automataComputational complexityInteractive proofsReachability problems

Mathematics Subject Classification ID

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

Related Items (2)

A Study of Chaos in Cellular Automata ⋮ Reachability problem in non-uniform cellular automata

Cites Work

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

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