Kévin Perrot | DeepAI

DeepAI AI Chat

Featured Co-authors

Guillaume Theyssier
15 publications
Enrico Formenti
12 publications
Camille Noûs
12 publications
Sylvain Sené
11 publications
Adrien Richard
10 publications
Florian Bridoux
9 publications
Christophe Crespelle
6 publications
Eric Remila
5 publications
Thi Ha Duong Phan
4 publications
Pacôme Perrotin
4 publications
Amélia Durbec
4 publications

∙ 04/19/2023

On countings and enumerations of block-parallel automata networks

When we focus on finite dynamical systems from both the computability/co...

0 Kévin Perrot, et al. ∙

∙ 02/09/2023

Hardness of monadic second-order formulae over succinct graphs

Our main result is a succinct counterpoint to Courcelle's meta-theorem a...

0 Guilhem Gamard, et al. ∙

∙ 01/05/2023

Interaction graphs of isomorphic automata networks I: complete digraph and minimum in-degree

An automata network with n components over a finite alphabet Q of size q...

0 Florian Bridoux, et al. ∙

∙ 01/22/2021

Rikudo is NP-complete

Rikudo is a number-placement puzzle, where the player is asked to comple...

0 Viet-Ha Nguyen, et al. ∙

∙ 12/04/2020

Complexity of fixed point counting problems in Boolean Networks

A Boolean network (BN) with n components is a discrete dynamical system ...

0 Florian Bridoux, et al. ∙

∙ 05/29/2020

Optimising attractor computation in Boolean automata networks

This paper details a method for optimising the size of Boolean automata ...

0 Kévin Perrot, et al. ∙

∙ 04/05/2020

#P-completeness of counting update digraphs, cacti, and a series-parallel decomposition method

Automata networks are a very general model of interacting entities, with...

0 Camille Noûs, et al. ∙

∙ 01/21/2020

Complexity of limit-cycle problems in Boolean networks

Boolean networks are a general model of interacting entities, with appli...

0 Florian Bridoux, et al. ∙

∙ 10/16/2019

On the complexity of acyclic modules in automata networks

Modules were introduced as an extension of Boolean automata networks. Th...

0 Kévin Perrot, et al. ∙

∙ 09/26/2019

How hard is it to predict sandpiles on lattices? A survey

Since their introduction in the 80s, sandpile models have raised interes...

0 Kévin Perrot, et al. ∙

∙ 09/07/2019

On the complexity of counting feedback arc sets

In this note we study the computational complexity of feedback arc set c...

0 Kévin Perrot, et al. ∙

∙ 09/06/2019

NP-completeness of the game Kingdomino

Kingdomino is a board game designed by Bruno Cathala and edited by Blue ...

0 Viet-Ha Nguyen, et al. ∙

∙ 03/14/2018

Computational complexity of the avalanche problem on one dimensional Kadanoff sandpiles

In this paper we prove that the general avalanche problem AP is in NC, f...

0 Enrico Formenti, et al. ∙

∙ 03/14/2018

Linearity is Strictly More Powerful than Contiguity for Encoding Graphs

Linearity and contiguity are two parameters devoted to graph encoding. L...

0 Christophe Crespelle, et al. ∙

∙ 02/28/2018

A framework for (de)composing with Boolean automata networks

Boolean automata networks (BANs) are a generalisation of Boolean cellula...

0 Kévin Perrot, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world