Kévin Perrot hey, fungal totalistic simulator | sandpile simulator | vulgariser



Location:
Luminy - TPR2
Office 05.34
(map)

LIS
Parc scientifique de Luminy
163, avenue de Luminy - Case 901
F-13288 Marseille Cedex 9
France

Phone:
+33(0)4 86 09 04 97
Part of Université publique.

Member of the Natural Computation reasearch group at LIS.

Computing and Philosophy reading group.

Neurogeeks reading group.

Publications

 Journal      Conference      Other

Automata 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, 2024. To appear. . [ 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. 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. page 19, 2024. . [ bib | arXiv ]
[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.
[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 ]

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)