Welcome to the webpage of the MC3 team from I3S laboratory (UMR 7271 CNRS & UniCA). This is one of the two teams of MDSC group.


MC3 research group

Description

Complex systems is a field of computer science which brings together problems from different scientific disciplines such as physics, computer science, biology, sociology, etc. Studied phenomena have a common denominator: many simple elementary components which cooperate to produce complex behavior.

In this context, a large number of new models have been proposed. These models often need to be formalized, compared or reduced to others, or basically studied with techniques from theoretical computer science. We propose to put at the service of the complex systems community our experience acquired in the fields of theoretical computer science (computability, language theory, dynamical systems, combinatorics, etc.) to carry out this in-depth work.

We seek to provide a formal framework for the study of complex systems using discrete dynamical systems as the main instrument of analysis, essentially focusing on the long-term properties of the system as well as the decidability/complexity of these properties.

Keywords

  • Complex Systems
  • Dicrete/Finite dynamical systems
  • Automata/Boolean networks
  • Cellular automata
  • Formal language
  • Decidability and Complexity
  • Combinatorics

History

The group was founded by Enrico Formenti in 2007 who led it until 2023. This web page succeeds the old page and only collects information from 2023.


Members

Permanent team members

Non-permanent team members

  • Issa-Moussa Diop, ATER.

PhD students

  • Kenza Benjelloun - PhD with Enrico Formenti.
    MIUR/PNRR funding with Univ. de Trieste, Italy (2022-).
  • Amelia Kunze - PhD with Enrico Formenti.
    MIUR funding with Univ. dell’Insubria, Varese, Italy (2023-).
  • Thomas Prevost, PhD with Bruno Martin.
    MESR/EDSTIC-UniCA funding (2023-).

Past members

Past Non-permanent team members

Past PhD students

  • Aymeric Picard-Marchetto, PhD with Adrien Richard and Florian Bridoux.
    MESR/EDSTIC-UniCA fundind (2021-2024).
  • François Doré, PhD with Enrico Formenti.
    MESR/EDSTIC-UniCA funding (2020-2023), UniCA ATER (2023-2024).

Past students

  • Mohamed Mahjoub, M1 Computer science UniCA, on factorization of sums of cycles, with Adrien, Christophe and Florian (2 months), 2023.
  • Sami Joudet, M1 Computer science UniCA, on frustration of signed graphs, with Adrien, Christophe and Florian (2 months), 2023.
  • Emir Melliti, L3 Mathematics ENS Paris, on frustration of signed graphs, with Adrien, Christophe and Florian (2 months), 2023.


Projects

  • 2024-2027 (48 months): Partnership in HORIZON project ACANOS Application-driven Challenges for Automata Networks and Complex Systems with UNIMIB (Milano-Bicocca, IT), UNITS (Trieste, IT), AMU (Marseille, FR), UTU (Turku, FI), MACKENZIE (São Paulo, BR) and CMM (Santiago, Chile).
  • 2023-2024 (24 months): Partnership in STIC AmSud project 22-STIC-02 CAMA with Brazil and Chile. Consensus Cellular Automata Algorithms and Tie-Majority Classification
  • 2019-2023 (48+6 months): Partnership in JCJC ANR project ANR-18-CE40-0002 FANs. Foundations of Automata Networks


Publications

2024

  1. Doré, François, Enrico Formenti, Antonio E Porreca, and Sara Riva. “Decomposition and Factorisation of Transients in Functional Graphs.” Theoretical Computer Science, 2024, 114514. arXiv-link  
  2. Dmitry A. Zaitsev, Zeyu Zhou, Tatiana R. Shmeleva, and Ding Liu. “Verification of Cryptocurrency Consensus Protocols: Reenterable Colored Petri Net Model Design.” International Journal of Parallel, Emergent and Distributed Systems 39, no. 1 (2024): 32–50.

