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

Publications

  1. 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  
  2. Perrot, Kévin, Sylvain Sené, and Léah Tapin. “Creation of Fixed Points in Block-Parallel Boolean Automata Networks.” Preprint, 2025. arXiv-link  
  3. Lutfalla, Victor, and Kévin Perrot. “Polygonal Corona Limit on Multigrid Dual Tilings.” Natural Computing, 2025. DOI-link   arXiv-link  
  4. 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  
  5. 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  
  6. Perrot, Kévin, Sylvain Sené, and Léah Tapin. “Foundations of Block-Parallel Automata Networks.” Preprint, 2025. arXiv-link  
  7. Porreca, Antonio E., and Marius Rolland. “Injectivity of Polynomials over Finite Discrete Dynamical Systems.” Preprint, 2025. arXiv-link  
  8. 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  
  9. 2024 Goubault–Larrecq, Aliénor, and Kévin Perrot. “Rice-like Complexity Lower Bounds for Boolean and Uniform Automata Networks.” Preprint, 2024. arXiv-link  
  10. 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
  11. 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  
  12. 2021 ———. “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

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!