4 papers
On K{\r u}rka's dichotomy for cellular automata on groups
Jade Angela Hope Audouard, Guillaume Theyssier
This paper is about topological dynamics of cellular automata on finitely generated groups. We tackle the problem of determining for which group sensitivity to initial conditions i…
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…
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'…