16 citations · 46 across the 31 of their papers we have counts for
13 papers · 1 filter
On the Dynamics of Bounded-Degree Automata Networks
Julio Aracena, Florian Bridoux, Maximilien Gadouleau +4
Automata networks can be seen as bare finite dynamical systems, but their growing theory has shown the importance of the underlying communication graph of such networks. This paper…
On the complexity of freezing automata networks of bounded pathwidth
Eric Goles, Pedro Montealegre, Martín Ríos-Wilson +1
An automata network is a graph of entities, each holding a state from a finite set and evolving according to a local update rule which depends only on its neighbors in the network'…
Hardness of monadic second-order formulae over succinct graphs
Guilhem Gamard, Aliénor Goubault-Larrecq, Pierre Guillon +3
Our main result is a succinct counterpoint to Courcelle's meta-theorem as follows: every cw-nontrivial monadic second-order (MSO) property is either NP-hard or coNP-hard over graph…
Intrinsic Simulations and Universality in Automata Networks
Martín Ríos-Wilson, Guillaume Theyssier
An automata network (AN) is a finite graph where each node holds a state from a finite alphabet and is equipped with a local map defining the evolution of the state of the node dep…
On Turedo Hierarchies and Intrinsic Universality
Samuel Nalin, Guillaume Theyssier
This paper is about turedos, which are Turing machine whose head can move in the plane (or in a higher-dimensional space) but only in a selfavoiding way, by putting marks (letters)…
The Mirage of Universality in Cellular Automata
Guillaume Theyssier
This note is a survey of examples and results about cellular automata with the purpose of recalling that there is no 'universal' way of being computationally universal. In particul…