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

DOI10.3390/A4010001MaRDI QIDQ1736474zbMATH OpenOpenAlexFDO

Authors Tatsuie Tsukiji, Takeo Hagiwara

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

cellular automatacomputational complexityLangton's antLorentz lattice gasPSPACE-hardness

Mathematics Subject Classification ID

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

Recommendations

• Complexity of Langton's ant
• scientific article; zbMATH DE number 1689044
• Langton's flies
• Nontrivial turmites are Turing-universal
• Intractable problems in reversible cellular automata

Cites work

• Complexity of Langton's ant
• Diffusion in Lorentz lattice gas cellular automata: the honeycomb and quasi-lattices compared with the square and triangular lattices
• scientific article; zbMATH DE number 426410 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1178990 (Why is no real title available?)
• Recurrence properties of Lorentz lattice gas cellular automata
• Rotators, periodicity, and absence of diffusion in cyclic cellular automata

Cited in

(5)

• Complexity of Langton's ant
• PSPACE-completeness of reversible deterministic systems
• scientific article; zbMATH DE number 1689044 (Why is no real title available?)
• PSPACE-completeness of reversible deterministic systems
• Agent motion planning as block asynchronous cellular automata: pushing, pulling, suplexing, and more

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1736474)