ALARICE

tries to obtain general complexity bounds for finite dynamical systems, among other things.

ANR-24-CE48-7504

Duration: 01/01/2025–31/12/2029 (60 months).

Agence Nationale de la Recherche Centre National de la Recherche Scientifique Inria

Laboratoire d'Informatique et des Systèmes Aix Marseille Université Laboratoire d'Informatique, Signaux et Systèmes de Sophia Antipolis Université Côte d'Azur

Institut de Mathématiques de Marseille JUNIA Laboratoire lorrain de Recherche en Informatique et ses Applications Centre de Recherche en Informatique, Signal et Automatique de Lille

Spirit

One of the most meaningful theorem in computer science is due to Rice, in 1953:
Theorem. Any non-trivial question on the behavior of programs is undecidable.
What is striking about this statement is its generality: it holds for any non-trivial question. Furthermore, trivial questions are answered by one of two trivial programs (either returning always “yes”, or returning always “no”), hence the dichotomy is both sharp and deep. This brings its interpretation to an epistemological ground regarding the powers and limits of algorithmic problem solving (i.e., by means of a computer, which is nowadays ubiquitous). Attaining this level of generality is the guiding principle of our project ALARICE — to obtain results “à la Rice”.

Rice’s theorem belongs to the field of computability theory, and we aim to bring its spirit to the field of complexity theory, which is another fundamental pillar of computer science. This shift towards the decidable world is motivated by the objects under consideration, finite dynamical systems, where virtually any question is decidable via a naive exhaustive search. As a consequence, the formulation of Rice-like results consists in general (lower and upper) bounds of computational complexity. The discrete dynamical systems at stake are defined by “simple” local rules, and readily show “complex” global behaviors. They are informally referred to as “complex systems”, and we endorse that the computational complexity point of view provides a theoretical framework to formalize this common intuition.

ALARICE is composed of three Objectives.
1) Develop a novel combination of techniques based on the expressiveness of finite model theory, which allows to prove metatheorems, provided a correct definition of non-triviality.
2) Adopt a systematic complexity point of view approach on all facets of automata network theory, aimed at gaining legible knowledge towards the implementation of vaster metatheorem proof techniques.
3) Transfer the results to other models of computation, such as finite cellular automata and reaction systems, through the reconsideration of simulations in the unifying framework of reductions, and reach an understanding of the complexity of finite dynamical systems as abstract and broad as possible.

For more, see alarice-pub.pdf.

Consortium

Partner 1 (Marseille, coord. LIS):

Partner 2 (Nice+, coord. I3S):

Institutions

Events

  • 2025-09-01 (1 week)
    Léah Tapin presents her work at UCNC-2025 in Nice, with Kévin Perrot and Sylvain Sené also participating.

  • 2025-07-21 (1 month)
    Marius Rolland visits the group of Luca Manzoni in Trieste, Italy.

  • 2025-07-14 (1 month)
    Kévin Perrot, Sylvain Sené, Léah Tapin visit the group of Luca Manzoni in Trieste, Italy.

  • 2025-07-14 (1 week)
    Aliénor Goubault-Larrecq and Marius Rolland present their work at CiE-2025 in Lisbon, Portugal.

  • 2025-07-30 (1 week)
    AUTOMATA-WAN-2025 takes place in Lille (CRIStAL), with financial support from the project. Sara Riva and Adien Richard are co-chairs. Florian Bridoux, Kévin Perrot, Marius Rolland, Sylvain Sené, Léah Tapin and Guillaume Theyssier participate.

  • 2025-06-16 (1 week)
    Kévin Perrot welcomes 3 high school students (classe de 2nde) at LIS : Jeanne Baudevin (lycée Jacques Chirac), Zoé Carotti and Line Lucet (lycée Marseilleveyre), discovering research around the game of life and elementary cellular automata.

  • 2025-06-12 (1 month)
    Visit of Eric Goles at LIS.

  • 2025-06-03 (2 months)
    Antonin Loubière (L3 ENS Paris Saclay) is in internship with Kévin Perrot and Pablo Concha on the complexity of sandpile models and crossovers.

  • 2025-06-02 (3 days)
    Pierre Guillon and Guillaume Theyssier participate to SDA2 days in Montpellier.

  • 2025-05-19 (2.5 months)
    Houzaime Ahamada (L2 AMU DLMI) is in internship with Kévin Perrot on developing a simulator of physarum polycephalum.

  • 2025-05-14 (2 days)
    Visit of Adrien Richard at LIS.

  • 2025-05-12 (1 week)
    Visit of Sara Riva at LIS.

  • 2025-05-06 (2 weeks)
    Visit of Martín Ríos-Wilson at LIS.

  • 2025-04-30 (1 day)
    Visit of Amélia Durbec at LIS.

  • 2025-03-27 (3 days)
    Congrès MATh.en.JEANS in Marseille, with Pierre Guillon, Kévin Perrot and Marius Rolland (year-long research activities with high school Pierre Mendes France, 13127 Vitrolles, in partnership with maths teacher Jessica Gouirand-Thuillet).

  • 2025-03-11 (2 days)
    ALARICE kickoff meeting at CIRM, Marseille Luminy.

  • 2025-01-06 (2 weeks)
    Visit of Marco Montalva at LIS.

