6 citations · 13 across the 21 of their papers we have counts for
3 papers · 1 filter
On countings and enumerations of block-parallel automata networks
Kévin Perrot, Sylvain Sené, Léah Tapin
When we focus on finite dynamical systems from both the computability/complexity and the modelling standpoints, automata networks seem to be a particularly appropriate mathematical…
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…
Interaction graphs of isomorphic automata networks I: complete digraph and minimum in-degree
Florian Bridoux, Kévin Perrot, Aymeric Picard Marchetto +1
An automata network with components over a finite alphabet of size is a discrete dynamical system described by the successive iterations of a function . I…