6 citations · 10 across the 9 of their papers we have counts for
12 papers · 1 filter
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…
#P-completeness of counting update digraphs, cacti, and a series-parallel decomposition method
Camille Noûs, Kévin Perrot, Sylvain Sené +1
Automata networks are a very general model of interacting entities, with applications to biological phenomena such as gene regulation. In many contexts, the order in which entities…
Complexity of limit-cycle problems in Boolean networks
Florian Bridoux, Caroline Gaze-Maillot, Kévin Perrot +1
Boolean networks are a general model of interacting entities, with applications to biological phenomena such as gene regulation. Attractors play a central role, and the schedule of…
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…
How hard is it to predict sandpiles on lattices? A survey
Kévin Perrot, Enrico Formenti
Since their introduction in the 80s, sandpile models have raised interest for their simple definition and their surprising dynamical properties. In this survey we focus on the comp…