Universality frontier for asynchronous cellular automata

DOI10.4230/LIPICS.MFCS.2025.11MaRDI QIDQ7310169zbMATH OpenFDO

Authors Ivan Baburin, Matthew Cook, Florian Grötschla, Andreas Plesner, Roger Wattenhofer

Publication date 5 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2025.11

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• (A-)synchronous (non)-deterministic cell spaces simulating each other
• A guided tour of asynchronous cellular automata
• Asynchronous game of life
• Delay-insensitive computation in asynchronous cellular automata
• Effect of random fluctuations on minimizing the complexity of universal asynchronous cellular automata
• Four states are enough!
• scientific article; zbMATH DE number 1818513 (Why is no real title available?)
• scientific article; zbMATH DE number 4195207 (Why is no real title available?)
• scientific article; zbMATH DE number 45557 (Why is no real title available?)
• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• scientific article; zbMATH DE number 1241089 (Why is no real title available?)
• scientific article; zbMATH DE number 1962850 (Why is no real title available?)
• scientific article; zbMATH DE number 2113945 (Why is no real title available?)
• scientific article; zbMATH DE number 5252388 (Why is no real title available?)
• On computable numbers, with an application to the Entscheidungsproblem.
• The Complexity of Small Universal Turing Machines: A Survey
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Theory of reversible computing
• Towards intrinsically universal asynchronous CA
• Universal delay-insensitive systems with buffering lines
• Universality in elementary cellular automata

This page was built for publication: Universality frontier for asynchronous cellular automata

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