The reachability problem for finite cellular automata

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

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)

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)

• A Study of Chaos in Cellular Automata
• Reachability problem in non-uniform cellular automata
• On the computational complexity of finite cellular automata

   Recommendations

• Reachability problem in non-uniform cellular automata 👍 👎
• On the computational complexity of finite cellular automata 👍 👎
• Reversibility and surjectivity problems of cellular automata 👍 👎
• Title not available (Why is that?) 👍 👎

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)