2023

  1. Crespelle, Christophe, Pål Grønås Drange, Fedor V Fomin, and Petr Golovach. “A Survey of Parameterized Algorithms and the Complexity of Edge Modification.” Computer Science Review 48 (2023): 100556. arXiv-link  
  2. Dennunzio, Alberto, Enrico Formenti, and Luciano Margara. “An Easy to Check Characterization of Positive Expansivity for Additive Cellular Automata Over a Finite Abelian Group.” IEEE Access, 2023. arXiv-link  
  3. Dennunzio, Alberto, Enrico Formenti, Luca Manzoni, Luciano Margara, and Giuliamaria Menara. “A Topology for P-Systems with Active Membranes.” J. Membr. Comput. 5, no. 4 (2023): 193–204.
  4. Dennunzio, Alberto, Enrico Formenti, Luciano Margara, and Sara Riva. “An Algorithmic Pipeline for Solving Equations over Discrete Dynamical Systems Modelling Hypothesis on Real Phenomena.” Journal of Computational Science 66 (2023): 101932. arXiv-link  
  5. Aracena, Julio, Florian Bridoux, Luis Gómez, and Lilian Salinas. “Complexity of Limit Cycles with Block-Sequential Update Schedules in Conjunctive Networks.” Natural Computing, 2023, 1–19. arXiv-link  
  6. Aracena, Julio, Adrien Richard, and Lilian Salinas. “Synchronizing Boolean Networks Asynchronously.” Journal of Computer and System Sciences 136 (2023): 249–79. arXiv-link  
  7. Bridoux, Florian, 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 (December 2023): 103458. DOI-link   arXiv-link  
  8. Naldi, Aurélien, Adrien Richard, and Elisa Tonello. “Linear Cuts in Boolean Networks.” Natural Computing, 2023, 1–21. arXiv-link  
  9. Richard, Adrien, and Elisa Tonello. “Attractor Separation and Signed Cycles in Asynchronous Boolean Networks.” Theoretical Computer Science, 2023, 113706. arXiv-link  
  10. Zaitsev, Dmitry. “Sleptsov Net Computing Resolves Problems of Modern Supercomputing Revealed by Jack Dongarra in His Turing Award Talk in November 2022.” International Journal of Parallel, Emergent and Distributed Systems 38, no. 4 (2023): 275–79.
  11. Zaitsev, Dmitry A, Tatiana R Shmeleva, Qing Zhang, and Hongfei Zhao. “Virtual Machine and Integrated Developer Environment for Sleptsov Net Computing.” Parallel Processing Letters, 2023, 2350006.
  12. Martin, Bruno. “Randomness Quality and Trade-Offs for CA Random String Generators.” In Reachability Problems, edited by O. Bournez, E. Formenti, and I. Potapov, 3–12. Springer Nature Switzerland, 2023.
  13. Formenti, Enrico, Sylvain Sené, and Guillaume Theyssier, eds. Current Trends in Cellular Automata and Automata Networks. Vol. 22. Natural Computing. Springer, 2023. DOI-link   PDF-link
  14. Bournez, Olivier, Enrico Formenti, and Igor Potapov. Reachability Problems: 17th International Conference, RP 2023, Nice, France, October 11–13, 2023, Proceedings. Vol. 14235. Springer Nature, 2023.


Seminars

