Kévin Perrot
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Kévin Perrot has a total of 26 co-authors. Here are the top co-authors by number of shared publications:
- Pablo Concha-Vega
LIS UMR 7020 Aix-Marseille Université Toulon CNRS Marseille France
5 shared publications - Eric Goles
Facultad de Ciencias y Tecnología Universidad Adolfo Ibáñez Santiago Chile
3 shared publications - Eurico L. P. Ruivo
Universidade Presbiteriana Mackenzie
3 shared publications - Pedro Montealegre
Facultad de Ingeniería y Ciencias, Universidad Adolfo Ibáñez, Santiago, Chile
3 shared publications - Aliénor Goubault-Larrecq
Aix Marseille Univ, CNRS, LIS
2 shared publications - Lucas Venturini
Université publique
2 shared publications
Latest Publications
- Open Access
- 6 January 2026
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 22, Is
Hardness of monadic second-order formulae over succinct graphs
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 graphs given by succinct representations. Succint representations are Boolean circuits computing the adjacency relation. Cw-nontrivial properties are those which have infinitely many models and infinitely many countermodels with bounded cliquewidth. Moreover, we explore what happens when the cw-nontriviality condition is dropped and show that, under a reasonable complexity assumption, the previous dichotomy fails, even for questions expressible in first-order logic.
- 6 January 2026
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 22, Is
Open AccessHardness of monadic second-order formulae over succinct graphs
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 graphs given by succinct representations. Succint representations are Boolean circuits computing the adjacency relation. Cw-nontrivial properties are those which have infinitely many models and infinitely many countermodels with bounded cliquewidth. Moreover, we explore what happens when the cw-nontriviality condition is dropped and show that, under a reasonable complexity assumption, the previous dichotomy fails, even for questions expressible in first-order logic.
- 1 October 2025
- Published by Springer Nature
- p. 205-220
Timed Prediction Problem for Sandpile Models
- Open Access
Complexity of the Freezing Majority Rule with L-shaped Neighborhoods
In this article we investigate the computational complexity of predicting two dimensional freezing majority cellular automata with states {-1, +1}, where the local interactions are based on an L-shaped neighborhood structure. In these automata, once a cell reaches state +1, it remains fixed in that state forever, while cells in state -1 update to the most represented state among their neighborhoods. We consider L-shaped neighborhoods, which mean that the vicinity of a given cell c consists in a subset of cells in the north and east of c.We focus on the prediction problem, a decision problem that involves determining the state of a given cell after a given number of time-steps. We prove that when restricted to the simplest L-shaped neighborhood, consisting of the central cell and its nearest north and east neighbors, the prediction problem belongs to NC, meaning it can be solved efficiently in parallel. We generalize this result for any L-shaped neighborhood of size two. On the other hand, for other L-shaped neighborhoods, the problem becomes P-complete, indicating that the problem might be inherently sequential.
Open AccessComplexity of the Freezing Majority Rule with L-shaped Neighborhoods
In this article we investigate the computational complexity of predicting two dimensional freezing majority cellular automata with states {-1, +1}, where the local interactions are based on an L-shaped neighborhood structure. In these automata, once a cell reaches state +1, it remains fixed in that state forever, while cells in state -1 update to the most represented state among their neighborhoods. We consider L-shaped neighborhoods, which mean that the vicinity of a given cell c consists in a subset of cells in the north and east of c.We focus on the prediction problem, a decision problem that involves determining the state of a given cell after a given number of time-steps. We prove that when restricted to the simplest L-shaped neighborhood, consisting of the central cell and its nearest north and east neighbors, the prediction problem belongs to NC, meaning it can be solved efficiently in parallel. We generalize this result for any L-shaped neighborhood of size two. On the other hand, for other L-shaped neighborhoods, the problem becomes P-complete, indicating that the problem might be inherently sequential.
- Open Access
Complexity of the Freezing Majority Rule with L-shaped Neighborhoods
In this article we investigate the computational complexity of predicting two dimensional freezing majority cellular automata with states $\{-1,+1\}$, where the local interactions are based on an L-shaped neighborhood structure. In these automata, once a cell reaches state $+1$, it remains fixed in that state forever, while cells in state $-1$ update to the most represented state among their neighborhoods. We consider L-shaped neighborhoods, which mean that the vicinity of a given cell $c$ consists in a subset of cells in the north and east of $c$. We focus on the prediction problem, a decision problem that involves determining the state of a given cell after a given number of time-steps. We prove that when restricted to the simplest L-shaped neighborhood, consisting of the central cell and its nearest north and east neighbors, the prediction problem belongs to $\mathsf{NC}$, meaning it can be solved efficiently in parallel. We generalize this result for any L-shaped neighborhood of size two. On the other hand, for other L-shaped neighborhoods, the problem becomes $\mathsf{P}$-complete, indicating that the problem might be inherently sequential.Open AccessComplexity of the Freezing Majority Rule with L-shaped Neighborhoods
In this article we investigate the computational complexity of predicting two dimensional freezing majority cellular automata with states $\{-1,+1\}$, where the local interactions are based on an L-shaped neighborhood structure. In these automata, once a cell reaches state $+1$, it remains fixed in that state forever, while cells in state $-1$ update to the most represented state among their neighborhoods. We consider L-shaped neighborhoods, which mean that the vicinity of a given cell $c$ consists in a subset of cells in the north and east of $c$. We focus on the prediction problem, a decision problem that involves determining the state of a given cell after a given number of time-steps. We prove that when restricted to the simplest L-shaped neighborhood, consisting of the central cell and its nearest north and east neighbors, the prediction problem belongs to $\mathsf{NC}$, meaning it can be solved efficiently in parallel. We generalize this result for any L-shaped neighborhood of size two. On the other hand, for other L-shaped neighborhoods, the problem becomes $\mathsf{P}$-complete, indicating that the problem might be inherently sequential. - Open Access
Timed Prediction Problem for Sandpile Models
We investigate the computational complexity of the timed prediction problem in two-dimensional sandpile models. This question refines the classical prediction problem, which asks whether a cell q will eventually become unstable after adding a grain at cell p from a given configuration. The prediction problem has been shown to be P-complete in several settings, including for subsets of the Moore neighborhood, but its complexity for the von Neumann neighborhood remains open. In a previous work, we provided a complete characterization of crossover gates (a key to the implementation of non-planar monotone circuits) for these small neighborhoods, leading to P-completeness proofs with only 4 and 5 neighbors among the eight adjancent cells. In this paper, we introduce the timed setting, where the goal is to determine whether cell q becomes unstable exactly at time t. We distinguish several cases: some neighborhoods support complete timed toolkits (including timed crossover gates) and exhibit P-completeness; others admit timed crossovers but suffer from synchronization issues; planar neighborhoods provably do not admit any timed crossover; and finally, for some remaining neighborhoods, we conjecture that no timed crossover is possible.
Open AccessTimed Prediction Problem for Sandpile Models
We investigate the computational complexity of the timed prediction problem in two-dimensional sandpile models. This question refines the classical prediction problem, which asks whether a cell q will eventually become unstable after adding a grain at cell p from a given configuration. The prediction problem has been shown to be P-complete in several settings, including for subsets of the Moore neighborhood, but its complexity for the von Neumann neighborhood remains open. In a previous work, we provided a complete characterization of crossover gates (a key to the implementation of non-planar monotone circuits) for these small neighborhoods, leading to P-completeness proofs with only 4 and 5 neighbors among the eight adjancent cells. In this paper, we introduce the timed setting, where the goal is to determine whether cell q becomes unstable exactly at time t. We distinguish several cases: some neighborhoods support complete timed toolkits (including timed crossover gates) and exhibit P-completeness; others admit timed crossovers but suffer from synchronization issues; planar neighborhoods provably do not admit any timed crossover; and finally, for some remaining neighborhoods, we conjecture that no timed crossover is possible.
- Open Access
Timed Prediction Problem for Sandpile Models
We investigate the computational complexity of the timed prediction problem in two-dimensional sandpile models. This question refines the classical prediction problem, which asks whether a cell q will eventually become unstable after adding a grain at cell p from a given configuration. The prediction problem has been shown to be P-complete in several settings, including for subsets of the Moore neighborhood, but its complexity for the von Neumann neighborhood remains open. In a previous work, we provided a complete characterization of crossover gates (a key to the implementation of non-planar monotone circuits) for these small neighborhoods, leading to P-completeness proofs with only 4 and 5 neighbors among the eight adjancent cells. In this paper, we introduce the timed setting, where the goal is to determine whether cell q becomes unstable exactly at time t. We distinguish several cases: some neighborhoods support complete timed toolkits (including timed crossover gates) and exhibit P-completeness; others admit timed crossovers but suffer from synchronization issues; planar neighborhoods provably do not admit any timed crossover; and finally, for some remaining neighborhoods, we conjecture that no timed crossover is possible.
Open AccessTimed Prediction Problem for Sandpile Models
We investigate the computational complexity of the timed prediction problem in two-dimensional sandpile models. This question refines the classical prediction problem, which asks whether a cell q will eventually become unstable after adding a grain at cell p from a given configuration. The prediction problem has been shown to be P-complete in several settings, including for subsets of the Moore neighborhood, but its complexity for the von Neumann neighborhood remains open. In a previous work, we provided a complete characterization of crossover gates (a key to the implementation of non-planar monotone circuits) for these small neighborhoods, leading to P-completeness proofs with only 4 and 5 neighbors among the eight adjancent cells. In this paper, we introduce the timed setting, where the goal is to determine whether cell q becomes unstable exactly at time t. We distinguish several cases: some neighborhoods support complete timed toolkits (including timed crossover gates) and exhibit P-completeness; others admit timed crossovers but suffer from synchronization issues; planar neighborhoods provably do not admit any timed crossover; and finally, for some remaining neighborhoods, we conjecture that no timed crossover is possible.
- 20 June 2025
- Published by Springer Nature
- p. 237-252
Circuit Metaconstruction in Logspace for Rice-Like Complexity Lower Bounds in ANs and SGRs
- 20 June 2025
- Published by Springer Nature
- p. 237-252
Circuit Metaconstruction in Logspace for Rice-Like Complexity Lower Bounds in ANs and SGRs
- 11 November 2024
- Published by Springer Nature in Natural Computing
- Vol. 24 (1) , 29-66
Sandpiles prediction and crossover on $\mathbb {Z}^2$ within Moore neighborhood- 11 November 2024
- Published by Springer Nature in Natural Computing
- Vol. 24 (1) , 29-66
Sandpiles prediction and crossover on $\mathbb {Z}^2$ within Moore neighborhood- Open Access
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$ is a discrete dynamical system described by the successive iterations of a function $f:Q^n\to Q^n$. In most applications, the main parameter is the interaction graph of $f$: the digraph with vertex set $[n]$ that contains an arc from $j$ to $i$ if $f_i$ depends on input $j$. What can be said on the set $\mathbb{G}(f)$ of the interaction graphs of the automata networks isomorphic to $f$? It seems that this simple question has never been studied. Here, we report some basic facts. First, we prove that if $n\geq 5$ or $q\geq 3$ and $f$ is neither the identity nor constant, then $\mathbb{G}(f)$ always contains the complete digraph $K_n$, with $n^2$ arcs. Then, we prove that $\mathbb{G}(f)$ always contains a digraph whose minimum in-degree is bounded as a function of $q$. Hence, if $n$ is large with respect to $q$, then $\mathbb{G}(f)$ cannot only contain $K_n$. However, we prove that $\mathbb{G}(f)$ can contain only dense digraphs, with at least $\lfloor n^2/4 \rfloor$ arcs.Open AccessInteraction 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$ is a discrete dynamical system described by the successive iterations of a function $f:Q^n\to Q^n$. In most applications, the main parameter is the interaction graph of $f$: the digraph with vertex set $[n]$ that contains an arc from $j$ to $i$ if $f_i$ depends on input $j$. What can be said on the set $\mathbb{G}(f)$ of the interaction graphs of the automata networks isomorphic to $f$? It seems that this simple question has never been studied. Here, we report some basic facts. First, we prove that if $n\geq 5$ or $q\geq 3$ and $f$ is neither the identity nor constant, then $\mathbb{G}(f)$ always contains the complete digraph $K_n$, with $n^2$ arcs. Then, we prove that $\mathbb{G}(f)$ always contains a digraph whose minimum in-degree is bounded as a function of $q$. Hence, if $n$ is large with respect to $q$, then $\mathbb{G}(f)$ cannot only contain $K_n$. However, we prove that $\mathbb{G}(f)$ can contain only dense digraphs, with at least $\lfloor n^2/4 \rfloor$ arcs. - 20 April 2022
- Published by Springer Nature
- p. 117-143
Sandpile Toppling on Penrose Tilings: Identity and Isotropic Dynamics
- 20 April 2022
- Published by Springer Nature
- p. 117-143
Sandpile Toppling on Penrose Tilings: Identity and Isotropic Dynamics