Showing 2024Show all
3 papers · 1 filter
cs.DM2024
A sequential solution to the density classification task using an intermediate alphabet
Pacôme Perrotin, Pedro Paulo Balbi, Eurico Ruivo
We present a sequential cellular automaton of radius 2 1 as a solution to the density classification task that makes use of an intermediate alphabet, and converges to a clean fixed…
cs.FL2024
Subshifts defined by nondeterministic and alternating plane-walking automata
Benjamin Hellouin de Menibus, Pacôme Perrotin
Plane-walking automata were introduced by Salo & Törma to recognise languages of two-dimensional infinite words (subshifts), the counterpart of -way finite automata for two-dime…
cs.DM2024
Fast solutions to k-parity and k-synchronisation using parallel automata networks
Pacôme Perrotin, Eurico Ruivo, Pedro Paulo Balbi
We present a family of automata networks that solve the k-parity problem when run in parallel. These solutions are constructed by connecting cliques in a non-cyclical fashion. The…