To subscribe, please email Adrien RICHARD at <surname at unice dot fr>.

  • January 9, 2025, 14h00 at I3S (007)
    ‘‘‘À la Rice’ complexity bounds for finite dynamical systems’‘
    by Aliénor Goubault-larrecq (LIS, AMU)
    See abstract

    Given a question ϕ on the form of a First-Order (FO) or Monadic Second-Order Logic (MSO) formula, if we consider the dynamics of a fixed Automata Network belonging to one of certain families of Automata Networks (determinist in the FO case, or bounded tree-width non-deterministic in the MSO case), knowing whether the dynamics verifies ϕ or not has been proven to be either solvable in constant time or NP-hard or coNP-hard by Gamard, Guillon, Perrot and Theyssier. It established 'à la Rice' lower complexity bounds, stating that every non-trivial question is hard from the perspective of algorithmic complexity. The question is how to extend these results to other families of Automata Networks. In this talk, we will present some tools used to extend the results to deterministic Automata Networks over MSO formulas, and how the extension to q-uniform Automata Networks is possible.

  • November 28, 2024, 14h00 at I3S (007)
    ‘‘Dynamic of threshold automata over signed undirected graphs’‘
    by Eric Goles (Universidad Adolfo Ibáñez, Chile)
    See abstract

    Given a threshold automata network, I present an index which allows to discriminate whether a class of iterations ( in particular the parallel one) only leads to fixed points or cycles appear.

  • November 14, 2024, 14h00 at I3S (007)
    ‘‘Complexity of the resolution of univariate polynomial equations over finite discrete dynamical systems’‘
    by Marius Rolland (LIS, AMU)
    Slides: PDF
    See abstract

    The computational complexity of the resolution of polynomial equations of the form P(X) = B in the semiring of finite discrete dynamical system (FDDS) is largely open. Indeed, even if we have already shown that this is NP-hard in the general case, we do not have such a result when the number of variables in the equation is bounded, irrespective of the value of the bound. Even worse, this is also the case for monomial equations. In other words, we do not know the complexity of the resolution of the equation AX^k = B. Nevertheless, recent results prove that solving A X^k = B is in polynomial time if the solution respects certain conditions like connectivity. Also, it is proved that the resolution of A X = B is in polynomial time if A is cancellable (contains a connected component with a fixed point). Common features of these kinds of equations are that they are univariate and their number of solutions is at most one. For this reason, we would like to know if the following assertion is correct: if the number of solutions of the equation P(X) = B is at most one then we can solve it in polynomial time. A first step towards an answer is proving that this property is verified in the case of injective polynomial functions, and I will prove this result in this talk.

  • November 7, 2024, 14h00 at I3S (308)
    ‘‘Divisor of Sum of Cycles’‘
    by Ha Duong PHAN (Institut de Mathématiques de l’Académie des Sciences et Technologies du Vietnam)
    Slides: PDF
    See abstract

    We investigate questions related to the divisors of a graph that can be represented as a sum of cycles. Initially, we focus on cases where the cycle lengths are powers of the same prime number. Subsequently, we generalize this problem by employing a recurrence method based on the number of distinct prime factors appearing in the cycles. We provide polynomial time algorithms to determine whether a sum of divisors is a divisor of another and analyze the complexity.

  • July 4, 2024, 14h00 at I3S (007)
    ‘‘Our talks on the semiring of functional digraphs, for AUTOMATA’24’‘
    by François Doré and Adrien Richard (MC3)

  • June 13, 2024, 14h00 at I3S (007)
    ‘‘Qu’est-ce qu’un réseau Booléen ?’‘
    by Maximilien Gadouleau (Durham, UK)
    Slides: PDF
    See abstract

    Les réseaux Booléens modélisent des réseaux d’interaction, où chaque entité a un état Booléen et une fonction Booléenne qui met à jour ce dernier. On peut voir un réseau Booléen de plusieurs façons différentes, chacune amenant des questions et des constructions intéressantes ; c’est sans doute l’un des aspects les plus excitants de la recherche dans ce domaine. Dans cet exposé, nous donnerons un aperçu de certaines de ces visions : un réseau Booléen est une transformation de l’ensemble {0,1}^n, de l’hypercube de dimension n, du treillis Booléen de hauteur n, de l’espace vectoriel GF(2)^n, ou même du corps fini GF(2^n)... Aucune connaissance préalable des réseaux Booléens n’est requise.

  • March 28, 2024, 14h00 at I3S (007)
    ‘‘Développement d’un protocole pour l’échange de clé quantique et intégration à une bibliothèque’‘
    by Thomas Prévost (MC3)
    See abstract

    Le projet consiste à développer un protocole pour étendre la portée des systèmes d'échange de clé quantiques. Ces derniers étant limités à environ 100 km, nous souhaitons mettre en place un système de relais qui permettrait de faire passer des morceaux de clé cryptographique au travers de plusieurs liens quantiques en parallèle. Finalement les utilisateurs pourront reconstruire une clé cryptographique commune à partir des morceaux qu'ils ont reçu des différents relais. Nous souhaiterions enfin proposer une vérification formelle du protocole cryptographique, puis une intégration de ce dernier à une bibliothèque logicielle afin de proposer une encapsulation transparente pour l'utilisateur.

  • Fabryary 8, 2024, 16h00 at I3S (007)
    ‘‘Well distributed occurrences property in infinite words’‘
    by Svetlana Puzynina (Saint Petersburg State University)
    See abstract

    In this talk, I will present a new abelian-type property of infinite words, so-called well distributed occurrences property. We will discuss how infinite words satisfying this property can be used to produce aperiodic pseudorandom number generators with good statistical behavior. We study the well distributed occurrences property for certain families of infinite words including words generated by morphisms, Sturmian words and Arnoux–Rauzy words.

  • September 28, 2023, 15h30 at I3S (007)
    ‘‘Community detection in directed graphs using stationary distribution and hitting times methods (with Tien Dat Dang, Duy Hieu Do)’‘
    by Ha Duong PHAN (Institut de Mathématiques de l’Académie des Sciences et Technologies du Vietnam)
    See abstract

    Community detection has been extensively developed using various algorithms. One of the most powerful algorithms for undirected graphs is Walktrap, which determines the distance between vertices by employing random walk and evaluates clusters using modularity based on vertex degrees. Although several directions have been explored to extend this method to directed graphs, none of them have been effective. In this paper, we investigate the Walktrap algorithm (Pons and Latapy in J Graph Algorithms Appl 10:191–218, 2006) and the spectral method (Newman in Phys Rev E 88:042822, 2013) and extend them to directed graphs. We propose a novel approach in which the distance between vertices is defined using hitting time, and modularity is computed based on the stationary distribution of a random walk. These definitions are highly effective, as algorithms for hitting time and stationary distribution have been developed, allowing for good computational complexity. Our proposed method is particularly useful for directed graphs, with the well-known results for undirected graphs being special cases. Additionally, we utilize the spectral method for these problems, and we have implemented our algorithms to demonstrate their plausibility and effectiveness.

  • Fabruary 2, 2023, 14h00 at I3S (007)
    ‘‘Verification of Square Lattices with Various Neighborhoods by Infinite Petri Nets’‘
    by Tatiana R. Shmeleva (MC3)
    See abstract

    Different types of square lattice abstract structures with various neighborhoods and edge conditions are basic constructs in many real-life areas like telecommunications, computing, nanotechnologies, and biological systems. Detailed models of realistic switching devices have been built, which combine cut-through and store-and-forward modes of switching; models were studied for von Neumann's and Moore's neighborhoods. For modeling rectangular structures, the infinite Petri net models have been developed and investigated. Based on the parametric expression of square lattice models, infinite systems of linear homogenous equations have been derived. The constructed models are the place invariant Petri nets for any given size of square lattice.


