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

PhD students

Past members

Past Non-permanent team members

Past PhD students

  • François Doré, PhD with Enrico Formenti.
    (MESR/EDSTIC-UniCA funding, 2020-2023).

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>.

  • 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

  • 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>.