2 papers
cs.FL2025
Universality Frontier for Asynchronous Cellular Automata
Ivan Baburin, Matthew Cook, Florian Grötschla +2
In this work, we investigate the computational aspects of asynchronous cellular automata (ACAs), a modification of cellular automata in which cells update independently, following…
cs.FL2025
A Close Analysis of the Subset Construction
Ivan Baburin, Ryan Cotterell
Given a nondeterministic finite-state automaton (NFA), we aim to estimate the size of an equivalent deterministic finite-state automaton (DFA). We demonstrate that computing the st…