Member of the Natural Computation reasearch group at LIS.
Computing and Philosophy reading group.
Neurogeeks reading group.
Publications
Journal Conference OtherAutomata networks.
| [PST24a] | Kévin Perrot, Sylvain Sené, and Léah Tapin. Combinatorics of Block-Parallel Automata Networks. In Proceedings of SOFSEM'2024, volume 14519 of LNCS, pages 442--455. Springer, 2024. . [ bib | DOI | arXiv ] |
| [PST24b] | Kévin Perrot, Sylvain Sené, and Léah Tapin. Complexity of Boolean automata networks under block-parallel update modes. In Proceedings of SAND'2024, volume 292 of LIPIcs, pages 19:1--19:19, 2024. . [ bib | DOI | arXiv ] |
| [GP24] | Aliénor Goubault--Larrecq and Kévin Perrot. Rice-like complexity lower bounds for Boolean and uniform automata networks. Preprint, page 32, 2024. . [ bib | arXiv ] |
| [BPPMR23] | Florian Bridoux, Kévin Perrot, Aymeric Picard Marchetto, and Adrien Richard. Interaction graphs of isomorphic automata networks I: Complete digraph and minimum in-degree. Journal of Computer and System Sciences, 138:103458, 2023. . [ bib | DOI | arXiv ] |
| [GGPT23] | Guilhem Gamard, Pierre Guillon, Kevin Perrot, and Guillaume Theyssier. Hardness of monadic second-order formulae over succinct graphs. Preprint, page 25, 2023. . [ bib | arXiv | HAL ] |
| [ABG+23] | Julio Aracena, Florian Bridoux, Pierre Guillon, Kévin Perrot, Adrien Richard, and Guillaume Theyssier. On the dynamics of bounded-degree automata networks. Exploratory paper of AUTOMATA'2023, 2023. . [ bib | DOI | pdf | HAL ] |
| [BDPR22] | Florian Bridoux, Amélia Durbec, Kévin Perrot, and Adrien Richard. Complexity of fixed point counting problems in Boolean Networks. Journal of Computer and System Sciences, 126:138--164, 2022. . [ bib | DOI | arXiv ] |
| [BGMPS21] | Florian Bridoux, Caroline Gaze-Maillot, Kévin Perrot, and Sylvain Sené. Complexity of limit-cycle problems in boolean networks. In Proceedings of SOFSEM'2021, volume 12607 of LNCS, pages 135--146. Springer, 2021. . [ bib | DOI | arXiv ] |
| [GGPT21] | Guilhem Gamard, Pierre Guillon, Kevin Perrot, and Guillaume Theyssier. Rice-Like Theorems for Automata Networks. In Proceedings of STACS'2021, volume 187 of LIPIcs, pages 32:1--32:17. Schloss Dagstuhl, 2021. . [ bib | DOI ] |
| [PPS21a] | Kévin Perrot, Pacôme Perrotin, and Sylvain Sené. On Boolean automata networks (de)composition. Fundamenta Informaticae, 181(2-3):163--188, 2021. . [ bib | DOI | arXiv ] |
| [PPS21b] | Kévin Perrot, Pacôme Perrotin, and Sylvain Sené. Optimising attractor computation in Boolean automata networks. In Proceedings of LATA'2021, volume 12638 of LNCS, pages 68--80, 2021. . [ bib | arXiv ] |
| [NPSV20] | Camille Noûs, Kévin Perrot, Sylvain Sené, and Lucas Venturini. #P-completeness of counting update digraphs, cacti, and series-parallel decomposition method. In Proceedings of CiE'2020, volume 12098 of LNCS, pages 326--338. Springer, 2020. . [ bib | DOI | arXiv ] |
| [PPS20] | Kévin Perrot, Pacôme Perrotin, and Sylvain Sené. On the Complexity of Acyclic Modules in Automata Networks. In Proceedings of TAMC'2020, volume 12337 of LNCS, pages 168--180. Springer, 2020. . [ bib | DOI | arXiv ] |
| [BDPR19] | Florian Bridoux, Nicolas Durbec, Kévin Perrot, and Adrien Richard. Complexity of Maximum Fixed Point Problem in Boolean Networks. In Proceedings of CiE'2019, volume 11558 of LNCS, pages 132--143. Springer, 2019. . [ bib | DOI | HAL ] |
| [PPS18] | Kévin Perrot, Pacôme Perrotin, and Sylvain Sené. A framework for (de)composing with Boolean automata networks. In Proceedings of MCU'2018, volume 10881 of LNCS, pages 121--136. Springer, 2018. . [ bib | DOI | arXiv | HAL ] |
| [BGP+17] | Florian Bridoux, Pierre Guillon, Kévin Perrot, Sylvain Sené, and Guillaume Theyssier. On the cost of simulating a parallel boolean automata network by a block-sequential one. In Proceedings of TAMC'2017, volume 10185 of LNCS, pages 112--128. Springer, 2017. . [ bib | DOI | arXiv | HAL ] |
| [APS16] | Aurore Alcolei, Kévin Perrot, and Sylvain Sené. On the flora of asynchronous locally non-monotonic Boolean automata networks. In Proceedings of SASB'2015, volume 326 of ENTCS, pages 3--25, 2016. . [ bib | DOI | arXiv ] |
Sandpile models, a kind of non-linear discrete dynamical system exhibiting non-trivial emergent structures, from a simple evolution rule... quite surprising. Wanna play?
| [LP24] | Victor Lutfalla and Kevin Perrot. Polygonal corona limit on multigrid dual tilings. Preprint, page 19, 2024. . [ bib | arXiv ] |
| [CVGMP24] | Pablo Concha-Vega, Eric Goles, Pedro Montealegre, and Kévin Perrot. Sandpiles prediction and crossover on Z2 within Moore neighborhood. Natural Computing, 2024. . [ bib | DOI | pdf ] |
| [FNP22] | Jérémy Fersula, Camille Noûs, and Kévin Perrot. Sandpile toppling on penrose tilings: identity and isotropic dynamics. (Chapter) Automata and complexity, Springer Series on Emergence, Complexity and Computation, 42, 2022. . [ bib | DOI | arXiv ] |
| [GMP21] | Eric Goles, Pedro Montealegre, and Kévin Perrot. Freezing sandpiles and Boolean threshold networks: Equivalence and complexity. Advances in Applied Mathematics, 125:102161, 2021. . [ bib | DOI | arXiv ] |
| [PR20] | Kévin Perrot and Éric Rémila. On the emergence of regularities on one-dimensional decreasing sandpiles. Theoretical Computer Science, 843:1--24, 2020. . [ bib | DOI | HAL ] |
| [FP19] | Enrico Formenti and Kévin Perrot. How Hard is it to Predict Sandpiles on Lattices? A Survey. Fundamenta Informaticae, 171:189--219, 2019. . [ bib | DOI | arXiv ] |
| [FPR18] | Enrico Formenti, Kévin Perrot, and Eric Rémila. Computational complexity of the avalanche problem for one dimensional decreasing sandpiles. Journal of Cellular Automata, 13:215--228, 2018. . [ bib | HAL ] |
| [NP18] | Viet-Ha Nguyen and Kévin Perrot. Any shape can ultimately cross information on two-dimensional abelian sandpile models. In Proceedings of AUTOMATA'2018, volume 10875 of LNCS, pages 127--142. Springer, 2018. . [ bib | DOI | arXiv | HAL ] |
| [PR17] | Kévin Perrot and Eric Rémila. Strong emergence of wave patterns on Kadanoff sandpiles. Electronic Journal of Combinatorics, 24(2), 2017. . [ bib | pdf | HAL ] |
| [PR15b] | Kévin Perrot and Éric Rémila. Piles de sable décroissantes 1D : classification expérimentale d'émergences. Technique et Science Informatiques -- Automates cellulaires et réseaux d'automates : le rôle central de l'irrégularité, 2015. . [ bib | HAL ] |
| [PR15a] | Kévin Perrot and Éric Rémila. Emergence on decreasing sandpile models. In Proceedings of MFCS'2015, volume 9234 of LNCS, pages 419--431. Springer, 2015. . [ bib | HAL ] |
| [PR14b] | Kévin Perrot and Éric Rémila. Emergence of wave patterns on Kadanoff Sandpiles. In Proceedings of LATIN'2014, volume 8392 of LNCS, pages 634--645. Springer, 2014. . [ bib | arXiv ] |
| [FPR14] | Enrico Formenti, Kévin Perrot, and Eric Rémila. Computational complexity of the avalanche problem on one dimensional Kadanoff sandpiles. In Proceedings of AUTOMATA'2014, volume 8996 of LNCS, pages 21--30. Springer, 2014. . [ bib | arXiv ] |
| [PR14a] | Kévin Perrot and Éric Rémila. Emergence of regularities on decreasing sandpile models. 15th Mons Theoretical Computer Science Days, Nancy, France, 2014. . [ bib ] |
| [PR13] | Kévin Perrot and Éric Rémila. Kadanoff sand pile model. Avalanche structure and wave shape. Theoretical Computer Science, 504:52--72, 2013. . [ bib | arXiv ] |
| [PR12] | Kévin Perrot and Éric Rémila. Kadanoff Sand Piles, following the snowball. Research report, page 26, 2012. . [ bib | arXiv ] |
| [PR11a] | Kévin Perrot and Éric Rémila. Avalanche Structure in the Kadanoff Sand Pile Model. In Proceedings of LATA'2011, volume 6638 of LNCS, pages 427--439. Springer, 2011. . [ bib | arXiv ] |
| [PR11b] | Kévin Perrot and Éric Rémila. Transduction on Kadanoff Sand Pile Model Avalanches, Application to Wave Pattern Emergence. In Proceedings of MFCS'2011, volume 6907 of LNCS, pages 508--520. Springer, 2011. . [ bib | arXiv ] |
| [PPVP11] | Kévin Perrot, Ha Duong Phan, and Trung Van Pham. On the set of Fixed Points of the Parallel Symmetric Sand Pile Model. In Proceedings of AUTOMATA'2011, DMTCS, pages 17--28, 2011. . [ bib | arXiv | HAL ] |
Cellular automata. You can give a try to this great simple simulator written in javascript by Charles Paperman.
| [RPBP24] | Eurico Ruivo, Kévin Perrot, Pedro Paulo Balbi, and Pacôme Perrotin. Negative results on density determination with one-dimensional cellular automata with block-sequential asynchronous updates. Journal of Computational Science, 82:102430, 2024. . [ bib | DOI | HAL ] |
| [BFP+22] | Pedro Paulo Balbi, Enrico Formenti, Kévin Perrot, Sara Riva, and Eurico L. P. Ruivo. Non-maximal Sensitivity to Synchronism in ECA: Exact Asymptotic Measures. Theoretical Computer Science, 926:21--50, 2022. Extended version of AUTOMATA'2020. . [ bib | DOI | arXiv ] |
| [PMMdOR20] | Kévin Perrot, Marco Montalva-Medel, Pedro P. B. de Oliveira, and Eurico L. P. Ruivo. Maximum sensitivity to update schedule of elementary cellular automata over periodic configurations. Natural Computing, 19:51--90, 2020. . [ bib | DOI | read-only pdf | HAL ] |
| [RBMMP20] | Eurico L. P. Ruivo, Pedro Paulo Balbi, Marco Montalva-Medel, and Kévin Perrot. Maximum sensitivity to update schedules of elementary cellular automata over infinite configurations. Information and Computation, page 104538, 2020. . [ bib | DOI ] |
| [RBP20] | Eurico L. P. Ruivo, Pedro Paulo Balbi, and Kévin Perrot. An asynchronous solution to the synchronisation problem for binary one-dimensional cellular automata. Physica D: Nonlinear Phenomena, 413:132554, 2020. . [ bib | DOI ] |
| [BFP+20] | Pedro Paulo Balbi, Enrico Formenti, Kévin Perrot, Sara Riva, and Eurico L. P. Ruivo. Non-maximal Sensitivity to Synchronism in Periodic Elementary Cellular Automata: Exact Asymptotic Measures. In Proceedings of AUTOMATA'2020, volume 12286 of LNCS, pages 14--28, 2020. . [ bib | DOI | arXiv ] |
| [RMMdOP18] | Eurico L. P. Ruivo, Marco Montalva-Medel, Pedro P. B. de Oliveira, and Kévin Perrot. Characterisation of the elementary cellular automata in terms of their maximum sensitivity to all possible asynchronous updates. Chaos, Solitons & Fractals, 113:209--220, 2018. . [ bib | DOI ] |
| [GMPT17] | Eric Goles, Pedro Montealegre, Kévin Perrot, and Guillaume Theyssier. On the complexity of two-dimensional signed majority cellular automata. Journal of Computer and System Sciences, 91:1--32, 2017. . [ bib | DOI | HAL ] |
| [MMPdOR17] | Marco Montalva Medel, Kévin Perrot, Pedro de Oliveira, and Eurico Ruivo. Sensitivity to synchronism in some boolean automata networks. Exploratory paper of AUTOMATA'2017, pages 69--76, 2017. . [ bib | HAL ] |
Algebra of discrete dynamical systems.
| [DPP+24] | François Doré, Kévin Perrot, Antonio E. Porreca, Sara Riva, and Marius Rolland. Roots in the semiring of finite deterministic dynamical systems. In Proceedings of AUTOMATA'2024, volume 14782 of LNCS, pages 120--132. Springer, 2024. . [ bib | DOI | arXiv ] |
Chip-firing games.
| [PVP16] | Kévin Perrot and Trung Van Pham. Chip-firing game and partial Tutte polynomial for Eulerian digraphs. Electronic Journal of Combinatorics, 23(1), 2016. . [ bib | arXiv | pdf ] |
| [PVP15] | Kévin Perrot and Trung Van Pham. Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of Chip-firing game on directed graphs. Annals of Combinatorics, 19:373--396, 2015. . [ bib | arXiv ] |
Distributed algorithms.
| [BNP18] | Cédric Berenger, Peter Niebert, and Kévin Perrot. Balanced Connected Partitioning of Unweighted Grid Graphs. In Proceedings of MFCS'2018), volume 117 of LIPIcs, pages 39:1--39:18, 2018. . [ bib | DOI | pdf ] |
Games.
| [NP22] | Viet-Ha Nguyen and Kévin Perrot. Rikudo is NP-complete. Theoretical Computer Science, 910:34--47, 2022. . [ bib | DOI | arXiv ] |
| [NPV20] | Viet-Ha Nguyen, Kévin Perrot, and Mathieu Vallet. NP-completeness of the game Kingdomino. Theoretical Computer Science, 822:23--35, 2020. . [ bib | DOI | arXiv | HAL ] |
Graphs.
| [Per22] | Kévin Perrot. On the complexity of counting feedback arc sets. Chicago Journal of Theoretical Computer Science, 2022, 2022. . [ bib | DOI | arXiv | pdf ] |
| [CLPP16] | Christophe Crespelle, Tien-Nam Le, Kévin Perrot, and Thi Ha Duong Phan. Linearity is strictly more powerful than contiguity for encoding graphs. Discrete Mathematics, 339:2168--2177, 2016. . [ bib | arXiv ] |
| [CLPP15] | Christophe Crespelle, Tien-Nam Le, Kévin Perrot, and Thi Ha Duong Phan. Linearity is strictly more powerful than contiguity for encoding graphs. In Proceedings of WADS'2015, volume 9214 of LNCS, pages 212--223. Springer, 2015. . [ bib ] |
Ecological population modeling.
| [PNNP13] | Kévin Perrot, Doanh Nguyen-Ngoc, and Ha Duong Phan. Effects of Migration of Three Competing Species on Their Distributions in Multizone Environment. In Proceedings of RIVF'2013, IEEE, pages 227--232, 2013. . [ bib | pdf ] |
Edition.
| [CGP21] | Alonso Castillo-Ramirez, Pierre Guillon, and Kévin Perrot, editors. 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2021, July 12-14, 2021, Aix-Marseille University, France, volume 90 of OASIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. . [ bib | pdf | http ] |
Scientific diffusion (vulgarisation).
| [Per23] | Kévin Perrot. Tout est complexe. Interstices -- Revue de culture scientifique en ligne publiée par Inria, 2023. . [ bib | http ] |
| [PS22] | Kévin Perrot and Sylvain Sené. Les réseaux d'automates booléens au coeur du calcul naturel. 1024 -- Bulletin de la Socété informatique de France, 20:171--182, November 2022. . [ bib | DOI | pdf ] |
Academic.
| [Per22] | Kévin Perrot. Études de la complexité algorithmique des réseaux d'automates. HDR, Aix-Marseille Université, 2022. . [ bib | pdf | HAL ] |
| [Per13] | Kévin Perrot. Les piles de sable Kadanoff. PhD, Ecole normale supérieure de lyon, 2013. . [ bib | pdf | HAL ] |
(this bibliography was generated with bibtex2html)