Publications

  1. Concha-Vega, Pablo, and Kévin Perrot. “Timed Prediction Problem for Sandpile Models.” Preprint, 2025. HAL-link  
  2. Porreca, Antonio E., and Marius Rolland. “Solving Pseudo-Injective Polynomial Equations over Finite Dynamical Systems.” Preprint, 2025. arXiv-link  
  3. Gamard, Guilhem, Aliénor Goubault-Larrecq, Pierre Guillon, Pierre Ohlmann, Kévin Perrot, and Guillaume Theyssier. “Hardness of Monadic Second-Order Formulae over Succinct Graphs.” Preprint, 2025. HAL-link   arXiv-link  
  4. Perrot, Kévin, Sylvain Sené, and Léah Tapin. “Creation of Fixed Points in Block-Parallel Boolean Automata Networks.” Preprint, 2025. HAL-link   arXiv-link  
  5. Lutfalla, Victor, and Kévin Perrot. “Polygonal Corona Limit on Multigrid Dual Tilings.” Natural Computing, 2025. DOI-link   arXiv-link  
  6. Goubault-Larrecq, Aliénor, and Kévin Perrot. “Circuit Metaconstruction in Logspace for Rice-like Complexity Lower Bounds in ANs and SGRs.” Preprint, 2025. arXiv-link  
  7. Concha-Vega, Pablo, Eric Goles, Pedro Montealegre, and Kévin Perrot. “Sandpiles Prediction and Crossover on Z2 within Moore Neighborhood.” Natural Computing 24 (2025): 29–66. DOI-link   HAL-link  
  8. Perrot, Kévin, Sylvain Sené, and Léah Tapin. “Foundations of Block-Parallel Automata Networks.” Preprint, 2025. arXiv-link  
  9. Porreca, Antonio E., and Marius Rolland. “Injectivity of Polynomials over Finite Discrete Dynamical Systems.” Preprint, 2025. arXiv-link  
  10. Doré, François, Kévin Perrot, Antonio E. Porreca, Sara Riva, and Marius Rolland. “Roots in the Semiring of Finite Deterministic Dynamical Systems.” Preprint, 2025. arXiv-link  
  11. (2024) Goubault–Larrecq, Aliénor, and Kévin Perrot. “Rice-like Complexity Lower Bounds for Boolean and Uniform Automata Networks.” Preprint, 2024. arXiv-link  
  12. (2024) Theyssier, Guillaume. “FO Logic on Cellular Automata Orbits Equals MSO Logic.” In Proceedings of ICALP’2024, 297:154:1–154:20. LIPIcs. Schloss Dagstuhl, 2024. DOI-link   HAL-link   PDF-link
  13. (2023) Gamard, Guilhem, Pierre Guillon, Kévin Perrot, and Guillaume Theyssier. “Hardness of Monadic Second-Order Formulae over Succinct Graphs.” Preprint, 2023. HAL-link   arXiv-link  
  14. (2023) Perrot, Kévin. “Tout Est Complexe.” Interstices – Revue De Culture Scientifique En Ligne Publiée Par Inria, 2023. HTTP-link
  15. (2021) Gamard, Guilhem, Pierre Guillon, Kévin Perrot, and Guillaume Theyssier. “Rice-like Theorem for Automata Networks.” In Proceedings of STACS’21, 187:32:1–32:17. LIPIcs. Schloss Dagstuhl, 2021. DOI-link   PDF-link

Credits

The .pdf documents hosted on this website remain the property of their authors.

Site made with Jekyll from the template BlackDoc and jekyll-scholar.
Runs on gitlab.lis-lab.fr/kevin.perrot/alarice with Gitlab pages.

Something wrong? Bug or obsolete info?
Please email Kevin Perrot at <name dot surname at lis-lab dot fr>. Thanks!