On the complexity of deadlock detection in families of planar nets
From MaRDI portal
Publication:1285587
DOI10.1016/S0304-3975(97)00185-0zbMath0913.68082MaRDI QIDQ1285587
Bruno Durand, Anne-Cécile Fabret
Publication date: 28 April 1999
Published in: Theoretical Computer Science (Search for Journal in Brave)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- A Random NP-complete problem for inversion of 2D cellular automata
- Average case completeness
- A linear speed-up theorem for cellular automata
- Simulations between cellular automata on Cayley graphs
- Undecidability and nonperiodicity for tilings of the plane
- Randomizing Reductions of Search Problems
- Average Case Complete Problems
- Matrix Transformation Is Complete for the Average Case
- On the undecidability of deadlock detection in families of nets
- The undecidability of the domino problem