3 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.FL2024
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…
cs.FL2023
An Analysis of On-the-fly Determinization of Finite-state Automata
Ivan Baburin, Ryan Cotterell
In this paper we establish an abstraction of on-the-fly determinization of finite-state automata using transition monoids and demonstrate how it can be applied to bound the asympto…