7 papers
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…
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…
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…
Turning block-sequential automata networks into smaller parallel networks with isomorphic limit dynamics
Pacôme Perrotin, Sylvain Sené
We state an algorithm that, given an automata network and a block-sequential update schedule, produces an automata network of the same size or smaller with the same limit dynamics…
Optimising attractor computation in Boolean automata networks
Kévin Perrot, Pacôme Perrotin, Sylvain Sené
This paper details a method for optimising the size of Boolean automata networks in order to compute their attractors under the parallel update schedule. This method relies on the…
On the complexity of acyclic modules in automata networks
Kévin Perrot, Pacôme Perrotin, Sylvain Sené
Modules were introduced as an extension of Boolean automata networks. They have inputs which are used in the computation said modules perform, and can be used to wire modules with…
A framework for (de)composing with Boolean automata networks
Kévin Perrot, Pacôme Perrotin, Sylvain Sené
Boolean automata networks (BANs) are a generalisation of Boolean cellular automata. In such, any theorem describing the way BANs compute information is a strong tool that can be ap…