Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard

DOI10.3390/a4010001zbMath1461.68126OpenAlexW2154560238MaRDI QIDQ1736474

Tatsuie Tsukiji, Takeo Hagiwara

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a4010001

zbMATH Keywords

computational complexitycellular automataLangton's antLorentz lattice gasPSPACE-hardness

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

PSPACE-completeness of reversible deterministic systems

Cites Work

• Recurrence properties of Lorentz lattice gas cellular automata
• Rotators, periodicity, and absence of diffusion in cyclic cellular automata
• Complexity of Langton's ant
• Diffusion in Lorentz lattice gas cellular automata: the honeycomb and quasi-lattices compared with the square and triangular lattices
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard