Kévin Perrot

95 papers A 1B 6C 8Journal 65Unranked 12
YearRankTypeTitle / Venue / Authors
2026 J jnl
Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions.
CoRR
Colin Geniet, Aliénor Goubault-Larrecq, Kévin Perrot
2026 J jnl
Complexity of the freezing majority rule with L-shaped neighborhoods.
Theor. Comput. Sci.
Pablo Concha-Vega, Eric Goles, Pedro Montealegre, Kévin Perrot
2026 J jnl
Hardness of monadic second-order formulae over succinct graphs.
Log. Methods Comput. Sci.
Guilhem Gamard, Aliénor Goubault-Larrecq, Pierre Guillon, Pierre Ohlmann, Kévin Perrot, Guillaume Theyssier
2026 J jnl
Majority Boolean networks classifying density: structural characterization and complexity.
CoRR
Kévin Perrot, Marius Rolland
2026 J jnl
Non-trivial automata networks do exist that solve the global majority problem with the local majority rule.
CoRR
Pedro Paulo Balbi, Kévin Perrot, Marius Rolland, Eurico L. P. Ruivo
2026 J jnl
On the dynamics of bounded-degree automata networks.
Nat. Comput.
Julio Aracena, Florian Bridoux, Maximilien Gadouleau, Pierre Guillon, Kévin Perrot, Adrien Richard, Guillaume Theyssier
2025 C conf
Circuit Metaconstruction in Logspace for Rice-Like Complexity Lower Bounds in ANs and SGRs.
CiE
Aliénor Goubault-Larrecq, Kévin Perrot
2025 J jnl
Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs.
CoRR
Aliénor Goubault-Larrecq, Kévin Perrot
2025 J jnl
Complexity of the Freezing Majority Rule with L-shaped Neighborhoods.
CoRR
Pablo Concha-Vega, Eric Goles, Pedro Montealegre, Kévin Perrot
2025 — conf
Creation of Fixed Points in Block-Parallel Boolean Automata Networks.
UCNC
Kévin Perrot, Sylvain Sené, Léah Tapin
2025 J jnl
Creation of fixed points in block-parallel Boolean automata networks.
CoRR
Kévin Perrot, Sylvain Sené, Léah Tapin
2025 J jnl
Foundations of block-parallel automata networks.
CoRR
Kévin Perrot, Sylvain Sené, Léah Tapin
2025 J jnl
Foundations of block-parallel automata networks.
Theor. Comput. Sci.
Kévin Perrot, Sylvain Sené, Léah Tapin
2025 J jnl
On the Dynamics of Bounded-Degree Automata Networks.
CoRR
Julio Aracena, Florian Bridoux, Maximilien Gadouleau, Pierre Guillon, Kévin Perrot, Adrien Richard, Guillaume Theyssier
2025 J jnl
Polygonal corona limit on multigrid dual tilings.
Nat. Comput.
Victor H. Lutfalla, Kévin Perrot
2025 J jnl
Sandpiles prediction and crossover on $\mathbb {Z}^2$ within Moore neighborhood.
Nat. Comput.
Pablo Concha-Vega, Eric Goles, Pedro Montealegre, Kévin Perrot
2025 J jnl
Solving decision problems by distributed consensus with one-dimensional, binary, radius-2 cellular automata over cyclic configurations.
CoRR
Eurico L. P. Ruivo, Pedro Paulo Balbi, Kévin Perrot, Marco Montalva-Medel, Eric Goles
2025 — conf
Timed Prediction Problem for Sandpile Models.
AUTOMATA
Pablo Concha-Vega, Kévin Perrot
2025 J jnl
Timed Prediction Problem for Sandpile Models.
CoRR
Pablo Concha-Vega, Kévin Perrot
2024 B conf
Combinatorics of Block-Parallel Automata Networks.
SOFSEM
Kévin Perrot, Sylvain Sené, Léah Tapin
2024 — conf
Complexity of Boolean Automata Networks Under Block-Parallel Update Modes.
SAND
Kévin Perrot, Sylvain Sené, Léah Tapin
2024 J jnl
Complexity of Boolean automata networks under block-parallel update modes.
CoRR
Kévin Perrot, Sylvain Sené, Léah Tapin
2024 J jnl
Negative results on density determination with one-dimensional cellular automata with block-sequential asynchronous updates.
J. Comput. Sci.
Eurico L. P. Ruivo, Kévin Perrot, Pedro P. B. de Oliveira, Pacôme Perrotin
2024 J jnl
Polygonal corona limit on multigrid dual tilings.
CoRR
Victor H. Lutfalla, Kévin Perrot
2024 J jnl
Rice-like complexity lower bounds for Boolean and uniform automata networks.
CoRR
Aliénor Goubault-Larrecq, Kévin Perrot
2024 — conf
Roots in the Semiring of Finite Deterministic Dynamical Systems.
AUTOMATA
François Doré, Kévin Perrot, Antonio E. Porreca, Sara Riva, Marius Rolland
2024 J jnl
Roots in the semiring of finite deterministic dynamical systems.
CoRR
François Doré, Kévin Perrot, Antonio E. Porreca, Sara Riva, Marius Rolland
2023 J jnl
Hardness of monadic second-order formulae over succinct graphs.
CoRR
Guilhem Gamard, Pierre Guillon, Kévin Perrot, Guillaume Theyssier
2023 J jnl
Interaction graphs of isomorphic automata networks I: Complete digraph and minimum in-degree.
J. Comput. Syst. Sci.
Florian Bridoux, Kévin Perrot, Aymeric Picard Marchetto, Adrien Richard
2023 J jnl
Interaction graphs of isomorphic automata networks I: complete digraph and minimum in-degree.
CoRR
Florian Bridoux, Kévin Perrot, Aymeric Picard Marchetto, Adrien Richard
2023 J jnl
On countings and enumerations of block-parallel automata networks.
CoRR
Kévin Perrot, Sylvain Sené, Léah Tapin
2022 J jnl
Complexity of fixed point counting problems in Boolean networks.
J. Comput. Syst. Sci.
Florian Bridoux, Amélia Durbec, Kévin Perrot, Adrien Richard
2022 J jnl
Non-maximal sensitivity to synchronism in elementary cellular automata: Exact asymptotic measures.
Theor. Comput. Sci.
Pedro Paulo Balbi de Oliveira, Enrico Formenti, Kévin Perrot, Sara Riva, Eurico L. P. Ruivo
2022 J jnl
Rikudo is NP-complete.
Theor. Comput. Sci.
Viet-Ha Nguyen, Kévin Perrot
2022 — conf
Sandpile Toppling on Penrose Tilings: Identity and Isotropic Dynamics.
Automata and Complexity
Jérémy Fersula, Camille Noûs, Kévin Perrot
2022 — book
Études de la complexité algorithmique des réseaux d'automates. (Studies of the algorithmic complexity of automata networks).
Kévin Perrot
2021 — ed.
27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2021, Aix-Marseille University, France, July 12-14, 2021
AUTOMATA
Alonso Castillo-Ramirez, Pierre Guillon, Kévin Perrot
2021 B conf
Complexity of Limit-Cycle Problems in Boolean Networks.
SOFSEM
Florian Bridoux, Caroline Gaze-Maillot, Kévin Perrot, Sylvain Sené
2021 J jnl
Freezing sandpiles and Boolean threshold networks: Equivalence and complexity.
Adv. Appl. Math.
Eric Goles, Pedro Montealegre, Kévin Perrot
2021 J jnl
Freezing sandpiles and Boolean threshold networks: equivalence and complexity.
CoRR
Eric Goles, Pedro Montealegre, Kévin Perrot
2021 J jnl
On Boolean Automata Networks (de)Composition.
Fundam. Informaticae
Kévin Perrot, Pacôme Perrotin, Sylvain Sené
2021 C conf
Optimising Attractor Computation in Boolean Automata Networks.
LATA
Kévin Perrot, Pacôme Perrotin, Sylvain Sené
2021 A conf
Rice-Like Theorems for Automata Networks.
STACS
Guilhem Gamard, Pierre Guillon, Kévin Perrot, Guillaume Theyssier
2021 J jnl
Rikudo is NP-complete.
CoRR
Viet-Ha Nguyen, Kévin Perrot
2020 C conf
#P-completeness of Counting Update Digraphs, Cacti, and Series-Parallel Decomposition Method.
CiE
Kévin Perrot, Sylvain Sené, Lucas Venturini
2020 J jnl
#P-completeness of counting update digraphs, cacti, and a series-parallel decomposition method.
CoRR
Camille Noûs, Kévin Perrot, Sylvain Sené, Lucas Venturini
2020 J jnl
Complexity of fixed point counting problems in Boolean Networks.
CoRR
Florian Bridoux, Amélia Durbec, Kévin Perrot, Adrien Richard
2020 J jnl
Complexity of limit-cycle problems in Boolean networks.
CoRR
Florian Bridoux, Caroline Gaze-Maillot, Kévin Perrot, Sylvain Sené
2020 J jnl
How Hard is it to Predict Sandpiles on Lattices? A Survey.
Fundam. Informaticae
Enrico Formenti, Kévin Perrot
2020 J jnl
Maximum sensitivity to update schedules of elementary cellular automata over infinite configurations.
Inf. Comput.
Eurico L. P. Ruivo, Pedro P. B. de Oliveira, Marco Montalva-Medel, Kévin Perrot
2020 J jnl
Maximum sensitivity to update schedules of elementary cellular automata over periodic configurations.
Nat. Comput.
Kévin Perrot, Marco Montalva-Medel, Pedro Paulo Balbi de Oliveira, Eurico L. P. Ruivo
2020 J jnl
NP-completeness of the game
Theor. Comput. Sci.
Viet-Ha Nguyen, Kévin Perrot, Mathieu Vallet
2020 — conf
Non-maximal Sensitivity to Synchronism in Periodic Elementary Cellular Automata: Exact Asymptotic Measures.
Automata
Pedro Paulo Balbi de Oliveira, Enrico Formenti, Kévin Perrot, Sara Riva, Eurico L. P. Ruivo
2020 J jnl
Non-maximal sensitivity to synchronism in periodic elementary cellular automata: exact asymptotic measures.
CoRR
Pedro Paulo Balbi de Oliveira, Enrico Formenti, Kévin Perrot, Sara Riva, Eurico L. P. Ruivo
2020 C conf
On the Complexity of Acyclic Modules in Automata Networks.
TAMC
Kévin Perrot, Pacôme Perrotin, Sylvain Sené
2020 J jnl
On the emergence of regularities on one-dimensional decreasing sandpiles.
Theor. Comput. Sci.
Kévin Perrot, Éric Rémila
2020 J jnl
Optimising attractor computation in Boolean automata networks.
CoRR
Kévin Perrot, Pacôme Perrotin, Sylvain Sené
2019 C conf
Complexity of Maximum Fixed Point Problem in Boolean Networks.
CiE
Florian Bridoux, Nicolas Durbec, Kévin Perrot, Adrien Richard
2019 J jnl
How hard is it to predict sandpiles on lattices? A survey.
CoRR
Kévin Perrot, Enrico Formenti
2019 J jnl
NP-completeness of the game Kingdomino.
CoRR
Viet-Ha Nguyen, Kévin Perrot, Mathieu Vallet
2019 J jnl
On the complexity of acyclic modules in automata networks.
CoRR
Kévin Perrot, Pacôme Perrotin, Sylvain Sené
2019 J jnl
On the complexity of counting feedback arc sets.
CoRR
Kévin Perrot
2018 C conf
A Framework for (De)composing with Boolean Automata Networks.
MCU
Kévin Perrot, Pacôme Perrotin, Sylvain Sené
2018 J jnl
A framework for (de)composing with Boolean automata networks.
CoRR
Kévin Perrot, Pacôme Perrotin, Sylvain Sené
2018 — conf
Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models.
Automata
Viet-Ha Nguyen, Kévin Perrot
2018 B conf
Balanced Connected Partitioning of Unweighted Grid Graphs.
MFCS
Cedric Berenger, Peter Niebert, Kévin Perrot
2018 J jnl
Computational Complexity of the Avalanche Problem for One Dimensional Decreasing Sandpiles.
J. Cell. Autom.
Enrico Formenti, Kévin Perrot, Eric Rémila
2018 J jnl
Computational complexity of the avalanche problem on one dimensional Kadanoff sandpiles.
CoRR
Enrico Formenti, Kévin Perrot, Eric Rémila
2018 J jnl
Linearity is Strictly More Powerful than Contiguity for Encoding Graphs.
CoRR
Christophe Crespelle, Tien-Nam Le, Kévin Perrot, Thi Ha Duong Phan
2018 J jnl
On the complexity of two-dimensional signed majority cellular automata.
J. Comput. Syst. Sci.
Eric Goles, Pedro Montealegre, Kévin Perrot, Guillaume Theyssier
2017 C conf
On the Cost of Simulating a Parallel Boolean Automata Network by a Block-Sequential One.
TAMC
Florian Bridoux, Pierre Guillon, Kévin Perrot, Sylvain Sené, Guillaume Theyssier
2017 J jnl
On the cost of simulating a parallel Boolean automata network by a block-sequential one.
CoRR
Florian Bridoux, Pierre Guillon, Kévin Perrot, Sylvain Sené, Guillaume Theyssier
2017 J jnl
Strong Emergence of Wave Patterns on Kadanoff Sandpiles.
Electron. J. Comb.
Kévin Perrot, Eric Rémila
2016 J jnl
Chip-Firing Game and a Partial Tutte Polynomial for Eulerian Digraphs.
Electron. J. Comb.
Kévin Perrot, Van Trung Pham
2016 J jnl
Linearity is strictly more powerful than contiguity for encoding graphs.
Discret. Math.
Christophe Crespelle, Tien-Nam Le, Kévin Perrot, Thi Ha Duong Phan
2015 — conf
Emergence on Decreasing Sandpile Models.
MFCS (1)
Kévin Perrot, Eric Rémila
2015 B conf
Linearity Is Strictly More Powerful Than Contiguity for Encoding Graphs.
WADS
Christophe Crespelle, Tien-Nam Le, Kévin Perrot, Thi Ha Duong Phan
2015 — conf
On the Flora of Asynchronous Locally Non-monotonic Boolean Automata Networks.
SASB
Aurore Alcolei, Kévin Perrot, Sylvain Sené
2015 J jnl
On the flora of asynchronous locally non-monotonic Boolean automata networks.
CoRR
Aurore Alcolei, Kévin Perrot, Sylvain Sené
2015 J jnl
Piles de sable décroissantes 1D. Classification expérimentale d'émergences.
Tech. Sci. Informatiques
Kévin Perrot, Eric Rémila
2014 — conf
Computational Complexity of the Avalanche Problem on One Dimensional Kadanoff Sandpiles.
Automata
Enrico Formenti, Kévin Perrot, Eric Rémila
2014 B conf
Emergence of Wave Patterns on Kadanoff Sandpiles.
LATIN
Kévin Perrot, Eric Rémila
2013 — conf
Effects of migration of three competing species on their distributions in multizone environment.
RIVF
Thi Ha Duong Phan, Nguyen-Ngoc Doanh, Kévin Perrot
2013 J jnl
Emergence of wave patterns on Kadanoff Sandpiles.
CoRR
Kévin Perrot, Eric Rémila
2013 J jnl
Kadanoff Sand Pile Model. Avalanche Structure and Wave Shape
CoRR
Kévin Perrot, Eric Rémila
2013 J jnl
Kadanoff Sand Piles, following the snowball
CoRR
Kévin Perrot, Eric Rémila
2013 J jnl
Kadanoff sand pile model. Avalanche structure and wave shape.
Theor. Comput. Sci.
Kévin Perrot, Eric Rémila
2013 — —
Les piles de sable Kadanoff. (Kadanoff sandpiles).
Kévin Perrot
2013 J jnl
NP-hardness of minimum feedback arc set problem on Eulerian digraphs and minimum recurrent configuration problem of Chip-firing game
CoRR
Kévin Perrot, Van Trung Pham
2012 J jnl
On the set of Fixed Points of the Parallel Symmetric Sand Pile Model
CoRR
Kévin Perrot, Thi Ha Duong Phan, Van Trung Pham
2011 J jnl
Avalanche Structure in the Kadanoff Sand Pile Model
CoRR
Kévin Perrot, Eric Rémila
2011 C conf
Avalanche Structure in the Kadanoff Sand Pile Model.
LATA
Kévin Perrot, Eric Rémila
2011 — conf
On the set of Fixed Points of the Parallel Symmetric Sand Pile Model.
Automata
Kévin Perrot, Thi Ha Duong Phan, Van Trung Pham
2011 J jnl
Transduction on Kadanoff Sand Pile Model Avalanches, Application to Wave Pattern Emergence
CoRR
Kévin Perrot, Eric Rémila
2011 B conf
Transduction on Kadanoff Sand Pile Model Avalanches, Application to Wave Pattern Emergence.
MFCS
Kévin Perrot, Eric Rémila