Software

  • FGT : set of tools for analyzing functional graphs.


News

  • Aymeric Picard Marchetto brilliantly defended his thesis on October 22, 2024, congratulations!
  • Visit of Eric Goles (Universidad Adolfo Ibáñez, Chile), in November (3 weeks), 2024.
  • Visit of Ha Duong Phan (Institut de Mathématiques de l’Académie des Sciences et Technologies du Vietnam), in November (3 weeks), 2024.
  • Enrico is organizing CCC 2024 associated with “Journée du GT Calculabilités” in Nice, September 30 - October 4, 2024.
  • Sandrine is organizing the 19e Journées Montoises d’Informatique Théorique in Nice, September 2-6, 2024.
  • Enrico is organizing MCU 2024 in Nice, June 5-7, 2024.
  • Enrico is organizing CMC 2024 in Nice, June 3-5, 2024.
  • Visit of Maximilien Gadouleau (Durham University), from June 9 to June 16, 2024.
  • Visit of Svetlana Puzynina (Saint Petersburg State University), from January 10 to February 10, 2024.
  • François Doré brilliantly defended his thesis on November 11, 2023, congratulations!
  • MDSC day, November 16, 2023, including talks by Bruno and Adrien.
  • Visit of Ha Duong Phan (Institut de Mathématiques de l’Académie des Sciences et Technologies du Vietnam), in October (2 weeks) and November (2 weeks), 2023.
  • Enrico is organizing RP’23 in Nice, October 11-13, 2023.


Credits

Site made with Jekyll from the template Hydeout and jekyll-scholar. Runs here with Github pages. To install jekyll-scholar, this post is very usefull.

This site is adapted from the site of CANA team from LIS, made with the same tools and running here with Gitlab pages; many thanks to Kévin Perrot for sharing!

For any remark concerning this page, please email Adrien RICHARD at <surname at unice dot fr>.