6 citations · 13 across the 21 of their papers we have counts for
29 papers
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…
Rikudo is NP-complete
Viet-Ha Nguyen, Kévin Perrot
Rikudo is a number-placement puzzle, where the player is asked to complete a Hamiltonian path on a hexagonal grid, given some clues (numbers already placed and edges of the path).…
Freezing sandpiles and Boolean threshold networks: equivalence and complexity
Eric Goles, Pedro Montealegre Kévin Perrot
The NC versus P-hard classification of the prediction problem for sandpiles on the two dimensional grid with von Neumann neighborhood is a famous open problem. In this paper we mak…
Complexity of fixed point counting problems in Boolean Networks
Florian Bridoux, Amélia Durbec, Kévin Perrot +1
A Boolean network (BN) with components is a discrete dynamical system described by the successive iterations of a function . This model finds applica…