A Random NP-complete problem for inversion of 2D cellular automata
From MaRDI portal
Publication:672376
DOI10.1016/0304-3975(94)00293-RzbMATH Open0873.68140OpenAlexW1980104174MaRDI QIDQ672376FDOQ672376
Authors: Bruno Durand 
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)00293-r
Recommendations
Cites Work
- Reversibility and surjectivity problems of cellular automata
- Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
- The undecidability of the domino problem
- Tesselations with local transformations
- Title not available (Why is that?)
- Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
- Undecidability and nonperiodicity for tilings of the plane
- Average case completeness
- Average Case Complete Problems
- Title not available (Why is that?)
- Reversibility of 2D cellular automata is undecidable
- Invertible cellular automata: A review
- Inversion of 2D cellular automata: Some complexity results
- The surjectivity problem for 2D cellular automata
- Randomizing Reductions of Search Problems
- Title not available (Why is that?)
- Matrix Transformation Is Complete for the Average Case
- The NP-completeness column: An ongoing guide
Cited In (6)
- Title not available (Why is that?)
- Complexity of inferring local transition functions of discrete dynamical systems
- On the complexity of deadlock detection in families of planar nets
- Inferring local transition functions of discrete dynamical systems from observations of system behavior
- Tilings: recursivity and regularity
- A random NP-complete problem for inversion of 2D cellular automata
This page was built for publication: A Random NP-complete problem for inversion of 2D cellular automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672376)
