DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2025.11

Universality Frontier for Asynchronous Cellular Automata

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

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract

In this work, we investigate computational aspects of asynchronous cellular automata (ACAs), a modification of cellular automata in which cells update independently, following an asynchronous update schedule. We introduce flip automata networks (FANs), a simple modification of automata networks that remain robust under any asynchronous updating order. By using FANs as a middleman, we show that asynchronous automata can efficiently simulate their synchronous counterparts with a linear memory overhead, which improves upon the previously established quadratic bound. Additionally, we address the universality gap for (a)synchronous cellular automata-the boundary separating universal and non-universal automata, which is still not fully understood. We tighten this boundary by proving that all one-way asynchronous automata lack universal computational power. Conversely, we establish the existence of a universal asynchronous 6-state first-neighbor automaton in one dimension and a 3-state von Neumann automaton in two dimensions, which represent the smallest known universal constructions to date.

Cite as

Ivan Baburin, Matthew Cook, Florian Grötschla, Andreas Plesner, and Roger Wattenhofer. Universality Frontier for Asynchronous Cellular Automata. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{baburin_et_al:LIPIcs.MFCS.2025.11,
  author =	{Baburin, Ivan and Cook, Matthew and Gr\"{o}tschla, Florian and Plesner, Andreas and Wattenhofer, Roger},
  title =	{{Universality Frontier for Asynchronous Cellular Automata}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.11},
  URN =		{urn:nbn:de:0030-drops-241182},
  doi =		{10.4230/LIPIcs.MFCS.2025.11},
  annote =	{Keywords: Universality, Asynchronous Cellular Automata, Automata Networks}
}

Search Results

Documents authored by Grötschla, Florian

Universality Frontier for Asynchronous Cellular Automata

Abstract

Cite as

Thanks for your feedback!

Could not send message