Welcome to the webpage of the CANA team
from Laboratoire d’Informatique et Systèmes (UMR CNRS 7020).

Natural Computation research group


Natural computation is a field of computer science. It is based on the links between informatics and other disciplines, mainly physics and biology. On the one hand, it aims at abstracting natural phenomena in order to develop new computational paradigms, or deepening the study of well-known nature-inspired models of computation. On the other hand, it aims at using these models of computation in order to achieve a better understanding of the phenomena at hand, with the hope to unravel some of the underlying fundamental laws.

The CANA research group (CANA is for ‘‘CAlcul NAturel’’, a French acronym for natural computation), in particular, seeks to capture at the formal level some of the fundamental paradigms of theoretical biology and physics, via the models and approaches of theoretical computer science and discrete mathematics. These approaches and their underlying methods, that we develop also per se, rest on the study of interacting entities. Most often in the models that we study, each of the constitutive entities is elementary and can only take a finite number of states. Moreover, they interact only locally with respect to the network on which they lie in discrete time steps. In spite of their apparent simplicity, these discrete models are able to capture the essence of the dynamics of numerous natural systems, upon which they shed a new light. For instance, thanks to their high level of abstraction, these models provide a qualitative representation of biological regulation networks, of particle propagation in quantum physics, or even of the emergence of waves in sandpiles. Beyond their ability to grasp natural phenomena, the models are also being studied for their own sake, in terms of their intrinsic dynamical, computability and complexity properties.

To define nature-inspired discrete models; to demonstrate their relevance; to tame the complex behaviours that they generate by means of rigorous mathematical results; to use this to better understand real systems: these are the main concerns of CANA research team.

Depending on the situation, the important features of the model can be of static (syntactic) or dynamical (semantic) nature. Moreover, the network of entities may be regular or not, the interaction rules may be deterministic, probabilistic, synchronous or asynchronous… We study these models and their variations both for their representational and computational abilities.

The methods used come from discrete dynamical system theory, combinatorics, complexity and computability theories, and non-monotonic logic, linear algebra, and quantum information.


(Non-)deterministic, probabilistic or quantum discrete dynamical systems;
Interaction networks: automata networks, cellular automata, sandpiles;
Inspirations from and applications to molecular biology, medicine and physics.


Permanent team members

PhD students

Non-permanent team members

Associate team members

  • Adrien Richard, chargé de recherches CNRS, I3S, Nice Sophia Antipolis, France.

Past members

Past permanent members

  • 2014-2020 – Pablo Arrighi, professeur des universités, now member of the LMF (Saclay).

Past PhD students

  • 2018-2021 (38 months) – Martín Ríos Wilson, PhD with Sylvain and Guillaume Theyssier on the French side, and Alejandro Maass and Eric Goles on the Chilean side (Chilean funding, 2018-2021). Currently on a postdoc position at the University Adolfo Ibañez, Santiago, Chile.
  • 2016-2021 (50 months) – Cédric Bérenger, PhD with Kévin and Peter Niebert (MESR/ED184 funding, 2016-2021). Currently R&D engineer in embedded systems at CB-Embedded, Marseille.
  • 2017-2021 (40 months) – Pacôme Perrotin, PhD with Kévin and Sylvain (MESR/ED184 funding, 2017-2021). Currently ATER at LIS, Marseille.
  • 2016-2019 (38 months) – Ivan Márquez Martín, PhD with Giuseppe and Pablo (Spanish funding, 2016-2019). Currently cybersecurity consultant at Evolutio Empowering the Cloud, Madrid.
  • 2016-2019 (32 months) – Florian Bridoux, PhD with Sylvain, Guillaume Theyssier and Adrien Richard (MESR/Labex Archimède funding, 2016-2019). Currently on a postdoc position at GREYC at the University of Caen-Normandie, Caen.
  • 2015-2018 (38 months) – Jose Luis Vilchis Medina, PhD with Pierre and Andrei Doncescu (Mexican funding, 2015-2018). Currently maître de conférences à l’École navale de Brest.

Past other non-permanent team members

  • 2020-2021 (12 months) – Étienne Moutot, postdoc with Giuseppe and Pablo (John Templeton QISS project funding). Currently chargé de recherche CNRS at I2M, Marseille.
  • 2019-2021 (22 months) – Guilhem Gamard, postdoc with Sylvain (ANR FANs funding). Currently maître de conférences at LORIA at the University of Lorraine, Nancy.
  • 2019-2021 (24 months) ‐- Florian Bridoux, ATER.
  • 2018-2019 (12 months) – Jose Luis Vilchis Medina, ATER.
  • 2016-2017 (12 months) – Timo Jolivet, postdoc with Sylvain (Labex Archimède funding). Currently full-time musician, Marseille.
  • 2015-2018 (36 months) – Stefano Facchini, postdoc with Pablo (12 months, Labex Archimède funding) then ATER (24 months). Currently Research Fellow at Queen Square Institute of Neurology of the University College of London.
  • 2013-2014 (6 months) ‐ Pierre-Étienne Meunier, postdoc with Sylvain (LIF funding). Currently CSO of Albedo Énergie, Paris.

Past graduate students


  • Mathieu Roget, 4th year of Computer science ENS Lyon (long research project), on rigourous study of a faut tolerant quantum search, with Giuseppe (3 months).


  • Lucas Venturini, 4th year of Computer science ENS Lyon (long research project), on deterministic periodic update of Boolean automata networks, with Kévin and Sylvain (5 months).
  • Johan Couturier, M2 Computer science and discrete mathematics AMU, on algebraic decomposition of finite dynamical systems, with Antonio (4 months).
  • Mathieu Roget, M2 Computer science ENS Lyon, on new statistical trade-off for quantum perceptron, with Giuseppe and Hachem Kadri (5 months).
  • Thomas Usimaki, M2 Computer science and discrete mathematics AMU, on building graphs states in optimal time, with Giuseppe and Alan Gardin (4 months).
  • Julien Zylberman, M2 Physics ENS Paris, on relativistic fluido-dynamics on quantum computer, with Giuseppe and Nuno Loureiro (5 months)


  • Odilon Duranthon, M2 Physics ENS Paris, on coarse-graining maps over quantum cellular automata, with Giuseppe (5 months).
  • Caroline Gaze-Maillot, M2 Computer science and discrete mathematics AMU, on semiring of dynamical systems, with Antonio (4 months).
  • Basile Herzog, M2 Physics Sorbonne, on non-linear quantum walks applied to quantum algorithmics, with Giuseppe (4 months).
  • Leo Kammerlocher, M2 Computer science and discrete mathematics AMU, on randomisation in symplectic and non reversible cellular automata, with Giuseppe, Nathanaël and Guillaume Theyssier (5 months).
  • Sokratis Varelogiannis, M2 Polytechnique, on Quantum walks for the Grover search, with Giuseppe and Pablo (3 months).
  • Marin Costes, M1 Computer science ENS Paris-Saclay, on Gauge-invariant CA, with Giuseppe, Nathanaël and Pablo (3 months).
  • Smith-Etchanm Djamoura, M1 Polytech Sophia, on predicting 1D sandpiles, with Kévin and Enrico Formenti (2 months).


  • Balthazar Casalé M2 Computer science AMU, on quantum bandit problem, with Giuseppe and Hachem Kadri (5 months).
  • Nathanaël Eon, M2 ECM, on non-Abelian gauge invariant cellular automata, with Giuseppe and Pablo (5 months).
  • Alan Gardin, M2 IMT Atlantique, on two-interacting-quantum walkers, with Giuseppe (4 months).
  • Karmouda Ouafae, M2 Computer science AMU, on learning algorithms for separability and entanglement detection, with Giuseppe and Hachem Kadri (5 months).
  • Kevissen Sellapillay, M2 Physics ENS Paris, on general covariant quantum walks, with Giuseppe, Ivan, and Pablo (5 months).
  • Julien Aguero, M1 Physics AMU, on two-interacting-quantum walkers, with Giuseppe and Ivan (2 months).
  • Maxime Gabiot, M1 Computer science AMU, on gravity-like cellular automata, with Giuseppe and Antonio (2 months).
  • Caroline Gaze, M1 Computer science AMU, on limit cycle complexity problems in Boolean automata networks, with Kévin and Sylvain (2 months).
  • Stephane Guilliet, M1 Physics AMU, on natural occurring research algorithm, with Giuseppe and Pablo (2 months).
  • Mathieu Vallet, M1 Computer science AMU, on Kinkdomino game, with Kévin (2 months).
  • Lucas Venturini, M1 Computer science ENS Lyon, on update schedules, with Kévin and Sylvain (3 months).


  • Nicolas Durbec, M2 Computer science AMU, on causal graph dynamics, with Pablo (6 months).


  • Talia Lacombe, M2 Computer science AMU, on parallel symmetric sandpiles, with Kévin and Sylvain (6 months).
  • Pacôme Perrotin, M2 Computer science AMU, on compositionnality of Boolean automata networks, with Kévin and Sylvain (6 months).
  • Nicolas Durbec, M1 Computer science AMU, on fixed point complexity problems in Boolean automata networks, with Kévin (2 months).
  • Noé Goudian, M1 Computer science AMU, on causal graph dynamics, with Pablo (2 months).
  • Hà Nguyen, M1 Computer science ENS Lyon, on sandpile crossings, with Kévin (3 months).
  • Abderrahim Radoua, M1 Computer science AMU, on Secure Exchange Protocol, with Kévin and Pablo (3 months).


  • Florian Bridoux, M2 Info Univ. Orléans, on intrinsic simulations of Boolean automata networks, with Kévin, Sylvain, and Pierre Guillon (6 months).


  • Aurore Alcolei, M2 Computer science ENS Lyon, on non-monotone asynchronous Boolean automata networks, with Kévin and Sylvain (6 months).
  • Bastien Rulat, M2 Computer science AMU, on chip firing game dynamics, with Kévin and Sylvain (4 months).
  • Michaël Dubuis, M1 Computer science AMU, on Secure Exchange Protocol, with Kévin and Pablo (2 months).
  • Julien Prudhomme, M1 Computer science AMU, on Secure Exchange Protocol, with Kévin and Pablo (2 months).


  • Michaël Blanc, M2 Computer science AMU, on exponential paths of non-monotone Boolean automata networks, with Pierre-Étienne and Sylvain (6 months).


  • 2022-2028 (72 months) : Local coordination of ANR PIA3 PEPR EPiQ Etude de la pile quantique : algorithmes, modèles de calcul et simulation pour l’informatique quantique
  • 2021 (12 months) : Coordination of INS2I project with I2M Fault Invariant Distributed Quantum Algorithms
  • 2020-2022 (36 months) : Partnership in ECOS-Sud project C19E02 SyDySys
    with Chile. Symbolic dynamical systems: a dialog between finite and infinite
  • 2019-2023 (48+6 months): Coordination of ANR project ANR-18-CE40-0002 FANs. Foundations of Automata Networks
  • 2019-2022 (48 months): Partnership in John Templeton Foundation Large Grant #61466 QISS. The Quantum Information Structure of Spacetime
  • 2019-2021 (36 months): Partnership in ANR project ANR-19-CE23-0011 QuantML. Quantum Machine Learning: Foundations and Algorithms
  • 2019-2020 (24 months): French coordination of STIC AmSud project 19-STIC-03 (Campus France 43478PD) CoDANet with Brazil and Chile.
    Computation and Dynamics of Deterministic Automata Networks
  • 2019-2020 (18 months): Coordination of Amidex (pépinière d’excellence 2018) project DQTS. Discrete Time Quantum Simulator
  • 2018-2020 (36 months): Coordination of CNRS PICS project GQS with Spain.
    Geometry and Quantum Simulation
  • 2018-2020 (24 months): Partnership in ECOS-Sud project A17C03 QuCA
    with Argentina. Quantum Calculi
  • 2018 (12 months): Coordination of CNRS INFINITI 2018 project LQST.
    Lattice Quantum Simulation Theory
  • 2017-2025 (108 months): Partnership in ANR convergences project
    ANR-16-CONV-00001 CENTURI. Turing centre for living systems
  • 2017-2019 (36 months): French coordination of ECOS-Sud project
    C16E01 ANipad with Chile. Automata Networks: Inverse Problem and Dynamics
  • 2017-2018 (24 months): Coordination of IXXI project SSE
    Sharing the ‘‘sharing economy’’
  • 2017 (12 months): Coordination of CNRS PEPS JCJC INS2I project CGETA
    Graph Compression with Efficient Algorithmic Complexity
  • 2017 (12 months): Coordination of CNRS PEPS JCJC INS2I project QNG
    Quantum Networks and Growing
  • 2017 (6 months): Coordination of AMU Labex Archimède software development project SXP. Secure eXchange Protocol
  • 2016-2018 (24 months): Partnership in Stic-AmSud project 16-STIC-05 FoQCoSS with Argentina. Foundations of Quantum Computation: Syntax and Semantics
  • 2015-2018 (36 months): Coordination of PACA project FRI-2015_01134.
    Interaction Network foundations
  • 2012-2016 (48 months): Partnership in ANR project ANR-12-BS02-0007 TARMAC. Theory of AlgoRithms: Machines, completeness, Axiomatization and physical Constraints



  1. Bridoux, Florian, 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 (June 2022): 138–64. DOI-link   arXiv-link  
  2. Sellapillay, Kevissen, Pablo Arrighi, and Giuseppe Di Molfetta. “A Discrete Relativistic Spacetime Formalism for 1+1-QED with Continuum Limits.” Scientific Reports 12 (February 2022): 2198. DOI-link   arXiv-link  
  3. Perrot, Kévin. “Études De La Complexité Algorithmique Des Réseaux d’Automates.” Aix-Marseille Université, January 2022. Habilitation à diriger des recherches.   PDF-link
  4. Arrighi, Pablo, Giuseppe Di Molfetta, and Nathanaël Eon. “Gauge-Invariance in Cellular Automata.” Natural Computing, January 2022. DOI-link   arXiv-link  
  5. Bridoux, Florian. “Sequentialization and Procedural Complexity in Automata Networks.” Theoretical Computer Science 898 (January 2022): 92–109. DOI-link   PDF-link


  1. Goles, Eric, Diego Maldonado, Pedro Montealegre, and Martín Ríos Wilson. “On the Complexity of Asynchronous Freezing Cellular Automata.” Information and Computation 281 (December 2021): 104764. DOI-link   arXiv-link  
  2. Goles, Eric, Andrew Adamatzky, Pedro Montealegre, and Martín Ríos Wilson. “Generating Boolean Functions on Totalistic Automata Networks.” International Journal of Unconventional Computing 16 (November 2021): 343–91. arXiv-link  
  3. Kari, Jarkko, and Étienne Moutot. “Decidability and Periodicity of Low Complexity Tilings.” Theory of Computing Systems, October 2021. DOI-link   arXiv-link  
  4. Arrighi, Pablo, Marin Costes, and Nathanäel Eon. “Universal Gauge-Invariant Cellular Automata.” In Proceedings of MFCS’21, 202:9:1–9:14. LIPIcs. Schloss Dagstuhl Publishing, 2021. DOI-link   arXiv-link   PDF-link
  5. Perrot, Kévin, Pacôme Perrotin, and Sylvain Sené. “On Boolean Automata Networks (De)Composition.” Fundamenta Informaticae 181 (August 2021): 163–88. DOI-link   PDF-link
  6. Goles, Eric, Pedro Montealegre, Martín Ríos Wilson, and Guillaume Theyssier. “On the Impact of Treewidth in the Computational Complexity of Freezing Dynamics.” In Proceedings of CiE’21, 12813:260–72. LNCS. Springer, 2021. DOI-link   arXiv-link  
  7. Paulevé, Loïc, and Sylvain Sené. “Non-Deterministic Updates of Boolean Networks.” In Proceedings of AUTOMATA’21, 90:10:1–10:16. OASIcs. Schloss Dagstuhl Publishing, 2021. DOI-link   arXiv-link  
  8. Castillo-Ramirez, Alonso, Pierre Guillon, and Kévin Perrot, eds. Proceedings of AUTOMATA’21. Vol. 90. OASIcs. Schloss Dagstuhl Publishing, 2021.
  9. Durbec, Amélia. “Graph Subshifts.” In Proceedings of AUTOMATA’21 (Exploratory Papers), 4:1–4:11, 2021. PDF-link
  10. Perrotin, Pacôme. “Associating Parallel Automata Network Dynamics and Strictly One-Way Cellular Automata.” In Proceedings of AUTOMATA’21 (Exploratory Papers), 8:1–8:15, 2021. PDF-link
  11. Ríos Wilson, Martín. “On Automata Networks Dynamics: an Approach Based on Computational Complexity Theory.” PhD thesis, Aix-Marseille Université & Universidad de Chile, 2021. PDF-link
  12. Goles, Eric, Pedro Montealegre, and Kévin Perrot. “Freezing Sandpiles and Boolean Threshold Networks: Equivalence and Complexity.” Advances in Applied Mathematics 125 (April 2021): 102161. DOI-link   arXiv-link  
  13. Duranthon, Odilon, and Giuseppe Di Molfetta. “Coarse-Grained Quantum Cellular Automata.” Physical Review A 103 (March 2021): 032224. DOI-link   arXiv-link  
  14. Gamard, Guilhem, Pierre Guillon, Kévin Perrot, and Guillaume Theyssier. “Rice-like Theorems for Automata Networks.” In Proceedings of STACS’21, 187:32:1–32:17. LIPIcs. Schloss Dagstuhl Publishing, 2021. DOI-link   PDF-link
  15. Perrot, Kévin, Pacôme Perrotin, and Sylvain Sené. “Optimising Attractor Computation in Boolean Automata Networks.” In Proceedings of LATA’21, 12638:68–80. LNCS. Springer, 2021. DOI-link   arXiv-link  
  16. Manighalam, Michael, and Giuseppe Di Molfetta. “Continuous Time Limit of the DTQW in 2D+1 and Plasticity.” Quantum Information Processing 20 (February 2021): 76. DOI-link   arXiv-link  
  17. Bridoux, Florian, Caroline Gaze-Maillot, Kévin Perrot, and Sylvain Sené. “Complexity of Limit-Cycle Problems in Boolean Networks.” In Proceedings of SOFSEM’21, 12607:135–46. LNCS. Springer, 2021. DOI-link   arXiv-link  
  18. Perrotin, Pacôme. “Simulation Entre Modèles De Calcul Naturel Et Modularité Des Réseaux d’Automates.” PhD thesis, Aix-Marseille Université, 2021. PDF-link
  19. Bérenger, Cédric. “Grands Réseaux Maillés Basse Énergie: Protocoles Minimalistes Pour La Synchronisation, La Mesure De Distance Et Le Partitionnement.” PhD thesis, Aix-Marseille Université, 2021.


  1. Di Molfetta, Giuseppe. “Quantum Walks, Limits and Transport Equations.” Aix-Marseille Université, December 2020. Habilitation à diriger des recherches.   PDF-link
  2. Bridoux, Florian, Maximilien Gadouleau, and Guillaume Theyssier. “Expansive Automata Networks.” Theoretical Computer Science 843 (December 2020): 25–44. DOI-link   arXiv-link  
  3. Roget, Mathieu, Basile Herzog, and Giuseppe Di Molfetta. “Quantum Control Using Quantum Memory.” Scientific Reports 10 (December 2020): 21354. DOI-link   arXiv-link  
  4. Perrot, Kévin, and Éric Rémila. “On the Emergence of Regularities on One-Dimensional Decreasing Sandpiles.” Theoretical Computer Science 843 (December 2020): 1–24. DOI-link  
  5. Leporati, Alberto, Luca Manzoni, Mauri Giancarlo, Antonio E. Porreca, and Claudio Zandron. “Simulating Counting Oracles with Cooperation.” Journal of Membrane Computing 2 (December 2020): 303–10. DOI-link   PDF-link
  6. Di Molfetta, Giuseppe, and Basile Herzog. “Searching via Nonlinear Quantum Walk on the 2D-Grid.” Algorithms 13 (November 2020): 305. DOI-link   arXiv-link  
  7. Goles, Eric, Pedro Montealegre, and Martín Ríos Wilson. “On the Effects of Firing Memory in the Dynamics of Conjunctive Networks.” Discrete and Continuous Dynamical Systems 40 (October 2020): 5765–93. DOI-link   PDF-link
  8. Ferretti, Claudio, Alberto Leporati, Luca Manzoni, and Antonio E. Porreca. “The Many Roads to the Simulation of Reaction Systems.” Fundamenta Informaticae 171 (October 2020): 175–88. DOI-link   arXiv-link  
  9. Perrot, Kévin, Pacôme Perrotin, and Sylvain Sené. “On the Complexity of Acyclic Modules in Automata Networks.” In Proceedings of TAMC’20, 12337:168–80. LNCS. Springer, 2020. DOI-link   arXiv-link  
  10. Balbi, Pedro P., 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’20, 12286:14–28. LNCS. Springer, 2020. DOI-link   arXiv-link  
  11. Manzoni, Luca, Antonio E. Porreca, and Grzegorz Rozenberg. “Facilitation in Reaction Systems.” Journal of Membrane Computing 2 (October 2020): 149–61. DOI-link   PDF-link
  12. Ruivo, Eurico L. P., 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 274 (October 2020): 104538. DOI-link  
  13. Formenti, Enrico, and Kévin Perrot. “How Hard Is It to Predict Sandpiles on Lattices? A Survey.” Fundamenta Informaticae 171 (October 2020): 189–219. DOI-link   arXiv-link  
  14. Bridoux, Florian, Maximilien Gadouleau, and Guillaume Theyssier. “Commutative Automata Networks.” In Proceedings of AUTOMATA’20, 12286:43–58. LNCS. Springer, 2020. DOI-link   arXiv-link  
  15. Casalé, Balthazar, Giuseppe Di Molfetta, Hachem Kadri, and Liva Ralaivola. “Quantum Bandits.” Quantum Machine Intelligence 2 (August 2020): 11. DOI-link   arXiv-link  
  16. Nguyen, Viet-Ha, Kévin Perrot, and Mathieu Vallet. “NP-Completeness of the Game Kingdomino TM.” Theoretical Computer Science 822 (June 2020): 23–35. DOI-link   arXiv-link  
  17. Bridoux, Florian, Maximilien Gadouleau, and Guillaume Theyssier. “On Simulation in Automata Networks.” In Proceedings of CiE’20, 12098:277–88. LNCS. Springer, 2020. DOI-link   arXiv-link  
  18. Perrot, Kévin, Sylvain Sené, and Lucas Venturini. “#P-Completeness of Counting Update Digraphs, Cacti, and Series-Parallel Decomposition Method.” In Proceedings of CiE’20, 12098:326–38. LNCS. Springer, 2020. DOI-link   arXiv-link  
  19. Bridoux, Florian, Alonso Castillo-Ramirez, and Maximillien Gadouleau. “Complete Simulation of Automata Networks.” Journal of Computer and System Sciences 109 (May 2020): 1–21. DOI-link   arXiv-link  
  20. Roget, Mathieu, Stéphane Guillet, Pablo Arrighi, and Giuseppe Di Molfetta. “Grover Search as a Naturally Occurring Phenomenon.” Physical Review Letters 124 (May 2020): 180501. DOI-link   arXiv-link  
  21. Goles, Eric, Fabiola Lobos, Gonzalo A. Ruz, and Sylvain Sené. “Attractor Landscapes in Boolean Networks with Firing Memory.” Natural Computing 19 (May 2020): 295–319. DOI-link   PDF-link
  22. Arnault, Pablo, Adrian Macquet, Andreu Anglès Castillo, Iván Márquez Martín, Vicente Pina Canelles, Armando Pérez, Giuseppe Di Molfetta, Pablo Arrighi, and Fabrice Debbasch. “Quantum Simulation of Quantum Relativistic Diffusion via Quantum Walks.” Journal of Physics A: Mathematical and Theoretical 53 (April 2020): 205303. DOI-link   arXiv-link  
  23. Jnane, Hamza, Giuseppe Di Molfetta, and Filippo M. Miatto. “Growing Random Graphs with Quantum Rules.” In Proceedings of QSQW’20, 315:38–47. EPTCS, 2020. DOI-link   arXiv-link  
  24. Di Molfetta, Giuseppe, Vivien Kendon, and Yutaka Shikano, eds. Proceedings of QSQW’20. Vol. 315. EPTCS, 2020. arXiv-link  
  25. Leporati, Alberto, Luca Manzoni, Mauri Giancarlo, Antonio E. Porreca, and Claudio Zandron. “A Turing Machine Simulation by P Systems without Charges.” Journal of Membrane Computing 2 (February 2020): 71–79. DOI-link   arXiv-link  
  26. ———. “Shallow Laconic P Systems Can Count.” Journal of Membrane Computing 2 (February 2020): 49–58. DOI-link   PDF-link
  27. Aristote, Quentin, Nathanaël Eon, and Giuseppe Di Molfetta. “Dynamical Triangulation Induced by Quantum Walk.” Symmetry 12 (January 2020): 128. DOI-link   arXiv-link  
  28. Arrighi, Pablo, Simon Martiel, and Simon Perdrix. “Reversible Causal Graph Dynamics: Invertibility, Block Representation, Vertex-Preservation.” Natural Computing 19 (January 2020): 157–78. DOI-link  
  29. Perrot, Kévin, 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 (January 2020): 51–90. DOI-link   PDF-link
  30. Demongeot, Jacques, and Sylvain Sené. “About Block-Parallel Boolean Networks: a Position Paper.” Natural Computing 19 (January 2020): 5–13. DOI-link   PDF-link
  31. Formenti, Enrico, and Sylvain Sené, eds. Automata Networks and Their Applications. Vol. 19. Natural Computing. Springer, 2020. DOI-link   PDF-link
  32. Arrighi, Pablo, Cédric Bény, and Terry Farrelly. “A Quantum Cellular Automaton for One-Dimensional QED.” Quantum Information Processing 19 (January 2020): 88. DOI-link   arXiv-link  
  33. Di Molfetta, Giuseppe, and Pablo Arrighi. “A Quantum Walk with Both a Continuous-Time Limit and a Continuous-Spacetime Limit.” Quantum Information Processing 19 (January 2020): 47. DOI-link   arXiv-link  


  1. Márquez Martín, Ivan. “Quantum Walks: Background Geometry and Gauge Invariance.” PhD thesis, Aix-Marseille Université & Universidad de Valencia, 2019. PDF-link
  2. Pires, Marcelo A., Giuseppe Di Molfetta, and Sílvio M. Duarte Queirós. “Multiple Transitions between Normal and Hyperballistic Diffusion in Quantum Walks with Time-Dependent Jumps.” Scientific Reports 9, no. 1 (December 2019): 19292. arXiv-link  
  3. Arrighi, Pablo, Giuseppe Di Molfetta, and Nathanaël Eon. “Non-Abelian Gauge-Invariant Cellular Automata.” In Proceedings of TPNC’19, 11934:211–21. LNCS. Springer, 2019. DOI-link   arXiv-link  
  4. Arrighi, Pablo, Simon Martiel, and Simon Perdrix. “Reversible Causal Graph Dynamics: Invertibility, Block Representation, Vertex-Preservation.” Natural Computing, October 2019. DOI-link  
  5. Vilchis Medina, José Luis, Pierre Siegel, Vincent Risch, and Andrei Doncescu. “A Resilient Behavior Approach Based on Non-Monotonic Logic.” In Proceedings of MICAI’19, 11835:403–13. LNCS. Springer, 2019. DOI-link   PDF-link
  6. Arrighi, Pablo. “An Overview of Quantum Cellular Automata.” Natural Computing 18, no. 4 (September 2019): 885–99. DOI-link   arXiv-link  
  7. Vilchis Medina, José Luis, Pierre Siegel, Vincent Risch, and Andrei Doncescu. “An Implementation of a Non-Monotonic Logic in an Embedded Computer for a Motor-Glider.” In Proceedings of ICLP’19 (Technical Communications), 306:323–29. EPTCS. Open Publishing Association, 2019. DOI-link   arXiv-link  
  8. Arrighi, Pablo, Cédric Bény, and Terry Farrelly. “A Quantum Cellular Automaton for One-Dimensional QED.” In Local Proceedings of AQIS’19, 2019. arXiv-link  
  9. Dennunzio, Alberto, Enrico Formenti, Luca Manzoni, and Antonio E. Porreca. “Complexity of the Dynamics of Reaction Systems.” Information and Computation 267 (August 2019): 96–109. DOI-link   arXiv-link  
  10. Arrighi, Pablo, Giuseppe Di Molfetta, Iván Márquez Martín, and Armando Pérez. “From Curved Spacetime to Spacetime-Dependent Local Unitaries over the Honeycomb and Triangular Quantum Walks.” Scientific Reports 9 (July 2019): 10904. DOI-link   arXiv-link  
  11. Bridoux, Florian. “Simulations Intrinsèques Et Complexités Dans Les Réseaux d’Automates.” PhD thesis, Aix-Marseille Université, 2019. PDF-link
  12. Bridoux, Florian, Nicolas Durbec, Kévin Perrot, and Adrien Richard. “Complexity of Maximum Fixed Point Problem in Boolean Networks.” In Proceedings of CiE’19, 11558:132–43. LNCS. Springer, 2019. DOI-link   PDF-link
  13. Dennunzio, Alberto, Enrico Formenti, Luca Manzoni, Luciano Margara, and Antonio E. Porreca. “On the Dynamical Behaviour of Linear Higher-Order Cellular Automata and Its Decidability.” Information Sciences 486 (June 2019): 73–87. DOI-link   arXiv-link  
  14. Arrighi, Pablo, Nicolas Durbec, and Aurélien Emmanuel. “Reversibility vs Local Creation/Destruction.” In Proceedings of RC’19, 11497:51–66. LNCS. Springer, 2019. DOI-link   arXiv-link  
  15. Leporati, Alberto, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, and Claudio Zandron. “Characterizing PSPACE with Shallow Non-Confluent P Systems.” Journal of Membrane Computing 1, no. 2 (April 2019): 75–84. DOI-link   arXiv-link  
  16. Arnault, Pablo, Armando Pérez, Pablo Arrighi, and Terry Farrelly. “Discrete-Time Quantum Walks as Fermions of Lattice Gauge Theory.” Physical Review A 99 (March 2019): 032110. DOI-link   arXiv-link  
  17. Hatifi, Mohamed, Giuseppe Di Molfetta, Fabrice Debbasch, and Marc Brachet. “Quantum Walk Hydrodynamics.” Scientific Reports 9, no. 1 (February 2019): 2989. DOI-link   PDF-link
  18. Dennunzio, Alberto, Enrico Formenti, Luca Manzoni, Luciano Margara, and Antonio E. Porreca. “Decidability of Sensitivity and Equicontinuity for Linear Higher-Order Cellular Automata.” In Proceedings of LATA’19, 11417:95–107. LNCS. Springer, 2019. DOI-link  
  19. Leporati, Alberto, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, and Claudio Zandron. “Solving QSAT in Sublinear Depth.” In Proceedings of CMC’18, 11399:188–201. LNCS. Springer, 2019. DOI-link   arXiv-link  


  1. Vilchis Medina, José Luis. “Modeling of Resilient Systems in Non-Monotonic Logic. Application to Solar Power UAV.” PhD thesis, Aix-Marseille Université, 2018. PDF-link
  2. Khaled, Tarek, Belaid Benhamou, and Pierre Siegel. “A New Method for Computing Stable Models in Logic Programming.” In Proceedings of ICTAI’18, 800–807. IEEE, 2018. DOI-link  
  3. Leporati, Alberto, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, and Claudio Zandron. “A Turing Machine Simulation by P Systems without Charges.” In Proceedings of ACMC’18, 530:213–21. CDMTCS Research Report Series, 2018. arXiv-link  
  4. Vilchis Medina, José Luis, Pierre Siegel, Vincent Risch, and Andrei Doncescu. “Intelligent and Adaptive System Based on a Non-Monotonic Logic for an Autonomous Motor-Glider.” In Proceedings of IEEE ICARCV’18, 442–47. IEEE, 2018. DOI-link  
  5. Siegel, Pierre, Andrei Doncescu, Vincent Risch, and Sylvain Sené. “Towards a Boolean Dynamical System Representation in a Nonmonotonic Modal Logic.” In Proceedings of NMR’18, 53–62, 2018. PDF-link
  6. Márquez Martín, Iván, Pablo Arnault, Giuseppe Di Molfetta, and Armando Pérez. “Electromagnetic Lattice Gauge Invariance in Two-Dimensional Discrete-Time Quantum Walks.” Physical Review A 98, no. 3 (September 2018): 032333. DOI-link   arXiv-link  
  7. Arrighi, Pablo, Giuseppe Di Molfetta, and Stefano Facchini. “Quantum Walking in Curved Spacetime: Discrete Metric.” Quantum 2 (August 2018): 84. DOI-link   arXiv-link  
  8. Bérenger, Cédric, Peter Niebert, and Kévin Perrot. “Balanced Connected Partitioning of Unweighted Grid Graphs.” In Proceedings of MFCS’18, 117:39:1–39:18. LIPIcs. DROPS, 2018. DOI-link   PDF-link
  9. Ruivo, Eurico L. P., 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 (August 2018): 209–20. DOI-link   PDF-link
  10. Demongeot, Jacques, and Sylvain Sené. “Phase Transitions in Stochastic Non-Linear Threshold Boolean Automata Networks on \MathbbZ^2: the Boundary Impact.” Advances in Applied Mathematics 98 (July 2018): 77–99. DOI-link   PDF-link
  11. Ruz, Gonzalo A., Eric Goles, and Sylvain Sené. “Reconstruction of Boolean Regulatory Models of Flower Development Exploiting an Evolution Strategy.” In Proceedings of IEEE CEC’18, 1–8. IEEE, 2018. DOI-link   PDF-link
  12. Arrighi, Pablo, Giuseppe Di Molfetta, Iván Márquez Martín, and Armando Pérez. “Dirac Equation as a Quantum Walk over the Honeycomb and Triangular Lattices.” Physical Review A 97, no. 6 (June 2018): 062111. DOI-link   arXiv-link  
  13. Di Molfetta, Giuseppe, Diogo O. Soares-Pinto, and Sílvio M. Duarte Queirós. “Elephant Quantum Walk.” Physical Review A 97, no. 6 (June 2018): 062112. DOI-link   arXiv-link  
  14. Khaled, Tarek, Belaid Benhamou, and Pierre Siegel. “Une Nouvelle Méthode De Calcul De Modèles Stables En Programmation Logique.” In Proceedings of JFPC’18), 2018. PDF-link
  15. Noual, Mathilde, and Sylvain Sené. “Synchronism versus Asynchronism in Monotonic Boolean Automata Networks.” Natural Computing 17 (June 2018): 393–402. DOI-link   PDF-link
  16. Arrighi, Pablo, Clément Chouteau, Stefano Facchini, and Simon Martiel. “Causal Dynamics of Discrete Manifolds.” In Proceedings of NCMA’18, 31–47. Österreichische Computer Gesellschaft, 2018. arXiv-link  
  17. Arrighi, Pablo, Giuseppe Di Molfetta, and Nathanaël Eon. “A Gauge-Invariant Reversible Cellular Automaton.” In Proceedings of AUTOMATA’18, 10875:1–12. LNCS. Springer, 2018. DOI-link   arXiv-link  
  18. Nguyen, Viet-Ha, and Kévin Perrot. “Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models.” In Proceedings of AUTOMATA’18, 10875:127–42. LNCS. Springer, 2018. DOI-link   arXiv-link  
  19. Perrot, Kévin, Pacôme Perrotin, and Sylvain Sené. “A Framework for (De)Composing with Boolean Automata Networks.” In Proceedings of MCU’18, 10881:121–36. LNCS. Springer, 2018. DOI-link   arXiv-link  
  20. Arrighi, Pablo, Simon Martiel, and Vincent Nesme. “Cellular Automata over Generalized Cayley Graphs.” Mathematical Structures in Computer Science 18, no. 3 (March 2018): 340–83. DOI-link   arXiv-link  
  21. Formenti, Enrico, Kévin Perrot, and Éric Rémila. “Computational Complexity of the Avalanche Problem for One Dimensional Decreasing Sandpiles.” Journal of Cellular Automata 13, no. 3 (March 2018): 215–28. arXiv-link  
  22. Goles, Eric, 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 (February 2018): 1–32. DOI-link   HAL-link   PDF-link


  1. Arrighi, Pablo, and Stefano Facchini. “Quantum Walking in Curved Spacetime: (3+1) Dimensions, and Beyond.” Quantum Information and Computation 17, no. 9-10 (August 2017): 0810–24. arXiv-link  
  2. Khaled, Tarek, Belaïd Benhamou, and Pierre Siegel. “Vers Une Nouvelle Méthode De Calcul De Modèles Stables Et Extensions En Programmation Logique.” In Proceedings of JIAF’17, 2017. PDF-link
  3. Siegel, Pierre, Andrei Doncescu, Vincent Risch, and Sylvain Sené. “Vers Une Représentation Des Systèmes Dynamiques Booléens En Logique Des Hypothèses.” In Proceedings of JIAF’17, 2017. PDF-link
  4. Vilchis Medina, José-Luis, Pierre Siegel, and Andrei Doncescu. “Pilotage Stable d’Un Planeur En Utilisant Une Logique Non Monotone.” In Proceedings of JFPDA’17, 2017. PDF-link
  5. Arrighi, Pablo, Alejandro Díaz-Caro, and Benoît Valiron. “The Vectorial λ-Calculus.” Information and Computation 254 (June 2017): 105–39. DOI-link   arXiv-link  
  6. Arrighi, Pablo, and Simon Martiel. “Quantum Causal Graph Dynamics.” Physical Review D 96, no. 2 (June 2017): 024026. DOI-link   arXiv-link  
  7. Montalva Medel, Marco, Kévin Perrot, Pedro de Oliveira, and Eurico Ruivo. “Sensitivity to Synchronism in Some Boolean Automata Networks.” In Proceedings of AUTOMATA’17 (Exploratory Papers), 2017. PDF-link
  8. Márquez Martín, Iván, Giseppe Di Molfetta, and Armando Pérez. “Fermion Confinement via Quantum Walks in (2+1)-Dimensional and (3+1)-Dimensional Space-Time.” Physical Review A 95, no. 4 (April 2017): 042112. DOI-link   arXiv-link  
  9. Perrot, Kévin, and Éric Rémila. “Strong Emergence of Wave Patterns on Kadanoff Sandpiles.” Electronic Journal of Combinatorics 24, no. 2 (April 2017): P2.4. DOI-link   PDF-link
  10. Vilchis Medina, José-Luis, Pierre Siegel, and Andrei Doncescu. “Autonomous Aerial Vehicle Based on Non-Monotonic Logic.” In Proceedings of VEHITS’17, 236–41. ScitePress, 2017. DOI-link   PDF-link
  11. Arrighi, Pablo, and Gilles Dowek. “Lineal: A Linear-Algebraic Lambda-Calculus.” Logical Methods in Computer Science 13, no. 1 (March 2017): 1–33. DOI-link   arXiv-link  
  12. Bridoux, Florian, Pierre Guillon, Kévin Perrot, Sylvain Sené, and Guillaume Theyssier. “On the Cost of Simulating a Parallel Boolean Automata Network with a Block-Sequential One.” In Proceedings of TAMC’17, 10185:112–28. LNCS. Springer, 2017. DOI-link   arXiv-link   PDF-link
  13. Arrighi, Pablo, Vincent Nesme, and Reinhard F. Werner. “Bounds on the Speedup in Quantum Signaling.” Physical Review A 95, no. 1 (January 2017): 012331. DOI-link   arXiv-link  


  1. Di Molfetta, Giuseppe, and Fabrice Debbasch. “Discrete-Time Quantum Walks in Random Artificial Gauge Fields.” Quantum Studies: Mathematics and Foundations 3 (December 2016): 293–311. DOI-link   arXiv-link  
  2. Alcolei, Aurore, Kévin Perrot, and Sylvain Sené. “On the Flora of Asynchronous Locally Non-Monotonic Boolean Automata Networks.” In Proceedings of SASB’15, 326:3–25. ENTCS. Elsevier, 2016. DOI-link   arXiv-link  
  3. Di Molfetta, Giuseppe, and Armando Pérez. “Quantum Walks as Simulators of Neutrino Oscillations in a Vacuum and Matter.” New Journal of Physics 18, no. 10 (October 2016): 103038. DOI-link   arXiv-link  
  4. Bru, Luis A., Germán J. de Valcárcel, Giuseppe Di Molfetta, Armando Pérez, Eugenio Roldán, and Fernando Silva. “Quantum Walk on a Cylinder.” Physical Review A 94, no. 3 (September 2016): 032328. DOI-link   arXiv-link  
  5. Arrighi, Pablo, Stefano Facchini, and Marcelo Forets. “Quantum Walking in Curved Spacetime.” Quantum Information Processing 15, no. 8 (August 2016): 3467–86. DOI-link   arXiv-link  
  6. Crespelle, Christophe, Tien-Nam Le, Kévin Perrot, and Thi Ha Duong Phan. “Linearity Is Strictly More Powerful than Contiguity for Encoding Graphs.” Discrete Mathematics 339, no. 8 (August 2016): 2168–77. DOI-link   arXiv-link  
  7. Melliti, Tarek, Damien Regnault, Adrien Richard, and Sylvain Sené. “Asynchronous Simulation of Boolean Networks by Monotone Boolean Networks.” In Proceedings of ACRI’16, 9863:182–91. LNCS. Springer, 2016. DOI-link   arXiv-link  
  8. Arnault, Pablo, Giuseppe Di Molfetta, Marc Brachet, and Fabrice Debbasch. “Quantum Walks and Non-Abelian Discrete Gauge Theory.” Physical Review A 94 (July 2016): 012335. DOI-link   arXiv-link  
  9. Arrighi, Pablo, Simon Martiel, and Simon Perdrix. “Reversible Causal Graph Dynamics.” In Proceedings of RC’2016, 9720:73–88. LNCS. Springer, 2016. DOI-link   arXiv-link  
  10. Nguyen, Thanh, Andrei Doncescu, and Pierre Siegel. “Performance Comparison of ADTree and Naive Bayes Algorithms for Spam Filtering.” World Academy of Science, Engineering and Technology 10, no. 5 (May 2016): 269–74. DOI-link  
  11. Arrighi, Pablo, and Gilles Dowek. “Free Fall and Cellular Automata.” In Proceedings of DCM’15, 204:1–10. EPTCS. Open Publishing Association, 2016. DOI-link   arXiv-link  
  12. Arrighi, Pablo, and Simon Perdrix. “Modèles De Calcul Quantiques.” In Informatique Mathématique - Une Photographie En 2016. CNRS Editions, 2016. PDF-link
  13. Perrot, Kévin, and Trung Van Pham. “Chip-Firing Game and Partial Tutte Polynomial for Eulerian Digraphs.” Electronic Journal of Combinatorics 23, no. 1 (March 2016): P1.57. DOI-link   arXiv-link  


  1. Arrighi, Pablo, and Gilles Dowek. “Discrete Geodesics and Cellular Automata.” In Proceedings TPNC’2015, 9477:137–49. LNCS. Springer, 2015. DOI-link   arXiv-link  
  2. Fatès, Nazim, and Sylvain Sené, eds. Automates Cellulaires Et Réseaux d’Automates : Le Rôle Central De l’Irrégularité. Vol. 35. Technique Et Science Informatiques. Lavoisier, 2015.
  3. Melliti, Tarek, Mathilde Noual, Damien Regnault, and Sylvain Sené. “Cycles, Double-Cycles d’Interactions Et Modes De Mise à Jour – Une Synthèse.” Technique Et Science Informatiques 35 (November 2015): 401–30. PDF-link
  4. Perrot, Kévin, and Éric Rémila. “Piles De Sable Décroissantes 1D : Classification Expérimentale d’Émergences.” Technique Et Science Informatiques 34, no. 4 (November 2015): 377–400. PDF-link
  5. Arrighi, Pablo, Simon Martiel, and Simon Perdrix. “Block Representation of Reversible Causal Graph Dynamics.” In Proceedings of FCT’2015, 9210:351–63. LNCS. Springer, 2015. DOI-link   PDF-link
  6. Melliti, Tarek, Mathilde Noual, Damien Regnault, Sylvain Sené, and Jérémy Sobieraj. “Asynchronous Dynamics of Boolean Automata Double-Cycles.” In Proceedings of UCNC’2015, 9252:250–62. LNCS. Springer, 2015. DOI-link   arXiv-link  
  7. Perrot, Kévin, and Éric Rémila. “Emergence on Decreasing Sandpile Models.” In Proceedings of MFCS’2015, 9234:419–31. LNCS. Springer, 2015. DOI-link   PDF-link
  8. Doncescu, Andrei, and Pierre Siegel. “Emerging Trends in Computational Biology, Bioinformatics, and Systems Biology,” 409–527. Elsevier, 2015. PDF-link
  9. Arrighi, Pablo, and Simon Perdrix. “La Décohérence, Une Alliée Pour La Simulation.” La Recherche 501-502 (July 2015): 66–68. PDF-link
  10. Crespelle, Christophe, 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, 9214:212–23. LNCS. Springer, 2015. DOI-link   arXiv-link  
  11. Perrot, Kévin, 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 (February 2015): 373–96. DOI-link   arXiv-link  


  1. Barlovatz-Meimon, Georgia, and Sylvain Sené. “Culture De Cellules Animales (3e Édition),” 217–40. Lavoisier, 2014. PDF-link
  2. Perrot, Kévin, and Éric Rémila. “Emergence of Regularities on Decreasing Sandpile Models.” In Proceedings of 15th Mons Theoretical Computer Science Days, 2014. PDF-link
  3. Doncescu, Andrei, Pierre Siegel, and Tan Le. “Representation and Efficient Algorithms for the Study of Cell Signaling Pathways.” In Proceedings of ICAI’2014, 504–10, 2014. PDF-link
  4. ———. “Relevance of Information in Cell Signaling Pathways Using Default Logic.” In Proceedings of BIOCOMP’2014, 16–22. CSREA Press, 2014. PDF-link


Subscribe to [cana-seminaire] mailing list

  • 19 juillet 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Trois exemples magiques d’algorithmes randomisés’‘
    by Kévin Perrot (LIS)
    See abstract

    1) Compter jusqu’à 10^309 sur ses 10 doigts. 2) Obtenir un multiplicateur robuste à partir d’un multiplicateur foireux. 3) Preuves à divulgation nulle de connaissance (zéro-knowledge proofs). Ces exemples sont tirés de l’article ‘Randomness + determinism = progresses: Why random processes could be favored by evolution’ par Nicolas Schabanel en 2012.

  • 28 juin 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘From global (color-blind) symmetry to local (gauge) invariance in cellular automata’‘
    by Nathanaël Eon (PhD LIS)
    See abstract

    In this talk, I will first introduce the concept of global (a.k.a. color-blind) and local (a.k.a. gauge) symmetries in cellular automata. The essence of those symmetries is for the cellular automata to be invariant under a change of the configuration, either done globally (applying the same transformation at every position) or locally (applying a different transformation at every position). Hence, a local symmetry is a priori stronger than a global one. In order to enforce the local symmetry, an extension of CA is introduced and an interesting equivalency result follows: globally symmetric CA are exactly those which can be extended into locally invariant ones (through a specific extension). Such result makes formal a folklore perspective in Physics which says that any local symmetry necessarily arise from an already existing global one. I will then provide two constructive proofs of universality for locally invariant cellular automata. The results provided in this talk can be found on arXiv:2102.06912.

  • 21 juin 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Influence: a partizan scoring game on graphs’‘
    by Éric Rémila (GATE LSE)
    See abstract

    We introduce the game influence, a scoring combinatorial game, played on a directed graph where each vertex is either colored black or white. The two players, Black and White, play alternately by taking a vertex of their color and all its successors (for Black) or all its predecessors (for White). The score of each player is the number of vertices he has taken. We prove that influence is a nonzugzwang game, meaning that no player has interest to pass at any step of the game, and thus belongs to Milnor’s universe. We study this game in the particular class of paths where black and white vertices are alternated. We give an almost tight strategy for both players when there is one path. More precisely, we prove that the first player always gets a strictly better score than the second one, but that the difference between the scores is bounded by 5. Finally, we exhibit some graphs for which the initial proportion of vertices of the color of a player is as small as possible but where this player can get almost all the vertices.

  • 31 mai 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Quantum Entanglement and Quantum Cellular Automaton’‘
    by Kevissen Sellapillay (PhD LIS & CPT)
    See abstract

    Entanglement is a quantum property with no classical counterpart. We briefly review entanglement, its definition and quantities to measure it. We then present a perturbation of a quantum cellular automaton based on rule 201 and study its entanglement propagation properties. This quantum cellular automaton breaks the Hilbert space into different ergodic sectors.

  • 5 avril 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘A Pipeline for Solving Equations over Discrete Dynamical Systems’‘
    by Sara Riva (PhD I3S, Sophia Antipolis)
    See abstract

    Finite Discrete Dynamical Systems (DDS) are a formal model to study complex phenomena appearing in many different domains. Hypotheses on the fine structure of the system can be modeled via polynomial equations over DDS. For example, AX=B represents the hypothesis that the dynamics of B is given by the joint action of a known system A and an unknown one X. Finding X would validate the hypothesis; the hypothesis is invalid if no solution exists. In general, solving generic equations over DDS has been proved undecidable. In the hypothesis validation case, a possible approach is to study the solutions through a finite number of different abstractions of the problem. Each abstraction allows studying specific properties and parts of specific dynamics. We focus on hypotheses about the cardinality of the set of states, the cyclic behaviour and the transient behaviour of DDS. We introduce a complete pipeline based on Multi-valued decision diagrams to validate hypotheses on the cardinality of the set of states and on the asymptotic behaviour, contained in the cyclic parts, of a DDS. These results are a step forward in the analysis of complex dynamics graphs as those appearing, for instance, in biological regulatory networks or in systems biology. Furthermore, this approach opens up new research challenges in the field of ordered decision diagrams and their operations.

  • 8 mars 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Théorème du point fixe de Kleene en calculabilité’‘
    by Kévin Perrot (LIS)
    See abstract

    Pour toute transformation de programme h calculable, il existe un programme n tel que n et h(n) font la même chose. Ce théorème est génial, et sa preuve d’une simplicité déconcertante. De plus ses corollaires sont nombreux, comme l’indécidabilité de l’arrêt, et l’existence de quine (programme qui affiche en sortie son propre code) dans tout langage de programmation acceptable. On programmera un quine ensemble :-) Cet exposé est tiré d’une séance de l’UE Calculabilité Avancée en M1 Info, pas de résultat nouveau, juste un peu de culture.

  • 8 February 2022 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Purely local self-assembly algorithm for a quasiperiodic octagonal tiling’‘
    by Ilya Galanov
    See abstract

    Self-assembly is the process in which the components of a system, whether molecules, polymers, or macroscopic particles, are organized into ordered structures as a result of local interactions between the components themselves, without exterior guidance. This talk is devoted to the self-assembly of aperiodic tilings. Aperiodic tilings serve as a mathematical model for quasicrystals - crystals that do not have any translational symmetry. Because of the specific atomic arrangement of these crystals, the question of how they grow remains open. Simulations strongly support the evidence that the algorithm we developed grows aperiodic tilings up to an unavoidable but neglectable proportion of missing tiles. In this talk, we state the first theorem regarding the Golden-Octagonal tilings and formulate conjectures for future results.

  • 14 December 2021 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Plans discrets substitutifs’‘
    by Victor Lutfalla
    See abstract

    Je vais présenter mes travaux de thèse sur les Plans Discrets Substitutifs. Les plans discrets substitutifs sont une famille de pavages du plans.

    Les pavages du plan par des losanges unitaires avec un nombre fini n de directions d’arêtes peuvent être relevés dans R^n en fixant un sommet qui est envoyé sur l’origine et en associant à chaque direction d’arête un vecteur de la base canonique de R^n. Les pavages sont ainsi relevés en des surfaces discrètes de R^n. Un plan discret est un pavage dont le relevé dans R^n approxime un plan 2D de R^n.

    Les substitutions sont des applications qui à chaque tuile associent un motif de tuiles (comme pour les substitutions sur les mots), une substitution est ensuite étendue aux motifs en l’appliquant séparément à chaque tuile et en recollant ensuite les résultats, notez que le recollement des résultats est plus compliqué sur les pavages que sur les mots. Un pavage est dit substitutif s’il existe une substitution telle que tous les motifs finis du pavages peuvent être générés par cette substitution.

    Je vais présenter deux familles de pavages : Sub Rosa et Planar Rosa.Les pavages Sub Rosa sont des pavages substitutifs avec symétrie rotationnelle d’ordre 2n mais ils ne sont pas des plans discrets.Les pavages Planar Rosa sont des plans discrets substitutifs avec symétrie rotationnelle d’ordre 2n.

  • 7 December 2021 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Conjunctive grammars, cellular automata and logic’‘
    by Théo Grente
    Slides: PDF
    See abstract

    Conjunctive grammars are an extension of context free grammars with a conjunction operation. Their expressive power (even on a unary alphabet) is largely unknown. When restricting time, space or even communication, cellular automata (CA) can act as languages recognizer defining complexity classes. The goal of this talk is to prove the inclusion of conjunctive languages in one of CA complexity classes. The proof uses a programming method which relies on exact characterizations of interesting CA complexity classes by sub-logics of ESO (existential second-order logic) with Horn formulas as their first-order part. By using this method, we just have to define conjunctive grammars in our logic to obtain an inclusion result.

  • 23 November 2021 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘Classes de transitivité pour les sous-décalage de type fini multi-dimensionnels’‘
    by Silvère Gangloff
    Slides: PDF
    See abstract

    Ce travail est en commun avec B.Hellouin et P.Oprocha. Les sous-décalages de type fini multidimensionnels ont été étudiés dans les dernières décennies à travers le spectre de propriétés topologiques telles que la transitivité ou le mélange. Dans des travaux récents, nous avons montré, avec B.Hellouin et M.Sablik, qu’en quantifiant ces propriétés, il est possible de caractériser la complexité de ces systèmes dynamique en fonction de la quantité de transitivité/mélange (en particulier du point de vue calculabilité). Cependant les différentes classes de transitivité (relatives à cette quantification) sont mal comprises dans le cas général. Avec B.Hellouin et P.Oprocha, nous travaillons à caractériser ces classes dans le cadre restreint des Hom shifts, c’est à dire les sous-décalages définis par des ensembles de motifs interdits consistant en des dominos dont les symboles ne sont pas voisins dans un graphe fini non-orienté. Dans cet exposé, je présenterai le problème, ainsi que des résultats obtenus et attendus dans cette direction, qui laissent espérer une caractérisation complète des classes de transitivité dans le cas des Hom shifts.

  • 16 November 2021 : 14h00 at Visio
    ‘‘Spatial search by continuous-time quantum walk’‘
    by Leonardo Novo
    Video: see on AMUpod
    See abstract

    I will present two recent contributions about the performance of quantum search algorithms based on continuous-time quantum walks [1,2]. First, I will present some general results about the performance of the algorithm introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], which uses a continuous-time quantum walk to find a marked node on a graph of n nodes. This algorithm is said to be optimal if it can find any of the nodes in the graph in O(sqrt(n)) time. I will present conditions, based on the spectrum of the Hamiltonian driving the quantum walk, that can be used to predict whether the algorithm is optimal on a given graph. In the second part of the talk, I will present a new algorithm based on Hamiltonian evolution that finds marked nodes on any ergodic reversible Markov chain P quadratically faster than its classical hitting time. This algorithm can be seen as a quantum walk on the edges of a Markov chain and its performance matches that of discrete-time quantum walk search algorithms based on the Szegedy formalism. This work improves upon the recent work of [Phys. Rev. A 102, 022227 (2020)] and finally closes a theoretical gap between the performance of continuous-time and discrete-time quantum walk approaches for search.

    - On the optimality of spatial search by continuous-time quantum walk, Shantanav Chakraborty, Leonardo Novo, and Jérémie Roland, Phys. Rev. A 102, 032214 (2020)
    - Finding a marked node on any graph by continuous-time quantum walk , Shantanav Chakraborty, Leonardo Novo, and Jérémie Roland, Phys. Rev. A 102, 022227 (2020)

  • 4 November 2021 : 15h00 at Visio
    ‘‘Majority-3SAT (and Related Problems) in Polynomial Time’‘
    by Shyan Shaer Akmal
    Video: see on AMUpod
    See abstract

    Majority-SAT is the problem of determining whether an input n-variable formula in conjunctive normal form (CNF) has at least 2^{n-1} satisfying assignments. Majority-SAT and related problems have been studied extensively in various AI communities interested in the complexity of probabilistic planning and inference. Although Majority-SAT has been known to be PP-complete for over 40 years, the complexity of a natural variant has remained open: Majority-kSAT, where the input CNF formula is restricted to have clause width at most k. It recent work, joint with Ryan Williams, we prove that for every k, Majority-kSAT is in P. In fact, for any positive integer k and rational ρ∈(0,1) with bounded denominator, we present an algorithm which determines whether a given k-CNF has at least ρ2^{n} satisfying assignments, in deterministic linear time (whereas the previous best-known algorithm ran in exponential time). In this talk we give an overview of the main ideas behind these algorithms, and highlight the implications for some additional problems related to counting satisfying assignments.

  • 2 November 2021 : 14h00 at TPR2/04.05 (Luminy)
    ‘‘ZX-calculus, a Swiss army katana for quantum computing’‘
    by Titouan Carette
    Slides: PDF
    See abstract

    It usually requires months to master the concepts of quantum mechanics necessary to quantum computing. This time can be reduced drastically by using conveniently designed notations. The ZX-calculus, a graphical language to denote tensor, have been claimed to be such a powerful tool allowing to learn and then reason efficiently on quantum processes. I will support this claim by providing several examples of applications through three extensions of the ZX-calculus that have been introduced in the recent years, namely: mixed states, scalable, and stream ZX-calculus.

  • 5 October 2021 : 14h00 at Visio and TPR2/04.05 (Luminy)
    ‘‘Quantum Natural Language Processing’‘
    by Giovanni De Felice
    See abstract

    I will talk about string diagrams, how they are used to capture different models of quantum computation (e.g. circuit-based, measurement-based and linear optical quantum computing), as well as different models of natural language syntax (e.g. context-free grammars, pregroup grammars). I will show how to use this to perform natural language processing on currently available quantum hardware.

  • 16 February 2021 : 14h00 at Visio and TPR2/04.02 (Luminy)
    ‘‘Classical and quantum causal graph dynamics’‘
    by Amélia Durbec
    See abstract

    Causal graph dynamics are a twofold extension of cellular automata : the underlying grid is extended to an arbitrary bounded-degree graph and the graph itself is allowed to evolve over time. Such dynamics are insightful toy models for theoritical physics in both the reversible and the quantum regime. In this talk, we are going to see how a graph dynamics can be reversible and yet create/destroy vertices, and that vertex names are necessary in order to prevent faster-than-light signalling. We will finish this talk with outlooks towards graph self-assembly and graph subshifts.

  • 5 January 2021 : 14h00 at Visio
    ‘‘Simulation entre modèles de calcul naturel et modularité des réseaux d’automates’‘
    by Pacôme Perrotin
    See abstract

    Nous explorons différentes généralisations concernant les modèles de calcul naturel. La plus théorique est la notion de simulation entre modèles, pour laquelle nous décrivons une série de propositions de définition, en discutant des intérêts et des failles de chacune d’elles. Nous profitons des définitions les plus prometteuses pour élargir le propos sur les possibles conséquences de la simulation en théorie de la complexité, comme la construction de nouvelles classes de complexité en proposant la substitution de la réduction polynomiale par la simulation. Notre approche plus appliquée consiste en la généralisation des réseaux d’automates sous formes de modules, qui possèdent des entrées. Ce formalisme permet d’approcher les questions de la dynamique des réseaux d’interactions sous un nouvel angle : nous explorons son utilité en tant qu’outil modulaire propre à simuler de façon flexible de nombreux objets similaires, ainsi que l’expressivité des modules acycliques. Ceux-ci permettent la caractérisation de la dynamique des réseaux d’automates sous la forme de fonctions de sortie. Cette expressivité nous autorise la description d’un processus d’optimisation de réseaux d’automates, qui réduit certains réseaux en taille tout en conservant des attracteurs équivalents.

  • 27 October 2020 : 14h00 at Visio
    ‘‘Rice-like theorems for automata networks’‘
    by Guilhem Gamard
    See abstract

    An automata network (AN for short) is a finite digraph where each node holds a state, choosen among a finite set, that evolves in function of the states of its inbound neighbors. Time is discrete and all nodes evolve synchronously and in parallel, similarly to what happens in an cellular automaton. In other terms, the differences between a cellular automaton and an automata network is that the “grid” is an arbitrary finite digraph, and that different nodes may have different update functions. ANs have been used to model neural networks, dynamics of expression and inhibition of genes, distributed algorithms, and more. Although ANs look like a model of computation, they are not Turing-complete, for they lack unbounded memory. Still, they are subject to some kind of “Rice theorems”, i.e., results along the lines of: “any nontrivial property of the function computed by an automata network is computationally hard to test”. In this talk, we will review several results that fit this pattern, as well as pieces of proof that hopefully may be reused in other contexts.

  • 6 October 2020 : 14h00 at Visio
    ‘‘The semiring of dynamical systems’‘
    by Antonio E. Porreca
    Slides: PDF
    Video: see on AMUpod
    See abstract

    We introduce an algebraic approach for the analysis and composition of finite, discrete-time dynamical systems in terms of the category-theoretical operations of sum (disjoint union) and (tensor) product, which correspond to alternative and synchronous execution. This defines a semiring structure over the set of dynamical systems (modulo isomorphism), which allows us to express decomposition problems in terms of factorisation and polynomial equations. We analyse the algebraic properties of the semiring and prove that most dynamical systems are irreducible, and that the reducible ones sometimes admit multiple factorisation into irreducibles. We also prove that polynomial equations over this semiring are, in general, algorithmically unsolvable, and that many solvable subclasses of equations, including linear ones, are intractable even if the explicit dynamics of the systems is given as input (while in applications, where the dynamical systems are described more succinctly, these problems are conjecturally even harder). Finally, we also analyse dynamical systems in terms of their “topographic profiles”, a more abstract view in terms of the number of states at a given distance from the limit cycles of the system, which turns out to share many of the same algebraic properties.

  • 14 April 2020 : 14h00 at Visio
    ‘‘Molecular computers in artificial chemistry’‘
    by Marius Buliga
    See abstract

    Download PDF

  • 18 February 2020 : 13h30 at Salle de réunion LIS-BU1 (Luminy)
    ‘‘Preuve du paradoxe de Banach-Tarski’‘
    by Kévin Perrot

  • 7 January 2020 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding Model’‘
    by Nicolas Schabanel
    See abstract

    The Oritatami model was introduced by Geary et al (2016) to study the computational potential of RNA cotranscriptional folding as first shown in wet-lab experiments by Geary et al (Science 2014). In Oritatami model, a molecule grows component by component (named beads) into the triangular and folds as it grows. More precisely, the $\delta$ last nascent beads are free to move and adopt the positions that maximizes the number of bonds with the current structure. This dynamics captures the essence of cotranscriptional folding to a considerable extent, where an RNA sequence folds upon itself into complex shapes and functions while being synthesized (transcribed) out of its template DNA sequence.

    The Oritatami model was proven that it is capable of efficient Turing universal computation by Geary et al (2018) thanks to a quite complicated construction that simulates Turing machines via tag systems. We propose here a simple Oritatami system which intrinsically simulates arbitrary 1D cellular automata. Being intrinsic, our simulation emulates the behavior of the cellular automata in a readable way and in time linear in space and time of the simulated automaton. Furthermore, the number of bead types needed is quite modest (182 as opposed to 542), and the delay $\delta$ is 2 (instead of 3). The length of the transcript is also only quadratic in the size of the cellular automata: $O(rQ^{2(2r+1)}\log Q)$ for a cellular automata with $Q$ states and radius $r$ (whose size is thus $O(Q^{2r+1}\log Q)$). Our construction relies on the development of new tools which are simple enough that we believe that some simplification of them may be implemented in the wet lab. Our construction has been implemented and will be soon freely downloaded for testing.

  • 4 December 2019 : 10h30 at Salle de réunion du modulaire (Luminy)
    ‘‘Algebra, Tilings and Nivat’‘
    by Etienne Moutot
    See abstract

    A quel point peut-on créer des structures complexes à l’aide de motifs élémentaires ?

    La conjecture de Nivat dit que toute configuration (coloration de la grille Z^2) defaible complexité (le nombre de motifs qui y apparaissent est “faible”)est nécessairement périodique. Autrement dit, il est impossible des créer des configuration “complexes” (non périodiques) à l’aide d’un petit nombre de motifs de base.En 2015, Michal Szabados et Jarkko Kari ont publié leur premier article utilisant une approche algébrique pour s’attaquer à cette conjecture. Leur idée est de représenter une configuration comme une série formelle, et en étudiant certaines structures qui lui sont liées (tels que des idéaux polynomiaux bien choisis). Ce faisant, ils parviennent à exploiter plusieurs théorèmes d’algèbre pour s’approcher de la conjecture de Nivat sous des angles nouveaux.

    Dans cet exposé, je présenterai les travaux que j’ai effectué avec Jarkko Kari dans le continuation de la thèse de Michal Szabados. Je parlerais de nouveaux théorèmes utilisant ces outils algébriques pour se rapprocher encore une fois de la conjecture de Nivat. Nous avons notamment prouvé que la conjecture de Nivat est vraie pour les configurations uniformément récurrentes (dont tous les motifs peuvent se trouver “partout” dans la configuration).Une des conséquences de ce résultat est que le problème du domino est décidable pour les sous-shifts de faible complexité. Ce problème est indécidable de manière générale, et si la conjecture de Nivat est vraie, il serait décidable de manière évidente. Un des intérêt de notre résultat est qu’il permet de prouver cette décidabilité, sans pour autant avoir besoin de la conjecture de Nivat, seulement une version affaiblie.

  • 29 October 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Quasériodes des mots biinfinis’‘
    by Guilhem Gamard
    See abstract

    Un mot fini q est une quasipériode d’un mot infini w si et seulement si w est recouvert de copies de q, éventuellement chevauchantes. Si w admet au moins une quasipériode, on dit qu’il est quasipériodique. Cette notion est apparue dans les années 1990 dans un contexte d’algorithmique du texte, puis fut employée en combinatoire des mots, ainsi que dans l’étude des subshifts.
    Un article récent (2016) donne une technique générale permettant de déterminer l’ensemble des quasipériodes d’un mot infini donné. Cette technique permet par exemple de caractériser les quasipériodes des mots sturmiens. En outre, elle permet de démontrer que les mots sturmiens standard sont les mots apériodiques possédant “le plus de quasipériodes possibles”. La première partie de cet exposé présentera ces résultats.
    Malheureusement, tous ces résultats ne portent que sur les mots infinis à droite ; dans le cas des mots biinfinis, la combinatoire du problème est considérablement plus compliquée. Le cas biinfini est cependant plus naturel pour la dynamique symbolique, car le shift d’un mot biinfini quasipériodique est encore quasipériodique (ce qui n’est pas vrai sur les mots infinis à droite). Dans la deuxième partie de cet exposé, nous verrons comment généraliser les résultats précédents au cas biinfini.

  • 11 July 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Invariance de jauge dans les automates cellulaires’‘
    by Nathanael Eon
    See abstract

    L’invariance de jauge est une symétrie fondamentale en physique, permettant la dérivation des quatre interactions fondamentales (électromagnétique, faible, forte, gravitationnelle). D’autre part, les automates cellulaires sont largement reconnus comme un modèle de calcul naturel utile à la modélisation de phénomènes physiques. Cet exposé à pour but de montrer comment ces deux théories peuvent être réunies et les perspectives que l’on peut en tirer. L’exposé présentera les résultats obtenus pendant mon alternance ainsi que mon stage de M2. Gauge-invariance is an essential symmetry in Physics as it allows for the derivation of the four fundamental interactions (namely electromagnetic, weak, strong and gravitation). From a different perspective, cellular automata are a model of natural calculus largely known for its capacity to model physical phenomena. This talks aims at uniting those two theories and see what perspectives comes from such unification. The results presented comes from a research project which encapsulate my M2 internship.

  • 9 July 2019 : 13h30 at Salle de réunion du modulaire (Luminy)
    ‘‘Computational complexity of finite asynchronous cellular automata’‘
    by Enrico Formenti
    See abstract

    Cellular Automata (CA) are a well-established bio-inspired model of computation that has been successfully applied in several domains. In the recent years the importance of modelling real systems more accurately has sparkled a new interest in the study of asynchronous CA (ACA). When using an ACA for modelling real systems, it is important to determine the fidelity of the model, in particular with regards to the existence (or absence) of certain dynamical behaviors. This paper is concerned with two big classes of problems: reachability and preimage existence. For each class, both an existential and a universal version are considered. The following results are proved. Reachability is PSPACE-complete, its resource bounded version is NP-complete (existential form) or coNP-complete (universal form). The preimage problem is dimension sensitive in the sense that it is NL-complete (both existential and universal form) for one-dimensional ACA while it is NP-complete (existential version) or PI^P_2-complete (universal version) for higher dimension. (article/pii/S0304397515011421)

  • 2 July 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Étude d’un exemple de dynamique causale de graphe quantique’‘
    by Alan Gardin
    See abstract

    La présentation concerne l’étude d’une dynamique causale de graphe quantique. Il existe des résultats théoriques sur le sujet, que j’espère éclairer en présentant un exemple d’une telle dynamique. J’expliquerai notamment comment ce modèle a été construit, et quels ont été les problèmes rencontrés. Une fois cet exemple défini, je m’intéresserai aux applications potentielles de ce modèle, et plus particulièrement aux capacités de calcul. Enfin, j’aborde l’étude théorique de ce modèle d’un point de vue mathématique. Cette approche permettra éventuellement à terme de déduire certaines propriétés utiles à l’étude des capacités de calculs du modèle.

  • 4 June 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Machines de Turing à temps infini : des fondements aux applications’‘
    by Sabrina Ouazzani
    See abstract

    Dans cet exposé je vous présenterai les fondements des machines de Turing à temps infini, en particulier comment calculer avec et quelques unes de leurs particularités issues de mes travaux de recherche, mais j’en présenterai aussi de nouvelles applications, notamment en analyse, sur lesquelles je travaille actuellement avec Olivier Bournez. En particulier, quels liens ces machines entretiennent-elles avec les équations différentielles ? Je conclurai en introduisant quelques questions d’ouverture.

  • 23 May 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Solving Equations on Discrete Dynamical Systems’‘
    by Sara Riva
    See abstract

    Boolean automata networks, genetic regulation networks, and metabolic networks are just a few examples of biological modeling by discrete dynamical systems (DDS). A major issue in modeling is the verification of the model against the experimental data or inducing the model under uncertainties in the data. Equipping finite discrete dynamical systems with an algebraic structure of semiring provides a suitable context for hypothesis verification on the dynamics of DDS. Indeed, hypothesis on the systems can be translated into polynomial equations over DDS. Solutions to these equations provide the validation to the initial hypothesis. Unfortunately, finding solutions to general equations over DDS is undecidable. However, many tractable cases have been highlighted. In this article, we want to push the envelop further by proposing a practical approach for such cases. We demonstrate that for many tractable equations all goes down to a “simpler” equation. However for us, the problem is not to decide if the simple equation has a solution, but to enumerate all the solutions in order to provide an insight on the set of solutions of the original, undecidable, equations. We evaluate experimentally our approach and show that it has good scalability property.

  • 21 May 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Designing devices with Variational Quantum Circuits’‘
    by Filippo Miatto
    See abstract

    The design of realistic quantum devices can be extremely challenging, due to the complexity of quantum interactions or to the scarcity of analytical methods in certain areas, such as non-gaussian optical interactions. My approach is to start from a network of random quantum interactions and then optimize their parameters until we obtain the desired device. This is possible with a Variational Quantum Circuit (VQC), which allows for gradient descent methods as the optimization workhorse. The advantage of this method is that the raw VQC can be composed of realistic devices and designed for full generality, which means that a) a solution consists in the explicit blueprint with all the correct parts, their connectivity and their parameters all sorted out and b) it can be applied to a variety of domains, not just quantum optical devices. I apply this method to the design of a realistic one-way quantum repeater, which includes non-gaussian quantum optical interactions and is therefore a very difficult problem to solve without clever numerical methods. A preliminary result shows that it is in principle possible to have a repeater interaction with at most a few hundred elementary optical elements, which is an extremely promising result. Our current goal is to combine our method with Reinforcement Learning techniques to design better and better raw VQCs that can achieve the same performance with fewer elements and ultimately lead to the simplest and cheapest versions of the devices that we look for.

  • 14 May 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘A new logic for quantum computing’‘
    by Dominic Horsman
    See abstract

    In this talk I will give an introduction to the use of the ZX calculus of observables as a new language in which to frame quantum computing. In particular, I will focus on how it acts as a high-level design and compilation language for surface codes with lattice surgery. ZX calculus diagrams allow purely diagrammatic equational reasoning, and I will show how they are especially suited to representing the structures of surface codes. Looking particularly at the operations of lattice surgery, I show how the generators of the calculus form a direct model for splitting and merging operations. This has important implications for how we think about quantum information processing, and I will discuss a few such issues here.

  • 6 May 2019 : 14h30 at Salle G.02.12 du TPR1 (Luminy)
    ‘‘Inference and of elementary cellular automata limit-graphs’‘
    by Eurico Ruivo
    See abstract

    Cellular automata are locally defined dynamical systems which are discrete in space, time and in the state variables, and capable of presenting arbitrarily complex global emergent behaviour. One core question in the study of cellular automata refers to their limit behaviour, that is, to the global dynamical features in a infinite time evolution. For finite time evolutions, one-dimensional cellular automata present dynamics which can be described by regular languages and, therefore, by finite automata. Also, there are growth patterns in the evolution of such finite automata for some cellular automata rules. In this work we present the formalisation of an automatic method to compute such structures. Based on this, the rules of the elementary cellular automata rule space were classified according to the existence of a growth pattern in their finite automata and a method to infer the limit graph of some elementary cellular automata rules by analysing the regular expressions describing their behaviour in finite-time is presented.

  • 30 avril 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘The search for a complexity notion for organised dynamical systems’‘
    by Silvère Gangloff
    See abstract

    The neuroscientists G. Tononi, O.Sporns and G.M. Edelman proposed in 1994 a notion of complexity, that they called neural complexity, which aims at measuring the balance in a system between independance or specialisation of its parts and their integration into the whole that have organised systems such as the brain. This work has attracted recently the attention of mathematicians: in 2009, J. Buzzi and L. Zambotti defined a class of functionals called intricacies, which includes the particular case of neural complexity, and studied the maximisers of these functionals. This notion of intricacy was studied by K. Petersen and B. Wilson (2016) in the frame of symbolic dynamics, and computed a formula for some intricacy for very elementary one-dimensional subshifts of finite type. In this talk, I will expose the basic material to understand this problem and make an overview of the literature. In the end, I will try to expose some directions for research on this subject.

  • 2 avril 2019 : 15h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Could density determination be solved with one-dimensional binary cellular automata with asynchronous update?’‘
    by Pedro Balbi de Oliveira
    See abstract

    This title reflects the question that will start to be addressed during my visit to LIS. In the talk I will discuss the background about it, and give some idea about how the problem can be tackled. In its original formulation, density determination refers to the problem of deciding, by means of a one-dimensional cellular automaton rule, which is the most frequent bit in a cyclic binary configuration. This is one of the most widely studied benchmark decision problems in the cellular automata literature. In spite of various positive and negative results already known on the problem, in its various formulations, the possibility of solving it with a rule being updated in a deterministic asynchronous fashion is still open.

  • 19 février 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘An introduction to rule algebras and stochastic mechanics for theories of rewriting’‘
    by Nicolas Behr
    See abstract

    Reference: https://arxiv.org/abs/1807.00785
    In this talk, without assuming any particular familiarity of the audience with the relevant theory of (M-) adhesive categories, I will provide an introduction to the so-called Double-Pushout (DPO) rewriting framework. Particular emphasis will be given to a novel series of results that concerns a certain form of associativity of the notion of sequential compositions of rewriting rules. In fact, it is this associativity that (via the mathematical framework of rule algebras) permits to make contact between classical notions of manipulations of graphs in combinatorics and statistical physics on the one hand, and the category-theoretical formulation of rewriting theories on the other hand. Some explicit application examples in the field of continuous-time Markov chains based on stochastic DPO-rewriting systems will be presented, including models of dynamical random graph ensembles (such as e.g. a birth-death process on edges of finite graphs).

  • 29 janvier 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Analogies between subshifts and groups: Higman type theorems for subshifts’‘
    by Pascal Vanier
    See abstract

    Subshifts are sets of colorings of Z² by a finite alphabet that avoid some family of forbidden patterns. We investigate here some analogies with group theory that were first noticed by Emmanuel Jeandel. In particular we will show theorems on subshifts inspired by Higman’s embedding theorems of group theory, among which, the fact that subshifts with a computable language can be obtained as restrictions of minimal subshifts of finite type. This is joint work with Emmanuel Jeandel.

  • 22 janvier 2019 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Sur les délais de communication entre systèmes numériques (microcontrôleurs)’‘
    by Cédric Berenger
    See abstract

    Lors de mon stage de recherche, j’avais développé un algorithme de synchronisation pour de grands réseaux sur la base d’un modèle probabiliste de délais de transmission d’un noeud à l’autre. Lors d’essais avec des systèmes réels, nous sommes tombés sur des observations inattendues qui nous obligent de repenser les modèles, mais qui ouvrent aussi des perspectives d’applications très surprenantes en transformant un défaut en un atout.

  • 20 décembre 2018 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘SAT est NP-complet, la preuve !’‘
    by Kévin Perrot
    See abstract

    Ne croyez pas ce que l’on vous a dit, le théorème de Cook-Levin n’est pas si difficile que cela à démontrer… J’ai longtemps admis cette preuve, et après l’avoir lue dans le livre de Sylvain Perifel, j’ai envie de la partager ! Venez ajouter LA brique de base à vos connaissances en complexité, ou simplement réviser :-)

  • 15 novembre 2018 : 10h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Adiabatic methods in quantum control’‘
    by Francesca Chittaro
    See abstract

    Quantum control is the branch of control theory concerned with quantum systems, that is, dynamical systems at atomic scales, that evolve according to the laws of quantum mechanics.

    One fundamental issue in quantum control theory is the controllability of quantum systems, that is, whether is it possible to drive a quantum system to a desired state, by means of suitably designed control fields. To cover most theoretical and practical situations, several notion of controllability have been proposed, as, for instance, controllability in the evolution operator, pure state controllability, controllability in population and eigenstate controllability. After a brief introduction on the topic, I will expose some results on the approximate spread controllability of (closed) quantum systems, obtained by means of adiabatic techniques, and taking advantage of the presence of conical intersections between the energy eigenstates. These results have been published in [1],[2].

    Adiabatic techniques can be successfully used also to study the dynamics of open quantum systems. In particular, in [3] they have been applied to find an effective description of the evolution of open, weakly coupled quantum systems, where the sub-system of interest dissipate with much slower time scales than the rest of the system.

    [1] U. Boscain, F. C. Chittaro, P. Mason, M. Sigalotti Quantum Control via Adiabatic Theory and intersection of eigenvalues IEEE-TAC, (2012) 57, No. 8, 1970–1983
    [2] F. C. Chittaro, P. Mason Approximate controllability via adiabatic techniques for the three-inputs controlled Schrödinger equation, SIAM J. Control Optim., (2017), 55(6), 4202–4226.

  • 13 novembre 2018 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Exploring attractor invariance in elementary cellular automata’‘
    by Stephanie McLean
    See abstract

    We are interested in the study of the set of attractors of all 256 Elementary Cellular Automata (ECA) , i.e., one-dimensional, binary 3-neighbourhood cellular automata, dened on an n-cell lattice (n is the length of the automaton).

    Recent works have studied the invariance of their attractors against dierent update schemes, and how these aect their dynamics. Specically, in [1] was introduced the notion of k-invariance: an ECA rule r is k-invariant if its set of attractors, denoted by Fr(s), remains invariant for all update schemes s having blocks of length at most k (notice that k=1 stands for sequential update schemes, while k = n is the parallel, or synchronous one). In this context, the 1-invariance was studied in [2], where 104 ECA rules showed to have this kind of invariance. In [1] and [3] the authors studied the k-invariance, for 2 < k ≤ n, for all 104 ECA rules above mentioned.

    In this work, we explore another notion of attractor invariance “in between ECA rules”, we say that two ECA rules u and v are attractor equivalent over a set of update schemes S, if given any s in S, Fu(s) = Fv(s). We begin our study with the 1-invariant rules, searching for equivalences between their sets of attractors, for all 4 ≤ n ≤ 14, so as to have a set of rules that are “candidates” to be attractor equivalent, since we know that if u and v are both 1-invariant ECA rules, then their sets of attractors remain invariant, but not necessarily the same, for all sequential update schemes s. Attractor equivalence gives us new insights of the dynamical behaviour of a rule (and its equivalent rules) under dierent update schemes.

  • 23 octobre 2018 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘On the Complexity of the Stability Problem of Binary Freezing Totalistic (Asynchronous) Cellular Automata’‘
    by Diego Maldonado
    See abstract

    We study the computational complexity of a family of simple two-dimensional, two-state freezing CA under synchronous and asynchronous update scheme. In such family of CA, sites in state 0 change to state 1 depending only on the sum of the states of their neighbors, while sites in state 1 remain always in that state. The complexity of a CA is an automata is that of stability problem: it consists in the long-term prediction of the state of a site. We show that in this family of 32 local rules, is possible to find cases with P-Complete, NC, and constant time complexity.

  • 16 octobre 2018 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Automates cellulaires et solitons’‘
    by Guillaume Theyssier
    See abstract

    Les automates cellulaires sont à la fois un modèle de calcul et une famille de systèmes dynamiques discrets. On peut se demander comment leur complexité computationnelle et leur complexité dynamique sont liées. Cet exposé propose de faire un petit pas dans ce questionnement en se basant sur une notion générale de soliton. Nous nous intéresserons aux automates cellulaires SANS soliton et à leur propriétés dynamiques. Nous verrons en particulier que l’absence de soliton caractérise la randomisation dans les automates abéliens et explorerons les liens avec les notions de pré-expansivité et de diffusion dans le cas général.

  • 21 septembre 2018 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Nombre de points fixes des réseaux booléen : Complexité algorithmique’‘
    by Florian Bridoux
    See abstract

    Dans cette présentation nous allons nous intéresser aux réseaux booléens (RB). Un RB de taille n peut être vu comme une fonction f: {0,1}^n -> {0,1}^n ou bien comme un produit de n fonctions f_1, f_2, …, f_n de {0,1}^n à {0,1}. Un problème classique est le calcul du nombre de points fixes, c’est-à-dire le nombre de configurations x dans {0,1}^n tel que f(x) = x. Un objet souvent utilisé (et qui justifie la terminologie de « réseaux ») quand on s’intéresse aux réseaux booléens est le graphe d’interaction. Il s’agit d’un graphe à n sommets numérotés de 1 à n tel qu’il y a un arc entre le sommet i et j ssi la valeur de f_j(x) dépendant de la i-eme composante de x pour un certain x (= le sommet i “a une influence” sur j). Chaque RB a son graphe d’interaction mais un même graphe d’interaction peut correspondre à de nombreux RBs. Nous allons noter F(G) l’ensemble des RBs correspondant à un certain graphe d’interaction G. Et nous allons nous intéresser à la question: “Étant donné G et un entier k, existe-t-il f dans F(G) qui a au moins/au plus k points fixes?” Nous allons voir que selon la nature de k et l’exacte question posée, le problème peut appartenir à différentes classe de complexité allant de P à NEXPTIME.

  • 11 septembre 2018 : 16h15 at Salle de réunion du modulaire (Luminy)
    ‘‘Quantum Computation with Indefinite Causal Order’‘
    by Fabio Costa
    See abstract

    In a quantum computer, a system undergoes a sequence of quantum transformations, which can solve certain problems more efficiently than any classical computer. However, the order in which the transformations take place is fixed. I will present an extension of this model, where an additional quantum system controls the order between transformations. This new possibility provides an advantage for computational and communication problems, above what is achievable by “ordinary” quantum computers. The formalism describing this new model of computation has further applications to the study of novel physical regimes, which combine quantum superpositions with general relativistic causal structure.

  • 10 juillet 2018 : 11h at Salle de réunion du modulaire (Luminy)
    ‘‘Elementary particle dynamics, return times and combinatorics’‘
    by Enrico Formenti
    See abstract

    In this talk we will explore simple particle dynamics and see how it can be studied using discrete dynamical systems. We will focus on return time, namely, the expected time after which a given particle will appear again at some fixed position. In particular, we will see how in the non-resting case, the movement of particles can be encoded into combinatorial questions about paths in a peculiar lattice.

  • 10 juillet 2018 : 11h at Salle de réunion du modulaire (Luminy)
    ‘‘Quantum Machine Learning’‘
    by Hachem Kadri
    See abstract

    Quantum Machine Learning is an emerging field of research, with fast growth. This research field is largely driven by the desire to develop artificial intelligence that uses quantum technologies to improve the speed and performance of learning algorithms. In this talk I will give a brief introduction to quantum machine learning and discuss current challenges in the field. I will pay special attention to quantum perceptron models and our recent work on entangled kernel machines, giving new insights into the interaction between Quantum Computing and Machine Learning.

  • 6 juin 2018 : 14h at Salle de réunion du modulaire (Luminy)
    ‘‘A gauge-invariant reversible cellular automaton’‘
    by Nathanaël Eon
    See abstract

    Gauge-invariance is a fundamental concept in physics—known to provide the mathematical justification for all four fundamental forces. In this paper, we provide discrete counterparts to the main gauge theoretical concepts, directly in terms of Cellular Automata. More precisely, we describe a step-by-step gauging procedure to enforce local symmetries upon a given Cellular Automaton. We apply it to a simple Reversible Cellular Automaton for concreteness. From a Computer Science perspective, discretized gauge theories may be applied to numerical analysis, quantum simulation, fault-tolerant (quantum) computation. From a mathematical perspective, discreteness provides a simple yet rigorous route straight to the core concepts.

  • 5 juin 2018 : 14h at Salle de réunion du modulaire (Luminy)
    ‘‘Folding shapes with oritatami systems’‘
    by Nicolas Schabanel
    See abstract

    so as to maximize the number of bonds formed, self-assemblying into a shape incrementally. The parameter $\delta$ is called the “delay” and is related to the transcription rate in nature.

    This article initiates the study of shape self-assembly using oritatami. A shape is a connected set of points in the triangular lattice. We first show that oritatami systems differ fundamentally from tile-assembly systems by exhibiting a family of infinite shapes that can be tile-assembled but cannot be folded by any OS. As it is NP-hard in general to determine whether there is an OS that folds into (self-assembles) a given finite shape, we explore the folding of upscaled versions of finite shapes. We show that any shape can be folded from a constant size seed, at any scale $n\geq 3$, by an OS with delay $1$. We also show that any shape can be folded at the smaller scale $2$ by an OS with “unbounded” delay. This leads us to investigate the influence of delay and to prove that there are shapes that can be folded (at scale $1$) with delay $\delta$ but not with delay $\delta’<\delta$, for all $\delta > 2$.

    These results serve as a foundation for the study of shape-building in this new model of self-assembly, and have the potential to provide better understanding of cotranscriptional folding in biology, as well as improved abilities of experimentalists to design artificial systems that self-assemble via this complex dynamical process.

  • 22 mai 2018 : 14h at Salle de réunion du modulaire (Luminy)
    ‘‘Quantum simulations via quantum walks over the honeycomb and triangular lattices’‘
    by Iván Márquez
    See abstract

    In this seminar we will talk about how to simulate quantum physical models via discrete-time quantum walks (DTQWs) over hexagonal and triangular lattices. We will define what a QW is from a computer science perspective. The study of QWs is growing due to two reasons. First, different kind of Quantum Computing algorithms have been created using them in an efficient way. On the other hand, they can be used for the purpose of quantum simulating in the future quantum simulation devices.

    From the quantum simulation perspective, QWs have been extensively used for reproducing relativistic particles dynamics described by the Dirac equation, always using regular lattices. We will show that QWs does not need to rely on the regular lattice grid, and that they can be casted on the hexagonal and triangular grid instead. We believe that this constitutes an important step towards: modeling propagation in crystalline materials; identifying substrates for QW implementations; studying topological phases and understanding propagation in discretized curved spacetime.

  • 17 mai 2018 : 14h at Salle des commissions, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Classical and Quantum Simulations via Quantum algorithms’‘
    by Pedro Costa
    See abstract

    The era of quantum computers has already started. One important question that we can do now that we have these quantum devices ready is which quantum model of computation will be a good choice for encoding the huge number of quantum algorithms available. Another important question which is also extremely important to people that work in the industry that very often employs numerical methods to solve differential equations is that if these numerical methods are a promising application for quantum computers. Going to these directions we will present in this seminar our latest results where we introduce a partitioned model of quantum cellular automata and show how it can simulate, with the same amount of resources, various models of quantum walks. All the algorithms developed within quantum walk models are thus directly inherited by the quantum cellular automata. The latter, however, has its structure based on local interactions between qubits, and as such it can be more suitable for present (and future) experimental implementations. In the part related with numerical methods to solve differential equations, we will present a quantum algorithm for simulating the wave equation under Dirichlet and Neumann boundary conditions. The algorithm uses Hamiltonian simulation and quantum linear system algorithms as subroutines. Relative to classical algorithms for simulating the D-dimensional wave equation, our quantum algorithm achieves exponential space savings, and a speedup which is polynomial for fixed D and exponential in D. We also consider using Hamiltonian simulation for Klein-Gordon equations and Maxwell’s equations.

  • 15 mai 2018 : 14h at Salle de réunion du modulaire (Luminy)
    ‘‘Systèmes dynamiques finis, jeux des chapeaux et théorie des codes’‘
    by Hervé Seligmann
    See abstract

    Three mechanisms reveal unsuspected information in protein-coding genes: 1) alternative transcriptions that transform along systematic rules template sequences (for example systematic deletions of k nucleotides after each n transcribed nucleotides and systematic exchanges between nucleotides, such as AC or A>C>G>A); 2) codon expansion, where tRNAs with anticodons expanded by noncoding nucleotide(s) decode expanded codons; and 3) reassignments of codons to different amino acids. Here I present evidences for mechanisms 1 and 2, and associated self-correcting properties of the genetic code.

  • 15 mai 2018 : 11h at TPR2, salle 304-306 (Luminy)
    ‘‘Cryptic genes and genetic codes in mitochondria: Some of DNA’s unexplored coding dimensions’‘
    by Maximilien Gadouleau
    See abstract

    Un système dynamique fini (FDS) est un réseau d’entités qui interagissent au cours du temps. Chaque entité a un état parmi q possibles, pour q ≥ 2 donné, qui varie en fonction du temps et des états d’autres entités. Formellement, un FDS est une fonction f de {0,1,…,q-1}n dans lui-même (n étant le nombre d’entités) ; un FDS avec q=2 est ainsi un réseau booléen. L’un des problèmes majeurs de l’étude des FDS est d’étudier la dynamique du réseau en fonction de son graphe d’interaction, qui indique les relations d’influence parmi les entités. Ici nous nous intéressons à l’existence d’un FDS f stable, i tel que pour tout état x, son successeur f(x) a au moins une coordonnée égale à celle de x. Nous relions ce problème au jeu des chapeaux de Winkler et nous utilisons la théorie des codes pour construire des FDS stables avec des graphes d’interaction très particuliers et contre-intuititifs.

  • 10 avril 2018 : 14h at Salle des commissions, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Quantum walks in curved spacetime’‘
    by Stefano Facchini
    See abstract

    A discrete-time Quantum Walk is essentially a unitary operator driving the evolution of a single particle on the lattice. We introduce the Grouped QWs, a generalization of the usual QWs where (i) the input is allowed a simple prior encoding and (ii) the local unitary coin is allowed to act on larger than usual neighborhoods; we show that it allows us to recover the Dirac equation in curved spacetime. Moreover we discretize the coin operator itself, only allowing a finite set of elementary local unitary operators. The discretization has the practical advantage of allowing easier experimental implementation, as well as of being of interest for studyingthe quantization of the metric.

  • 6 avril 2018 : 14h at Salle de réunion du modulaire (Luminy)
    ‘‘Entropy Inequalities, Secret Sharing and Applications’‘
    by Tarik Kaced
    See abstract

    Après une introduction au partage de secret, je présenterais quelques résultats sur le partage de secret non-parfait. Nous expliquerons la méthode des inégalités d’information pour obtenir des bornes sur l’efficacité des schémas de partage. Nous expliquerons des résultats généraux sur la géométrie du cône d’entropie et leurs applications.

  • 5 avril 2018 : 14h at Salle de réunion du modulaire (Luminy)
    ‘‘Communication topologies in natural computing’‘
    by Antonio Porreca
    See abstract

    When analysing the computational properties and the efficiency of uniform parallel computing models, most of these turn out to be either equivalent to deterministic Turing machines, thus characterising the complexity class P in polynomial time, or are otherwise capable of solving in polynomial time the problems that sequential computing devices solve in polynomial space (i.e., the complexity class PSPACE).

    However, certain natural computing models seem to escape this binary classification. In particular, several variants of parallel devices inspired by cell biology, called membrane systems, have been recently proved to characterise complexity classes between P and PSPACE when working in polynomial time. Some of these classes are rather unusual in the literature, and had previously only been defined in terms of Turing machines with oracles, rather than being characterised by a more concrete model of computation.

    Fundamental in the characterisation of these complexity classes is the communication topology of the device, that is, the graph along whose edges communication between the sequential computing units is allowed. The graph-theoretic (e.g., directedness, diameter) and geometric properties (e.g., embeddability in given metric spaces), as well as the description complexity of the graph (e.g., how the the adjacency list of a vertex can be computed) all influence the overall efficiency of the resulting device.

    In this talk we discuss the known relations between communication topology and computational complexity in membrane systems, and we propose to investigate these relations more generally and more abstractly by choosing a more convenient reference model, namely a variant of automata networks.

  • 3 avril 2018 : 16h at Salle de réunion du 3e étage de la FRUMAM (Saint-Charles).
    ‘‘Réseaux biologiques : algorithmique et optimisation’‘
    by Ricardo Andrade
    See abstract

    Dans cette présentation, je vais parler de deux problèmes d’énumération qui apparaissent lors de l’étude des réseaux biologiques. Le premier est le problème d’énumération d’ensembles de précurseurs dans un réseau métabolique. Un réseau métabolique est l’ensemble des processus chimiques et physiques qui déterminent le fonctionnement du métabolisme d’un organisme. Ce type de réseau est fréquemment modélisé comme un graphe de composés, un graphe biparti ou un hypergraphe, et un ensemble de précurseurs est un ensemble de composés source qui sont utilisés par un organisme pour produire un ensemble de composés cible. Le deuxième problème est une formulation bi-objective du problème du transversal minimum dans un hypergraphe. La motivation biologique est l’identification de gènes qui sont liés à des mutations qui contribuent directement au cancer. Notre hypergraphe modélise un réseau d’interaction de gènes. Les sommets correspondent à des gènes et il existe une arête entre deux gènes s’ils interagissent entre eux. Je vais présenter les problèmes et leurs motivations biologiques ainsi que brièvement quelques résultats de complexité et des algorithmes pour les résoudre.

  • 29 mars 2018 : 14h at Salle de réunion du 3e étage de la FRUMAM (Saint-Charles).
    ‘‘Utilisation de la programmation dynamique comme stratégie pour l’algorithme de simulation parfaite’‘
    by Christelle Rovetta
    See abstract

    En 1996, Propp et Wilson ont proposé un algorithme permettant l’échantillonnage sans biais de la distribution stationnaire d’une chaîne de Markov ergodique. Ce dernier appelé aussi algorithme de simulation parfaite, requiert la simulation en parallèle de tous les états possibles de la chaîne. Un des challenges lorsque l’on veut faire de l’échantillonnage par simulation parfaite réside généralement à mettre en place des stratégies permettant de ne pas avoir à simuler toutes les trajectoires.

    Un réseau fermé de files d’attente est un réseau dans lequel les clients ne peuvent ni entrer ni quitter le réseau. La dynamique de tels réseaux est couramment représentée par une chaîne de Markov ergodique. La difficulté pour qui voudrait appliquer l’algorithme de Propp et Wilson à de tels réseaux, réside dans la taille de l’espace des états qui est exponentielle en le nombre de files à laquelle s’ajoute une contrainte globale à savoir le nombre constant de clients.

    Pour commencer mon exposé, je présenterai une stratégie inspirée de la programmation dynamique qui permet la mise en œuvre de l’algorithme de Propp et Wilson pour des réseaux fermés de files d’attente. Dans un deuxième temps, je caractériserai la structure de données utilisée pour représenter l’espace des états, révélerai qu’elle englobe des objets combinatoires autres que les espaces d’états des réseaux fermés de files d’attente. Enfin, je terminerai par des applications induites par cette structure notamment dans le cadre de la méthode symbolique ainsi que dans le contexte de la cinétique du repliement d’ARN.

  • 22 mars 2018 : 14h at Salle de réunion du modulaire (Luminy)
    ‘‘Automaton groups, structure and properties’‘
    by Thibault Godin
    See abstract

    In this talk, I will give a brief overview of the interplay between the structure of a Mealy automaton and the properties of the (semi)group it generates.

    Mealy automata are special kind of transducers that can be used to generate (semi)groups. These (semi)groups have been widely used in mathematics since the 80’s as they can have some very interesting properties. For instance for first example of a group of intermediate growth has been discovered using a Mealy automaton. Furthermore, the underlying automata make these (semi-)groups amenable to computer science techniques, and I explain how automaton theoretic tools be used to predict characteristics of the group generated by a Mealy automaton.

  • 15 mars 2018 : 14h at Salle des commissions, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Pavages, calculs et quasipériodicité’‘
    by Guilhem Gamard
    See abstract

    Une tuile de Wang est un carré unité dont les bords sont colorés. Si on dispose d’un ensemble fini de tuiles, on peut chercher à paver le plan : il s’agit de placer une copie d’une tuile dans chaque cellule de la grille unité, de telle façon que deux bords en contact ont toujours la même couleur. Les rotations et les symétries ne sont pas autorisées. Ce modèle permet de définir des «langages» sur les mots infinis en deux dimensions (autrement dit, des ensembles de colorations de ℤ²).

    On sait depuis les années 1960 qu’il est possible d’encoder n’importe quelle machine de Turing dans des tuiles de Wang, mais la construction est passablement complexe. Dans les années 1990, Jarkko Kari a donné un nouveau moyen d’encoder du calcul dans des tuiles de Wang. L’avantage de cette construction est que l’état du calcul à un temps T est stocké de façon «diluée» dans l’espace, si bien que le calcul peut continuer même en présence de petites «erreurs» locales.

    Nous montrerons, en utilisant des invariants de théorie de l’information, en quoi ces deux constructions sont fondamentalement différentes. Nous esquisserons ensuite une généralisation de la construction de Kari en un modèle de calcul sur les réels, résistant aux erreurs. Ce dernier point est l’objet de travaux en cours, il y aura donc plus de questions que de réponses au sujet de ce modèle de calcul.

    Dans une dernière partie, indépendante de ce qui précède, nous nous pencherons sur un cas particulier de règle locale définissable par tuiles de Wang : la quasipériodicité. Un mot fini (1D ou 2D) q est une quasipériode d’un mot infini w si ce dernier est recouvert d’occurrences de q, éventuellement chevauchantes. Nous verrons que la quasipériodicité possède un pouvoir expressif surprenamment important, et nous montrerons également comment la généraliser pour construire un modèle de calcul.

  • 15 mars 2018 : 11h at Salle des commissions, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Tree sets: from combinatorics on words to symbolic dynamics’‘
    by Francesco Dolce
    See abstract

    A tree set is a language of finite words such that the extension graph of each of its elements, the graph describing left and right extensions of the word in the language, is a tree. This class of sets includes classical families such as Sturmian and episturmian sets, as well as the coding of interval exchange transformations.

    Despite the very simple combinatorial definition, this family of languages satisfies several non trivial properties. It also provides an interesting connection between combinatorics on words, symbolic dynamical systems, bifix codes and free groups.

    In this talk, we investigate these sets, focusing on some geometrical examples (interval exchanges and linear involutions) and on some closure properties.

  • 13 mars 2018 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Théorie des chemins et informatique : interactions’‘
    by Pierre-Louis Giscard
    See abstract

    Dans cet exposé nous démontrerons que les chemins sur les graphes obéissent à l’extension semi-commutative de la théorie des nombres ; complète avec ses éléments premiers, ses fonctions fondamentales (zêta, Möbius, von Mangoldt, Liouville …) et même une pléthore de relations entre objets combinatoires en extension directe de relations célèbres de la théorie des nombres. Cette approche fournie de nombreux outils nouveaux pour traiter des problèmes en mathématiques appliquées et informatique fondamentale. Nous présenterons un rapide tour d’horizon de ces applications, en combinatoire énumérative, calcul différentiel, inférence statistique, analyse des réseaux, algorithmique, apprentissage automatique sur les graphes, et dynamique quantique. Nous nous attacherons notamment à montrer comment des cribles non-commutatifs sur les chemins conduisent d’une part à une amélioration de prés de 25% sur le modèle de l’état de l’art concernant la prédiction des protéines de la plante Arabidopsis thaliana qui sont ciblées par des pathogènes; et d’autre part pour la détection de complexes de protéines chez la levure Saccharomyces cerevisiae. Nous illustrerons également les implications de nos résultats en sociologie, où un algorithme pour le dénombrement des cycles simples à permis de vérifier une vieille conjecture sur les interactions sociales; en chimie organique où nous classons des molécules selon leurs propriétés à l’aide d’un idempotent algébrique de Hopf; et pour la dynamique des ensembles de spins en résonance magnétique nucléaire.

    Mots clés : combinatoire des chemins; analyse des réseaux; apprentissage automatique; algorithmique.

    Références : le séminaire fera appel à de nombreuses publications, disponibles ici https://arxiv.org/find/all/1/all:+giscard/0/1/0/all/0/1.

  • 20 février 2018 : 14h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Méthodes de complétion et d’analyse de la dynamique des réseaux de régulation biologique : un résumé de mes travaux.’‘
    by Maxime Folschette (Dymec & Dyliss)
    See abstract

    Afin de contourner la complexité des systèmes d’équations différentielles, Kauffman (1969) puis Thomas (1973) jettent les bases d’une modélisation discrète sous forme de graphes, dont la dynamique est une restriction des réseaux d’automates, et assurant néanmoins une cohérence avec les systèmes réels modélisés. De nouvelles questions émergent alors, comme l’automatisation de la création de tels modèles discrets ou hybrides, ainsi que l’analyse de leur dynamique. Durant ce séminaire, après un rappel sur le classique modèle de Thomas, qui sert de base à mes travaux, j’exposerai les deux principaux aspects de ma recherche.
    * Le premier est la complétion de modèles, consistant à inférer la topologie ou les paramètres manquants d’un modèle.
    - Une première approche a consisté à utiliser une version modifiée de la logique de Hoare afin de trouver les valeurs de certains paramètres dynamiques ; pour cela, un comportement dynamique biologique tiré de la littérature est traduit en programme impératif et soumis à un calcul de plus faible précondition à la Dijkstra.
    - Une seconde approche, plus récente et expérimentale, consiste à reconstruire la topologie d’un réseau (les influences entre éléments, notamment) en se basant directement sur des données d’expression dans le temps, contrairement aux méthodes existantes qui requièrent une phase de discrétisation préalable.
    * Le second aspect est l’analyse de la dynamique d’un tel modèle complexe.
    - Analyse à l’aide d’Answer Set Programming (ASP), un paradigme de programmation logique récent et dont les solveurs donnent de bons résultats pour plusieurs problèmes classiques : atteignabilité d’un état, recherche des points fixes, recherche des attracteurs complexes.
    - Analyse à l’aide de µ-calcul, une extension de la logique temporelle classique CTL* : cela permet d’obtenir une plus grande expressivité, permettant notamment une recherche des attracteurs et des disruptions, ou encore une vérification de bisimulation entre modèles.
    - Analyse à l’aide d’analyse statique par interprétation abstraite : à l’inverse, pour une seule propriété donnée (ici, l’atteignabilité), réduit grandement la complexité et permet d’obtenir des résultats sur des grands modèles en très peu de temps.

  • 30 janvier 2018 : 9h30 at Salle du conseil, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Continuous models of computation: computability, complexity, universality.’‘
    by Amaury Pouly (Max Planck Institute)
    See abstract

    In 1941, Claude Shannon introduced a continuous-time analog model of computation, namely the General Purpose Analog Computer (GPAC). The GPAC is a physically feasible model in the sense that it can be implemented in practice through the use of analog electronics or mechanical devices. It can be proved that the functions computed by a GPAC are precisely the solutions of a special class of differential equations where the right-hand side is a polynomial. Analog computers have since been replaced by digital counterpart. Nevertheless, one can wonder how the GPAC could be compared to Turing machines.

    A few years ago, it was shown that Turing-based paradigms and the GPAC have the same computational power. However, this result did not shed any light on what happens at a computational complexity level. In other words, analog computers do not make a difference about what can be computed; but maybe they could compute faster than a digital computer. A fundamental difficulty of continuous-time model is to define a proper notion of complexity. Indeed, a troubling problem is that many models exhibit the so-called Zeno’s phenomenon, also known as space-time contraction.

    In this talk, I will present results from my thesis that give several fundamental contributions to these questions. We show that the GPAC has the same computational power as the Turing machine, at the complexity level. We also provide as a side effect a purely analog, machine- independent characterization of P and Computable Analysis.

    I will present some recent work on the universality of polynomial differential equations. We show that when we impose no restrictions at all on the system, it is possible to build a fixed equation that is universal in the sense it can approximate arbitrarily well any continuous curve over R, simply by changing the initial condition of the system.

    If time allows, I will also mention some recent application of this work to show that chemical reaction networks are strongly Turing complete with the differential semantics.

  • 23 janvier 2018 : 10h00 at Salle du conseil, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Crossing information on abelian sandpile models.’‘
    by Kévin Perrot
    See abstract

    We will study the family of abelian sandpile models :
    * on the two-dimensional grid,
    * with uniform neighborhood,
    and see how important is the shape of the neighborhood in the ability of the sandpile to simulate circuits, in order to prove the P-completeness of its prediction problem. The key point on which we will concentrate is the ability to construct a crossing gate. Joint work with Ha Nguyen, available at https://arxiv.org/abs/1709.00464.

  • 28 novembre 2017 : 14h30 at Salle des commissions, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Edge-colored graphs representing pseudo-manifolds and discrete quantum gravity.’‘
    by Luca Lionni (LaBRI)
    See abstract

    (D+1)-Edge-colored graphs represent D-dimensional triangulations, and the geometrical properties of the latter are translated into graph roperties. This finds an application in discrete approaches to quantum gravity called dynamical riangulations. Triangulations should then be classified according to their mean urvature. We introduce a bijection with combinatorial maps, which often helps us solve this problem.

  • 28 novembre 2017 : 11h00 at Salle des commissions, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Quantum cellular automata and quantum field theory.’‘
    by Terry Farrelly (Leibniz University, Hanover)
    See abstract

    The recent emergence of quantum computers as tools to simulate physics has been one of the driving forces of the field. Here we will look at a articular model of quantum computing called quantum cellular automata, which seems particularly seful for simulating quantum field theories. Many issues will arise, even for on-interacting quantum field theories, including finding the correct vacuum state on the lattice. e will discuss some of these problems, some results, and ideas for future work.

  • 27 novembre 2017 : 14h30 (séminaire LIRICA) at Salle de réunion du 2e étage de la FRUMAM (Saint-Charles)
    ‘‘Raisonnement non-monotone et prise de décision incertaine : application à un planeur autonome.’‘
    by Jose Luis Vilchis Medina
    See abstract

    L’exposé aborde l’étude d’un planeur autonome et de la prise de décision de pilotage, dans un environnement incertain. Dans ce cadre, le but d’un pilote de planeur est de rester en l’air le plus longtemps possible en prenant en compte des contraintes qui peuvent être contradictoires : contraintes de vol, recherche d’ascendance(thermal), réglementation aéronautique, sécurité … Dans un premier temps, nous allons essentiellement intéressés à modéliser le système capable de gérer des situations contradictoires et incertaines. Pour ce faire, nous allons utiliser un type de logique non-monotone, la logique des défauts de Reiter. Dans un deuxième temps, pour la prise de décision incertaine, nous allons définir une approche basée sur un critère non-probabiliste, pour choisir l’extension qui contient les actions optimales. Enfin, nous montrerons quelques résultats.

  • 3 octobre 2017 : 11h00 at Salle du conseil, Bât TPR 2 - 1er étage (Luminy)
    ‘‘Codes CSS et Complexes de chaines.’‘
    by Benjamin Audoux (I2M)
    See abstract

    Dans cet exposé, je rappellerais la définition des codes correcteurs d’erreurs quantiques dits CSS, et montrerai en quoi ils sont fortement liés à la notion, plus topologique, de complexe de chaine. Selon le temps disponible, je développerai ensuite quelques applications de ce point de vue topologique aux codes CSS.

  • 12 juillet 2017 : 10h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Algorithms for computing the rank of divisors on some classes of graphs.’‘
    by Ha Duong Phan (Institut de Mathématiques, Hanoi)
    See abstract

    The notion of rank of divisors on graphs was introduced by Baker and Norine in 2007 in showing the link with the similar notion on Riemann surfaces. Moreover, the authors have developed a theorem for divisors on graph analogue to the classical Riemann-Roch theorem. Since then, many works have studied for computing the rank of divisors on graphs. A very important is the new theorem on the NP-hardness complexity of the Problem of computing the rank of divisor on general graph. The proof of this result was based on the proof of the NP-hardness of the Problem of finding the minimum recurrent configurations of Chip Firing Game on directed graphs (by Perrot and Pham). In this talk, we will present some (polynomial) algorithms for computing the rank of divisors on some classes of graphs.

  • 20 juin 2017 : 14h30 at Salle de réunion du modulaire (Luminy)
    ‘‘Modélisation d’un système résilient en utilisant une logique non-monotone.’‘
    by Jose Luis Vilchis Medina
    See abstract

    Dans cet exposé, nous présentons un système résilient d’un moto-planeur autonome. Ce type de système a la caractéristique à s’adapter aux perturbations et/ou changement de consignes. Dans ce contexte, nous nous intéressons au pilotage autonome d’aéronefs. Ce type de problème est dit résilient puisque les perturbations “internes” (sécurité et sauvegarde de l’aéronef) et “externes” (changement de conditions atmosphériques) sont des informations capitales à partir desquelles le système doit réagir pour appliquer les actions nécessaires pour atteindre une zone de stabilité ou parvenir à compléter ses différents objectifs (par exemple une trajectoire de vol stable ou un atterrissage d’urgence). Le rôle d’un pilote est alors de contrôler l’aéronef dans des situations incertaines. Nous proposons un modèle basé sur une logique non-monotone, plus spécifiquement la logique des défauts, permettant de gérer l’information incomplete, incertaine et contradictoire. Enfin, nous présenterons un système de contrôle pour le pilotage d’un avion.

  • 12 juin 2017 : 14h00 at Amphi Herbrand (Luminy)
    ‘‘Inférence des causes moléculaires des switches phénotypiques.’‘
    by Célia Biane (IBISC)
    See abstract

    Inférence des déterminants moléculaires des switches phénotypiques. Un défi majeur de la recherche contre le cancer est de déterminer les mutations génétiques responsables des phénotypes cancéreux des cellules et inversement, des actions de médicaments permettant l’initiation de la mort de ces cellules cancéreuses. Un tel défi requiert d’établir des relations causales entre les effets moléculaires des mutations et des médicaments à leur conséquence sur les phénotypes. Nous proposons un cadre théorique où les mutations et les actions des médicaments sont représentées comme des modifications topologiques des réseaux moléculaires provoquant une reprogrammation du phénotype cellulaire. Nous introduisons les réseaux Booléens contrôlés qui permettent l’implémentation d’actions topologiques par des variables de contrôle et proposons un algorithme d’inférence des actions minimales causales permettant d’atteindre des comportements attendus aux états stables de la dynamique. Enfin, nous validons notre approche sur un modèle de régulation du switch apoptosis/prolifération en inférant de façon automatique des gènes causaux et des cibles thérapeutiques du Cancer du Sein.

    Inference of the molecular determinants of phenotypic switches. A major challenge in cancer research is to determine the genetic mutations causing the cancerous phenotype of cells and conversely, the actions of drugs initiating programmed cell death in cancer cells. However, such a challenge is compounded by the complexity of the genotype-phenotype relationship and requires to relate the molecular effects of mutations and drugs to their consequences on cellular phenotypes. We propose a theoretical framework where mutations and drug actions are seen as topological perturbations of molecular networks inducing cell phenotypic reprogramming. We introduce Boolean control networks where these topological network actions are modelled by control parameters. Based on this framework, we present a new algorithm using abductive reasoning principles that infers the minimal causal topological actions leading to an expected behavior at the stable states of the dynamics. We validate the framework on a model of network regulating the proliferation/apoptosis switch by automatically discovering driver genes and therapeutic targets in Breast Cancer.

  • 16 mai 2017 : 14h30 at Salle de réunion du modulaire (Luminy)
    ‘‘Modélisation déclarative des réseaux de régulation génique dus à R. Thomas, en programmation logique “non monotone”.’‘
    by Laurent Trilling (TIMC-IMAG)
    See abstract

    A. Rocca, E. Fanchon, L. Trilling. lab.TIMC-IMAG, Université de Grenoble, France.

    Nous nous intéressons à la modélisation déclarative des réseaux logiques de régulation génique proposés par René Thomas. Par approche déclarative, nous entendons : représentation de toutes les données biologiques disponibles (sur la structure ou la dynamique), sous forme d’axiomes logiques (contraintes) et obtention sous forme intensionelle (implicite) des réseaux de Tomas cohérents avec ces données en cas de satisfaisabilité. Pour ce faire, nous nous appuyons sur la technologie de programmation logique ASP (Answer Set Programming). Cette technologie est basée sur une logique non monotone n’autorisant que certains types de modèles logiques, dits stables: intuitivement, ne sont vrais que les atomes qui sont prouvables grâce aux axiomes. Un modèle stable est minimal en ce sens que de la suppression d’un atome d’un modèle ne peut résulter un modèle.

    Nous présenterons les grandes lignes de cette spécification logique en soulignant les choix de modélisation et en mettant en évidence, à l’aide d’exemples, les avantages de l’approche, comme la réparation automatique d’inconsistance ou l’apprentissage de toutes les propriétés, restreintes à une formulation fixée (par exemple les clauses d’une taille limitée sur un ensemble déterminé d’atomes), déductibles de tous modèles cohérents avec les données.

    Par ailleurs, nous aborderons l’apport de la non monotonie de la logique sous-jacente à ASP. Deux avantages généraux d’ASP sont reconnus : un traitement des données incomplètes radical (les atomes non prouvables sont réputés faux) et un pouvoir de déduction augmenté (les modèles stables forment un sous-ensemble des modèles). Nous nous consacrerons plutôt à trois aspects précis : 1) l’utilisation de défauts pour spécifier la réparation d’inconsistance en montrant l’intérêt d’exprimer la minimisation sous-jacente en termes logiques (et non pas algorithmiques), 2) l’emploi (et la méthodologie de construction) d’une conjonction de défauts originale pour exprimer la notion de composition d’interactions géniques seulement généralement vraie (i.e. sauf à être prouvée effectivement fausse), 3) la mise en œuvre de formules CTL générales, en particulier du type AF (indispensables pour exprimer des propriétés exhaustives sur les comportements), en prenant appui sur la minimalité des modèles stables.

  • 24 avril 2017 : 10h00 at Salle de réunion du modulaire (Luminy)
    ‘‘Sandpiles and graph polynomial.’‘
    by Kévin Perrot
    See abstract

    We will first play with a sandpile simulator and exhibit its surprising algebraic properties, then see how sand dynamics can be used to talk about the graph itself and progress towards the definition of a directed analogue to the Tutte polynomial.

    Joint work with Trung Van Pham, “Chip-Firing game and partial Tutte polynomial for Eulerian digraphs”, Electronic Journal of Combinatorics, volume 23, issue 1, 2016.

  • 14 février 2017 : 14h15 at Salle de réunion du modulaire (Luminy)
    ‘‘Domptage de substitutions bi-dimensionnelles.’‘
    by Timo Jolivet
    See abstract

    Le mot “substitution” correspond à plusieurs notions subtilement différentes, mais toutes liées à l’auto-similarité. Nous verrons comment aller d’une définition rigide/géométrique vers une définition plus flexible/combinatoire, en illustrant le tout par des applications et beaucoup d’exemples.

  • 31 janvier 2017 : 14h15 at Salle de réunion du modulaire (Luminy)
    ‘‘Des logiques non-monotones aux systèmes dynamiques discrets (SDD).’‘
    by Pierre Siegel
    See abstract

    Du point de vue logique et représentation des connaissances, un système biologique peut être considéré comme un ensemble d’éléments qui interagissent entre eux. Par exemple une cellule est un ensemble de protéines/gênes qui interagissent pour la faire survivre se reproduire et mourir. Pour l’Intelligence Artificielle la cellule pose des problèmes intéressants. Il faut d’abord formaliser les interactions, mais une formalisation en logique « classique » est difficile car elle donne des incohérences. Ensuite ce que l’on sait vient en grande partie d’expériences longues et coûteuses. On ne connaît donc qu’une petite partie des interactions et cette connaissance peut être révisable, incertaine, contradictoire et fausse. Il faut aussi essayer de compléter les interactions in-silico. D’autre part la complexité algorithme est importante et il est nécessaire de donner des techniques pour donner des temps de calcul raisonnables dans la pratique. Ces questions sont étudiées depuis longtemps en IA en utilisant en particulier des logiques non-monotones et des techniques issues de la programmation par contraintes. Des résultats ont été obtenus avec Andrei Doncescu et Tan Le [1] en utilisant la logique des défauts.

    D’un autre côté, les systèmes biologiques peuvent être étudiés dans le contexte des réseaux d’automates et des SDD. Des théorèmes fondateurs ont porté sur les cycles d’interactions et leur étude est fondamentale. Mais une représentation des SDD par la logique des défauts (et par la plupart des logiques non-monotones) n’est pas adaptée. Par exemple l’équivalent d’un circuit impair n’a pas d’extension (de solution, de point fixe..). Cette absence d’extension pour les logiques des défauts a été étudiée avec Camilla Schwind [2]. Cette étude a donné la Logique des Hypothèses. Pour cette logique on a toujours des extensions mais certaines de ces extensions, bien caractérisées (les extensions fantômes) sont spéciales et leur utilité n’était pas claire.

    Avec Sylvain Sené et Andrei Doncescu nous étudions une représentation des SDD par la logique des hypothèses. Un but est de permettre de discriminer les états stables, les cycles stables et les cycles instables. Les extensions fantômes semblent permettre de le faire. Un autre but est de donner des algorithmes efficaces pour calculer les cycles stables et instables. Quelques premiers résultats seront présentés.

    [1] Andrei Doncescu and Pierre Siegel. Emerging Trends in Computational Biology, Bioinformatics, and Systems Biology, chapter DNA Double-Strand Break–Based Nonmonotonic Logic, pages 409–427. In Emerging Trends in Computer Science and Applied Computing. Elsevier, August 2015.

    [2] P. Siegel, C. Schwind (93) Modal logic based theory for nonmonotonic reasoning. Journal of Applied Non classical Logic, vol 3 - n° 1/1993, P 73-92.

  • 17 janvier 2017 : 14h30 at Salle de réunion du modulaire (Luminy)
    ‘‘Let’s compute through infinite time!’‘
    by Sabrina Ouazzani (LACL)
    See abstract

    In this talk, we present infinite time Turing machines (ITTM), from the original definition of the model to some new infinite time algorithms.

    We will present algorithmic techniques that allow to highlight some properties of the ITTM-computable ordinals. In particular, we will study gaps in ordinal computation times, that is to say, ordinal times at which no infinite time program halts.

  • 9 janvier 2017 : 16h30 at Salle de réunion du modulaire (Luminy)
    ‘‘The gentleness of perturbations and the topological classification of quantum walks.’‘
    by Christopher Cedzich (University of Hannover)
    See abstract

    In this talk I present a topological classification of symmetric one-dimensional quantum walks. For each set of symmetries of the tenfold way, different classes of quantum walks are distinguished by a topological number, called the symmetry index of the walk. Like for systems in continuous time, this classification proves stable under perturbations homotopic to the identity (so-called gentle perturbations). Moreover, I will show that stability against non-gentle perturbations can be achieved and additional invariants are introduced which no not have a counterpart in the Hamiltonian case. As an application I will provide a simple proof of bulk-edge correspondence for one-dimensional quantum walks.



    Bulk-Edge Correspondence of one-dimensional Quantum Walks
    C. Cedzich, F. A. Grünbaum, C. Stahl, L. Velázquez, A. H. Werner and R. F. Werner
    Journal of Physics A: Mathematical and Theoretical 49(21): 21LT01, 2016.

    A topological classification of one-dimensional symmetric quantum walks
    C. Cedzich, T. Geib, F. A. Grünbaum, C. Stahl, L. Velázquez, A. H. Werner and R. F. Werner
    In preparation.

  • 13 décembre 2016 : 14h00 at Salle de réunion du 3e étage de la FRUMAM (Saint-Charles).
    ‘‘Points fixes dans les réseaux booléens monotones.’‘
    by Adrien Richard (I3S)
    See abstract

    Les réseaux booléens sont des systèmes dynamiques où chaque variable ne peut prendre que deux états possibles: 0 ou 1. Depuis les travaux pionniers de Kauffman et Thomas, ce sont des modèles très classiques pour les réseaux de gènes. Dans ce contexte, les points fixes sont d’un intérêt particulier: ils correspondent à des patterns stables d’expression des gènes souvent reliés à des fonctions cellulaires bien précises. Cependant, les premières informations disponibles sur un réseau de gènes concernent généralement le graphe d’interaction du réseau et non sa dynamique. Une question naturelle est donc la suivante: que peut-on dire sur les points fixes d’un réseau booléen en fonction de son graphe d’interaction seulement ? Dans cette exposé, on présente une étude du plus grand nombre de points fixes qu’un réseau booléen monotone peut admettre en fonction de son graphe d’interaction. On donnera des bornes inférieures et supérieures qui ne dépendent que de la structure des cycles du graphe d’interaction. Les deux paramètres centraux seront, d’une part, la taille d’un plus petit ensemble de sommets intersectant tous les cycles et, d’autre part, le plus grand nombre de cycles disjoints. L’étude fera intervenir des théorèmes, classiques en combinatoire, sur le treillis booléen et ses antichaines. C’est un travail réalisé en collaboration avec Julio Aracena et Lilian Salinas (Université de Concepcion, Chili) disponible à l’adresse suivante: http://arxiv.org/abs/1602.03109.

  • 11 octobre 2016 : 14h00 at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Marches quantiques : simulation d’un fluide relativiste.’‘
    by Mohamed Hatifi (Institut Fresnel)
    See abstract

    L’avènement de la physique quantique et des principes de relativité ont permis une meilleure compréhension du monde dans lequel nous vivons. La physique étant une science expérimentale, il est souvent nécessaire, dans un premier temps, d’avoir recours aux modélisations numériques. L’objet de cette présentation est de mettre au goût du jour la notion de fluide relativiste et de montrer comment nous pouvons le modéliser en utilisant un modèle basé sur les marches quantiques aléatoires. En quelques mots, ces marches sont définies comme analogue des marches classiques et sont depuis peu utilisées dans un large panel d’application: de l’optimisation d’algorithmes quantiques aux simulations de systèmes sans équivalents classiques. Il sera utile dans un premier temps de rappeler les concepts théoriques liés à ces marches, puis dans un deuxième temps, nous appliquerons ce formalisme à un cas particulier de solution puis nous interprèterons les résultats en s’appuyant sur des concepts d’hydrodynamique et d’optique géométrique.

  • 4 mai 2016 : 14h00 at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Influence et causalité dans les simulations de Kappa.’‘
    by Ioana Cristescu (Postdoc Harvard Medical School)
    See abstract

    Kappa est un language formel pour décrire l’interaction entre protéines. Les réactions moléculaires sont représentées par des règle de réécriture sur des graphes. À chaque règle on associe un taux cinétique, qui est la vitesse de la réaction. Le simulateur de Kappa, Kasim, va engendrer des simulations stochastiques à partir d’un ensemble de règles et d’un graphe initial. Un événement de la simulation consiste en une règle et une injection de cette règle dans le graphe. KaSim intègre aussi des outils qui permettent des analyses statiques et dynamiques du système. Au cours de mon exposé je vous présenterai ces outils, qui nous permettrons de parler des relations d’influence, de causalité ou de temporalité entre ces événements. Souvent, on construit un modèle Kappa à partir d’un texte biologique. Toutefois, certains affirmations, comme influence d’un processus sur un autre, ne peuvent être représentées comme des règles de réécriture. Plutôt que décrire un comportement, ces affirmations servent à vérifier la validité du système. Intégrer ces affirmations dans le modèle fait partie de mon travail en cours. On regardera comment on peut utiliser les relations entre événements induits par l’analyse statique et dynamique pour vérifier les affirmations d’influence.

  • 13 avril 2016 : 13h30 at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Self-shuffling words.’‘
    by Svetlana Puzynina (ENS Lyon)
    See abstract

    An infinite word x is self-shuffling, if x admits factorizations: $x=\prod_{i=1}^\infty U_iV_i=\prod_{i=1}^\infty U_i=\prod_{i=1}^\infty V_i$, where U_i,V_i are finite words. In other words, there exists a shuffle of x with itself which reproduces x. W­­e prove that many important and well studied words are self-shuffling: This includes the Thue-Morse word and all Sturmian words except Lyndons. We further establish a number of necessary conditions for a word to be self-shuffling, and show that certain other important words (including the paper-folding word and infinite Lyndon words) are not self-shuffling. This new notion has some unexpected applications: As a consequence of our characterization of self-shuffling Sturmian words, we recover a number theoretic result, originally due to Yasutomi, on a classification of pure morphic Sturmian words in the orbit of the characteristic. Finally, we provide a positive answer to a recent question by T. Harju whether square-free self-shuffling words exist and discuss self-shuffling in a shift orbit closure.

  • 12 avril 2016 : 14h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Méthodes de modélisation algébrique et d’analyse des réseaux de régulation biologique.’‘
    by Maxime Folschette (I3S)
    See abstract

    La modélisation qualitative des réseaux de régulation biologique consiste à représenter les systèmes d’interactions sous forme d’automates et de paramètres discrets plutôt que d’équations différentielles continues. Cela a permis de grandement réduire la complexité de l’analyse des comportements dynamiques des modèles en passant d’un cadre continu à un cadre discret ou hybride. Au cours de ce séminaire, je présenterai mes travaux dans le domaine de la modélisation et de l’analyse dynamique des modèles biologiques discrets. Ceux-ci se concentrent sur différentes sous-classes des modèles d’automates, dont fait notamment partie le très répandu modèle de Thomas, et sur différentes méthodes pour étudier leur comportement dynamique. Je présenterai notamment une méthode d’analyse statique par interprétation abstraite, qui permet de vérifier des propriétés d’accessibilité dans de très grands modèles avec une complexité très faible, ainsi qu’une approche reposant sur le µ-calcul polyadique, qui est une extension des logiques temporelles classiques (LTL et CTL) permettant de représenter une plus large palette de propriétés dynamiques.

  • 11 avril 2016 : 14h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Des automates cellulaires réversibles aux transformations causales et quantiques de graphes.’‘
    by Simon Martiel (Postdoc LSV, Paris)
    See abstract

    Les automates cellulaires décrivent l’évolution d’une grille discrète sous des contraintes inspirées de la physique: une portion bornée de la grille contient une quantité bornée d’information, l’information voyage à vitesse bornée au sein de la grille, et les lois d’évolutions de la grille sont les mêmes en tout endroit et tout temps. Un résultat élégant de la théorie des automates cellulaires réversibles (ACR) est que tout ACR peut être décrit comme un circuit de profondeur bornée d’opérations locales et réversibles. Dans cette présentation nous présenterons ce résultat, ainsi qu’une généralisation de celui-ci à un modèles d’automates cellulaires sur géométries dynamiques: les dynamiques causales de graphes. Enfin nous montrerons comment ce résultat peut-être utilisé pour caractériser d’une part les Automates Cellulaires Quantiques, et d’autre part les dynamiques causales quantiques.

  • 5 avril 2016 : 14h45 at Amphi 12, Luminy
    ‘‘Optimality of entropic uncertainty relations.’‘
    by Philippe Raynal (National University of Singapore)
    See abstract

    Heisenberg’s uncertainty principle states that, for any quantum state, the probability distributions of two non-commuting observables cannot be arbitrarily and simultaneously peaked. A famous example is the tradeoff between Which-Path information and Interference strength in a two-path interferometer, an instance of wave-particle duality. The modern form of the uncertainty principle is due to Robertson and takes the form of an inequality relating the standard deviations of the two distributions and the commutator of the two corresponding observables. Uncertainty relations can also be expressed in terms of other measures of information like Shannon and Réniy entropies. However, the entropic uncertainty relation derived by Maassen and Uffink, a lower bound on the sum of two entropies for an arbitrary pair of observables, is not optimal in the sense that in general the inequality cannot be saturated.

    Our goal is to find optimal entropic uncertainty relations in finite dimensions. Therefore in this talk, we will go beyond the Maassen and Uffink relation to investigate the curve of minimal entropy. We will disproof a conjecture, generalise various results, and propose new conjectures.

    Article: K. Abdelkhalek, R. Schwonnek, H. Maassen, F. Furrer, J. Duhme, P. Raynal, and B.-G. Englert, and R. F. Werner
    Int. J. Quantum Inform. 13, 1550045 (2015)

  • 5 avril 2016 : 10h at Salle de réunion du 5e (TPR1, entrée G, 5e étage)
    ‘‘Autour de la connexité dans les graphes avec conflits.’‘
    by Benjamin Momège (Postdoc Inria, Lille)
    See abstract

    Nous nous intéresserons aux graphes avec conflits (un conflit est une paire d’arêtes ne pouvant pas simultanément faire partie d’un sous-graphe), dans lesquels nous étudierons différents types de problèmes, de nature aussi bien algorithmique que combinatoire, notre ligne directrice étant la notion de connectivité. Nous verrons que plusieurs résultats, simples sans conflit, ne le sont plus lors de l’ajout de conflits. Nous présenterons : des algorithmes exacts (non polynomiaux), des résultats de NP-complétude, et des conditions suffisantes assurant l’existence de certains objets (arbre couvrant, chemin et cycle Hamiltonien) sans conflits.

  • 4 avril 2016 : 16h30 at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Introduction au calcul uniforme : élection de leader sur les automates cellulaires à entrée périodique.’‘
    by Nicolas Bacquey (ATER GREYC, Caen)
    See abstract

    Tous les modèles de calcul usuels présentent une “singularité” qui permet de démarrer un calcul : tête d’une machine de Turing, état initial, cellule au bord de la configuration d’un automate cellulaire… Est-il possible de définir une notion de calcul sur un modèle dénué d’un maximum de ces singularités ? Comment présenter l’entrée, comment lire un résultat ? Comment définir une complexité ?

    On tentera de répondre à ces questions dans le modèle de calcul des automates cellulaires à configuration périodique, modèle dans lequel à la fois la donnée et le programme sont uniformes dans l’espace. Plus précisément, on présentera une famille d’algorithmes réalisant l’élection de leader sur ces configurations périodiques.

    Il est impossible d’élire une unique cellule de la configuration par définition ; les algorithmes présentés utilisent des techniques permettant de transformer des différences spatiales en différences temporelles, induisant des ruptures de symétrie. Ainsi, on parvient à élire une unique classe d’équivalence de cellules de la configuration.

  • 21 mars 2016 : 16h30 at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Quantum Walks Gravity Simulation.’‘
    by Giuseppe Di Molfetta (Postdoc Instituto de Fisica Corpuscular (IFIC), Universitat de València)
    See abstract

    As we know, spacetime is not flat at the cosmological scale. In order to describe spacetime, in General Relativity theory (GR), we need a continuous and differentiable manifold and a formal way to account for the continuous distortion of the metrics. The main point is that changing coordinate systems should not affect physics laws (General Covariance). However at the Planck length, matter is not continuous and obeys Quantum Theory (QT). Although one century has passed, finding an intrinsically discrete counterpart of GR is still an open question. In fact, discretized GR does not turn out in just a mere finite difference scheme of the old formula.

    I recently showed that one way to describe a discrete curved spacetime is by using Quantum Walks. From a physical perspective a QW describes situations where a quantum particle is taking steps on a discrete grid conditioned on its internal state (say, spin states). The particle dynamically explores a large Hilbert space associated with the positions of the lattice and allows thus to simulate a wide range of transport phenomena.

    It is surprising that this unitary and local dynamics, defined on a rigid space-time lattice coincides in the continuous limit with the dynamical behavior of a quantum spinning-particle spreading on a curved spacetime. This could really turn out to be a powerful quantum numerical method to discretize GR.

  • 7 mars 2016 : 14h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Etude de la puissance d’expression et de l’universalité des modèles de calcul inspirés par la biologie.’‘
    by Sergiu Ivanov (ATER LACL, Paris)
    See abstract

    In this presentation, we will consider the problems of computational completeness and universality for several biologically-inspired models of computation: insertion-deletion systems, networks of evolutionary processors, and multiset rewriting systems. The presented results fall into two major categories: study of expressive power of the operations of insertion and deletion with and without control, and construction of universal multiset rewriting systems of low descriptional complexity.

    Insertion and deletion operations consist in adding or removing a subword from a given string if this subword is surrounded by some given contexts. The motivation for studying these operations comes from biology, as well as from linguistics and the theory of formal languages. In the first part, we focus on insertion-deletion systems closely related to RNA editing, which essentially consists in inserting or deleting fragments of RNA molecules. We show that allowing one-symbol insertion and deletion rules to check a two-symbol left context enables them to generate all regular languages. Moreover, we prove that allowing longer insertion and deletion contexts does not increase the computational power. We further consider insertion-deletion systems with additional control over rule applications and show that computational completeness can be achieved by systems with very small rules.

    The second part of the presentation is concerned with the universality problem, which consists in finding a fixed element able to simulate the work any other computing device. We start by considering networks of evolutionary processors (NEPs), a computational model inspired by the way genetic information is processed in the living cell, and construct universal NEPs with very few rules. We then focus on multiset rewriting systems, which model the chemical processes running in the biological cell. For historical reasons, we formulate our results in terms of Petri nets. We construct a series of universal Petri nets and give several techniques for reducing the numbers of places, transitions, inhibitor arcs, and the maximal transition degree. Some of these techniques rely on a generalisation of conventional register machines, proposed in this thesis, which allows multiple register checks and operations to be performed in a single state transition.

  • 23 fevrier 2016 : 10h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Calculs universels et comportements asymptotiques en dynamique symbolique.’‘
    by Benjamin Hellouin (Postdoc Andrés Bello University, Santiago)
    See abstract

    L’étude mathématique des systèmes dynamiques cherche à prévoir le comportement à long terme et à grande échelle d’un système à partir d’une information locale et limitée. La plupart des problèmes de prédiction se révèlent cependant indécidables dans le cas général, et la preuve de tels résultats passe souvent par la simulation, au sein du système considéré, de calcul universel sous une certaine forme. Les constructions nécessaires à ces simulations dépendent grandement du problème étudié, ce qui contraste avec l’idée naive d’une Turing-universalité “généraliste” qui rendrait tous les problèmes pertinents indécidables.

    Dans cet exposé, je ferai un panorama de ma recherche portant sur deux systèmes dynamiques discrets suivant cette approche : les automates cellulaires et la fourmi de Langton. Pour les automates cellulaires, le problème étudié est celui de décrire le comportement asymptotique typique partant d’une configuration initiale tirée au hasard. Avec Mathieu Sablik puis Martin Delacourt, nous avons montré que ce problème est indécidable dans le cas général; je comparerai la simulation de calcul universel impliquée dans la preuve de ce résultat avec les nombreuses autres formes connues dans les automates cellulaires, et la manière dont elles sont affectés par certaines restrictions dynamiques. Pour la fourmi de Langton, j’exposerai des travaux en cours en collaboration avec Anahi Gajardo et Diego Maldonado, dans lesquels nous cherchons à mettre en relation la complexité de la trajectoire de la fourmi et sa capacité à simuler du calcul universel sous différentes formes.

  • 22 fevrier 2016 : 14h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Directional Dynamics along Arbitrary Curves in Cellular Automata.’‘
    by Martin Delacourt (ATER LORIA, Nancy)
    See abstract

    This is a joint work with Victor Poupet, Mathieu Sablik and Guillaume Theyssier.

    Cellular automata (CA) are discrete dynamical systems with homogeneous and local evolution rule. We consider the one-dimensional case, that is CA with configurations in X^{Z} for some finite alphabet X. We can study classical dynamical properties like equicontinuity and expansivity, and Petr Kurka proposed in 1997 a classification of all CA according to these properties that describe the flows of informations in the evolutions of a CA.

    The shift is a specific CA that plays a crucial role in the world of CA, and in particular commutes with any other CA. Considering this, Mathieu Sablik gave in 2008 a new classification that considers the properties of equicontinuity and expansivity along linear directions, that is composing the CA with a constant and rational power of the shift. This gave rise to the notions of sets of directions of equicontinuity or expansivity.

    Here we enlarge the scope again and consider every possible direction. We prove a new version of the classification, provide various examples that show that this extension is meaningful and in particular we characterize the real numbers that can be the limit of sets of directions for equicontinuous dynamics.

  • 16 fevrier 2016 : 10h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Coherent activity in excitatory pulse-coupled networks.’‘
    by Simona Olmi (INS, AMU)
    See abstract

    An excitatory pulse-coupled neural network is a network composed of neurons coupled via excitatory synapses, where the coupling among the neurons is mediated by the instantaneous transmission of action potentials. The coherent activity of a neuronal population usually indicates that some form of correlation is present in the dynamics of the considered neurons.

    The role played by the topology in promoting coherent activity in excitatory diluted pulse-coupled neural networks at a microscopic and macroscopic level is investigated. In particular, we consider a diluted random network where neurons were connected as in a directed Erdös-Renyi graph with average connectivity (in-degree) scaling linearly with the number of neurons in the network. In these “massively connected” networks we show that in the infinite size limit the dynamics of coherent collective states coincide with that of fully coupled networks. However, the random dilution of the connections induces inhomogeneities in the neuronal behaviors for any finite system size, promoting a weak form of chaos, which vanishes in the limit of infinite size. In this limit, the random systems exhibit regular (non chaotic) dynamics thus recovering the properties of a homogeneous fully connected network.

    The situation is quite different for a “sparse network” characterized by a constant connectivity (in-degree), independent on the size of the network. In fact, on one side we show that a few tens of random connections are sufficient to sustain a nontrivial collective dynamics. In other words, collective motion is a rather generic and robust property and does not require an extremely high connectivity to be sustained. On an other side, the collective dynamics coexists with a microscopically chaotic dynamics that does not vanish in the thermodynamic limit and turns out to be extensive (i.e. the number of unstable directions is proportional to the network size). Extensive chaos has been already found in spatially extended system with nearest-neighbour coupling (diffusive coupling) induced by the additivity of the system. In this case this property is highly nontrivial, as the network dynamics is non additive and it cannot be approximated as the juxtaposition of almost independent sub-structures.

    Finally the dynamics of two symmetrically coupled populations of pulse-coupled neurons is considered: this is the simplest instance of “network-of-networks”, that is often invoked as paradigm for neural system. Upon varying both the self-coupling and the cross-coupling strengths various kinds of collective states were found: in particular the phase diagram of the system reveals various kinds of symmetric and symmetry broken collective states ranging from splay states to tori, from chimera states to collective chaos.

    S. Olmi, R. Livi, A. Politi and A. Torcini, Physical Review E 81, 046119 (2010).
    L. Tattini, S. Olmi, A. Torcini, Chaos 22, 023133 (2012).
    S.Luccioli, S. Olmi, A. Politi, A. Torcini, Phys. Rev. Lett. 109, 138103 (2012).
    S. Olmi, A. Politi and A. Torcini, EPL 92, 60007 (2010).

  • 15 fevrier 2016 : 14h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Condition combinatoire nécessaire et suffisante pour les corrélations Non-locales Causales.’‘
    by Julien Degorre (PCQC, Paris)
    See abstract

    Using a quantum particle as a support of information has led researchers to redefine the computer science from information theory to algorithm and complexity. A quantum computer can provide a huge advantage over a classical computer for some specific tasks (Shor’s algorithm and Quantum cryptography…), but it is certainly not true for all tasks.

    The problem is, in which case quantum computer is better than classical computer ? How quantifying the power of quantum resources with respect to classical resources ?

    In almost all example where a quantum computer has a clear advantage over classical, it involves quantum non-locality, means a non-signalling correlation stronger than any classical correlation.

    Here to characterize this non-local correlations with respect of the classical one, I will introduce new approach which doesn’t involves any Quantum physics but only combinatory. I will show a simple, necessary and sufficient Combinatorial condition to characterize the Non-signalling (i.e. causal) correlations. Moreover, this approach will give us intuitive view of the structure of causal probabilities distribution, or non signalling correlations.

    NOTE: An effort will done to introduce any prerequisites during the talk to be able to match with an eclectic audience (computer scientist, physicist, math…)

  • 8 fevrier 2016 : 14h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Symmetry in classical logics and its extension to non-monotonic logics and reasoning.’‘
    by Belaid Benhamou (LSIS)
    See abstract

    La symétrie est par définition un concept multidisciplinaire. Il apparaît dans de nombreux domaines allant des mathématiques à l’intelligence artificielle, de la chimie et de la physique. Il révèle des formes et des usages différents, même à l’intérieur du même domaine. En général, il renvoie à une transformation qui laisse invariant (ne pas modifier sa structure fondamentale et / ou ses propriétés ) un objet (un chiffre, une molécule, un système physique, une formule ou un réseau de contraintes). Par exemple, la rotation d’un échiquier jusqu’à 180 degrés donne un échiquier qui est indiscernable de celui d’origine. La symétrie est une propriété fondamentale qui peut être utilisée pour étudier ces différents objets, analyser finement ces systèmes complexes ou réduire la complexité de calcul lorsqu’il s’agit de problèmes combinatoires.

    La symétrie a été bien étudiée dans les logiques classiques et la programmation par contraintes depuis plus d’une décennie. Au début, Krishnamurthy a montré que certaines formules difficiles admettent de courtes démonstrations lors de l’extension du système de preuve par résolution de la logique propositionnelle par la règle de symétrie. Le groupe de Marseille (Benhamou, Sais et Siegel) travaillant sur la symétrie a développé le principe des symétries dans les années 1990, a montré comment les symétries peuvent être détectées et utilisées efficacement dans les solveurs SAT (logique propositionnelle) et solveurs CSP (Benhamou 94). Toutefois, en Intelligence Artificielle, on manipule souvent des informations incomplètes et nous devons inclure l’incertitude pour raisonner avec des connaissances contenant des exceptions et la non-monotonie. Plusieurs logiques non classiques sont introduits à cet effet, mais pour autant que nous savons, la notion de symétrie pour ces cadres n’avaient pas encore été étudiée.

    Dans cet exposé, nous parlerons d’abord de cette notion de symétrie dans les logiques classiques, ensuite nous montrons comment elle est étendue récemment à des logiques non- monotones comme les logiques préférentielles, les X-logiques et la logiques des défauts. Nous donnons de nouvelles règles d’inférence en utilisant la symétrie pour les X-logiques et la logique des défauts. Nous montrons comment mettre en œuvre le raisonnement par symétrie pour ces logiques non-monotones et nous prouvons que certaines symétries qui n’existent pas dans les logiques classiques sont bien présentes dans ces formalismes.

    Enfin, nous avons choisi le cadre des ASP (Answer Set Programming) pour mettre en œuvre et implémenter la symétrie dans le raisonnement non-monotone. L’ASP est un cadre non-monotone très utilisé, il est considéré comme un fragment de la logique des défauts. Nous parlerons ici de la notion des symétries locales et celle des symétries globales. Nous montrons comment les symétries locales d’un programme logique peuvent être détectées de manière dynamique au moyen des automorphismes de sa représentation graphique. Nous donnons également des propriétés qui permettent d’éliminer les symétries dans les solveurs ASP afin d’améliorer leurs efficacités.

  • 1 fevrier 2016 : 14h at Salle de réunion du 6e (TPR1, entrée G, 6e étage)
    ‘‘Approche comportementale pour la biologie : vers une automatisation de la conception des fonctions de synthèse.’‘
    by Adrien Basso-Blandin (Postdoc ENS Lyon)
    See abstract

    La biologie possède une masse de connaissances dont la disparité des données et la fragmentation entraine une difficulté d’appréhension des systèmes dans leur globalité.
    Plus particulièrement, en biologie de synthèse où l’objectif est de concevoir de nouvelles fonctionnalités n’existant pas à l’état naturel à partir de composants existants, la connaissance partielle de ces composants entraine de lourds risques de sécurité et de sureté lors de l’assemblage de nouveaux organismes.

    Dans ce cadre, nous proposons un grand axe majeur centré sur la définition d’une tour de modèles formels permettant dans le cas le plus abstrait une description comportementale des fonctionnalités des systèmes et dans celui le plus concret de décrire les interactions mécanistiques entre composants élémentaires.

    L’objectif à terme est de proposer à la communauté des biologistes un ensemble d’outils d’aide à la décision permettant l’agrégation de connaissances biologiques en une unique représentation de connaissances, puis l’inférence de nouvelles connaissances ainsi que la validation et la vérification formelle et in-vitro lors de la conception de nouvelles fonctions biologiques.

  • 16 novembre 2015 : 14h30 at Salle de séminaire du 5e au LIF (TPR1, entree G, 5e etage)
    ‘‘Computational complexity of majority boolean networks under different updating schemes’‘
    by Pedro Montealegre (PhD LIFO, Orléans)
    See abstract

    Given a threshold boolean network, as well as an updating scheme over its vertices, we study the computational complexity associated with the prediction of the future state of a vertex. An updating scheme can be synchronous (each vertex is updated at the same time), sequential (vertices are updated one by one in some fixed order) or block-sequential. We show that the prediction problem for synchronous and sequential updating schemes is P-Complete even when the input graph is cubic (3-regular) and is PSPACE-Complete for block sequential updating schemes.

  • 16 juin 2015 : 14h at Amphi 12 (bât. B, Luminy)
    ‘‘Intrinsic universality of causal graph dynamics’‘
    by Simon Martiel (PhD I3S, Nice)
    See abstract

    Causal Graph Dynamics generalize Cellular Automata, extending them to bounded degree, time varying graphs. The dynamics rewrites the graph in discrete time-steps, with respect to two physics-like symmetries: causality (there exists a bounded speed of information propagation) and shift-invariance (the rewriting acts everywhere the same). Intrinsic universality is the ability of the instance of a model to simulate all other instances, while preserving the structure of the computation. We present here an intrinsically universal family of Causal Graph Dynamics, and give insights on why it seems impossible to improve this result to the existence of a unique intrinsically universal instance.

  • 20 mai 2015 : 14h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Quantum processes: an introduction’‘
    by Cédric Bény (ITP, Hannover)
    See abstract

    Nature is quantum. One essential way in which quantum theory differs from classical probability theory is that an unknown state cannot be copied. In other words, quantum information is conserved. This has profound consequences. For instance, it explains why quantum phenomena are hard to detect: any random interaction between a quantum system and its environment will take away information which cannot also be shared with an observer without being classical.

  • 11 mai 2015 : 14h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Reversible Causal Graph Dynamics’‘
    by Pablo Arrighi
    See abstract

    Causal Graph Dynamics extend Cellular Automata to arbitrary, bounded-degree, time-varying graphs. The whole graph evolves in discrete time steps, and this global evolution is required to have a number of physics-like symmetries: shift-invariance (it acts everywhere the same) and causality (information has a bounded speed of propagation). We study a further physics-like symmetry, namely reversibility. Joint work with: Simon Martiel, Simon Perdrix.

  • 27 avril 2015 : 14h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘l’Oritatami, un modèle de pliage co-transcriptionel’‘
    by Pierre-Etienne Meunier (Postdoc Aalto, Helsinki)
    See abstract

    Les molécules essentielles du vivant (ARN, protéines) sont produites par pliage de chaînes (de nucléotides, d’acides aminés) linéaires, et leur géométrie une fois pliées est d’importance primordiale pour l’accomplissement de leurs fonctions.

    De nombreux modèles ont été proposés pour comprendre comment ce pliage s’effectue, mais ils ont tous ignoré un aspect essentiel du mécanisme de pliage : le fait que les molécules commencent à se plier pendant qu’elles sont transcrites. Ce détail change radicalement la complexité du modèle : dans les modèles de pliage précédents (le modèle HP, par exemple), le problème de prévoir la conformation la plus probable est NP-⁠complet. Or, notre compréhension actuelle de la physique (calcul quantique) semble contredire que toutes les cellules du vivant résolvent ce type de problèmes rapidement pour produire les molécules dont elles ont besoin.

    L’Oritatami est un modèle qui tient compte de ce phénomène; notre principal objectif jusqu’à maintenant a été de programmer des structures, c’est-⁠à-⁠dire de comprendre les molécules “de l’intérieur”, en essayant d’en créer de nouvelles plutôt qu’en les observant de l’extérieur.

    Bonus : en m’invitant au LIF, vous gagnez un accès gratuit et illimité à un jeu en ligne : http://users.ics.aalto.fi/~meunier/oritatami.hml

  • 13 avril 2015 : 14h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Fractals, indécidabilité et automates à plusieurs rubans’‘
    by Timo Jolivet (Postdoc IMT, Toulouse)
    See abstract

    On démontre que la propriété “être d’intérieur vide” est indécidable pour une famille simple et naturelle de fractals (définis par des systèmes de fonctions itérées affines 2D). Les méthodes utilisées font intervenir des automates à plusieurs rubans et une variante du problème de correspondance de Post. Ce travail a été réalisé en collaboration avec Jarkko Kari.

  • 23 mars 2015 : 14h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Une (petite) promenade formelle sur les chemins du raisonnement et de l’argumentation’‘
    by Vincent Risch (LSIS)
    See abstract

    Après un rappel de quelques approches canoniques proposées ces dernières années en IA pour la formalisation du raisonnement et de l’argumentation, cet exposé sera consacré à la présentation d’un calcul issu des X-logiques [Siegel, Forget, 96], et destiné à la simulation d’un échange argumentatif entre deux agents formels. J’aborderai la question d’une articulation entre raisonnement et argumentation à partir de la représentation d’un agent artificiel raisonnant sur un ensemble d’attitudes possibles face à un argument donné, et comme préliminaire à la génération d’un nouvel argument donné en réponse par cet agent. En particulier, à partir du caractère paraconsistant des X-logiques, il est facile d’exhiber la matrice non–déterministe d’une logique quadri-valuée, matrice dont découle directement un calcul de type n–séquents. La réduction à un calcul de séquents classiques peut alors être opérée à partir de la méthode proposée par [Avron, Ben-Naim, Konikowska, 09]. Au final, la logique obtenue se présente comme une généralisation de la logique Source Processeur La Plus Générale (Most General Source-Processor Logic), ce qui permet en retour de considérer l’utilisation de cette dernière au sein de notre propre système argumentatif. Un lien inattendu avec la cumulatitivité de la X-logique sous-jacente est établi.

  • 09 mars 2015 : 14h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Quelques axes de recherche de l’équipe MEB (Mathématiques, Évolution, Biologie)’‘
    by Gilles Didier (I2M)
    See abstract

    Sans avoir l’ambition d’être complètement exhaustive, la présentation exposera plusieurs thèmes de recherche actuellement explorés au sein de l’équipe “Mathématiques, Evolution, Biologie” de l’I2M, notamment:
    - La reconstruction d’états ancestraux (discrets et continus),
    - L’estimation des taux de spéciation-extinction à partir de données fossiles,
    - La mise en évidence de signatures génomiques d’événement de convergence évolutive,
    - La recherche de communautés dans les graphes biologiques…

  • 19 janvier 2015 : 14h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Un peu de logique pour l’Intelligence Artificielle et utilisation à l’étude des voies de signalisation cellulaire’‘
    by Pierre Siegel
    See abstract

    L’exposé donne une introduction rapide à l’Intelligence Artificielle et à la représentation des connaissances en IA. On s’intéresse plus particulièrement aux logiques non monotones qui veulent traitent de l’information incomplète ou incertaine. On applique cela à la représentation et l’étude des voies de signalisation dans la cellule cancéreuse. On parlera aussi un peu d’algorithmes pratiquement utilisables.

  • 12 janvier 2015 : 14h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Réseaux d’automates et questions diverses’‘
    by Sylvain Sené

  • 17 avril 2014 : 10h30 at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Joint Diagnosability of Distributed Discrete Event Systems’‘
    by Lina Ye (Postdoc INRIA CONVECS, Grenoble)
    See abstract

    Diagnosis reasoning is to detect possible faults that can explain the observations. The possibility to achieve such a diagnosis reasoning depends on the diagnosability of the system. Diagnosability is a crucial system property determining at design stage how accurate any diagnosis algorithm can be on a partially observable system. Most existing approaches for diagnosability analysis require the global order of observable events, which is however not always available. Hence, we study the systems where each component can only observe its own observable events to keep the internal structure private in terms of observations. First, we propose a new definition called joint diagnosability that requires only the local order of observable events. Second, we prove that verifying joint diagnosability is an undecidable problem when communications between different components are not observable. Third, we provide a sufficient algorithm to check this property. Finally, we show that this problem is decidable when communications are observable.

  • 15 avril 2014 : 11h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Ensembles limites d’automates cellulaires associés à une mesure de probabilité’‘
    by Martin Delacourt (Postdoc CMM UChile, Santiago)
    See abstract

    Un automate cellulaire est un système dynamique composé d’une infinité de cellules qui ont un état choisi parmi un ensemble fini, n’interagissent qu’avec leurs voisines et évoluent de manière synchrone au moyen d’une règle commune. On s’intéresse au comportement asymptotique d’un tel objet, c’est à dire à l’ensemble des états globaux accessibles arbitrairement tard : l’ensemble limite. C’est un objet très étudié, avec de nombreux résultats à la clé. Ici, on se donne de plus une mesure de probabilité sur l’ensemble des états et on regarde l’ensemble des états du système accessibles à la fois arbitrairement tard et souvent. On s’intéressera aux questions de structure et aux propriétés de calculabilité de cet objet.

  • 11 avril 2014 : 9h30 at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Variabilité spatio-temporelle des épidémies: application au paludisme et au choléra’‘
    by Jean Gaudart (MCU-PH SESSTIM, AMU)
    See abstract

    Aujourd’hui, parmi les 106 pays où la transmission du paludisme est en cours, 81 pays mettent l’accent sur le contrôle, alors que 25 sont dans la phase de pré-élimination/élimination. Une des principales causes de l’échec des programmes de lutte est la forte hétérogénéité de la dynamique de transmission du paludisme. Entre la variabilité du climat, la dynamique des sociétés et le parasite il est souvent difficile d’identifier le poids et le rôle des différents facteurs de risque.

    Pour comprendre la dynamique de transmission du paludisme à l’échelle locale il est nécessaire d’analyser finement la cartographie dynamique des cas de paludisme en lien avec l’environnement.

    Tout d’abord, à l’échelle d’un village (Bancoumana, Mali), nous avons recherché des zones de risques différents. Pour cela il a été nécessaire de développer une méthode de découpage oblique du plan (SpODT), détectant de « frontières » entre ces zones.

    Pour mieux comprendre la relation pluie-paludisme, nous avons développé un modèle dynamique de transmission conduit par la pluviométrie, permettant de reproduire l’évolution temporelle des cas de paludisme, ainsi qu’un modèle de réaction-diffusion pour représenter la diffusion spatiale au sein d’un village.

    Cette meilleure connaissance de la dynamique du paludisme nous a conduits à proposer de nouvelles stratégies de lutte fondées sur la notion de diffusion à partir de réservoirs actuellement en cours d’évaluation au Sénégal.

    Le choléra est généralement considéré comme le prototype de la maladie liée à l’eau, en particulier du fait que Vibrio cholerae, l’agent du choléra, est d’abord un germe de l’environnement capable de se développer dans les eaux saumâtres des estuaires. Cette bactérie tolère aussi l’eau douce, surtout si la faible salinité est compensée par une chaleur importante et la présence de nutriments. De nombreuses études ont mis en évidence le caractère saisonnier du choléra. En octobre 2010 une épidémie de choléra est déclarée en Haiti. Elle deviendra la plus importante épidémie de choléra avec 493 069 cas et 6 293 décès en 1 an. Dès le départ, des modélisations mathématiques ont été publiées, mais, ne tenant pas compte de la réalité épidémiologique notamment du mode de démarrage, les prévisions étaient fausses au moment même de la publication. L’analyse précise du démarrage épidémique et la relation avec l’environnement a permis de démontrer l’importation de la maladie à partir du Népal, l’aspect violent du démarrage dans le bas Artibonite due à une contamination brutale et transitoire du fleuve, sans aucun lien avec une pluviométrie faible. Par contre, la dynamique de transmission c’est ensuite modifiée, plus liée à la pluie, tout en diminuant progressivement. Là encore, la connaissance de la dynamique de transmission a permis de proposer une stratégie de lutte ciblée actuellement en cours et soutenue par l’UNICEF, qui nous amènera à l’élimination à court terme.

    Gaudart J, Rebaudet S, Barrais R, Boncy J, Faucher B, Piarroux M, Magloire R, Thimothe G, Piarroux R. Spatio-temporal dynamics of cholera during the first year of the epidemic in Haiti. PLoS Negl Trop Dis. 2013 Apr 4;7(4):e2145.


    Piarroux R, Barrais R, Faucher B, Haus R, Piarroux M, Gaudart J, Magloire R, Raoult D. Understanding the cholera epidemic, Haiti. Emerg Infect Dis. 2011 Jul;17(7):1161-8.


    Gaudart J, Poudiougou B, Ranque S, Doumbo O. Oblique decision trees for spatial pattern detection: optimal algorithm and application to malaria risk. BMC Med Res Methodol. 2005 Jul 18;5:22.


    Gaudart J, Poudiougou B, Dicko A, Ranque S, Toure O, Sagara I, Diallo M, Diawara S, Ouattara A, Diakite M, Doumbo OK. Space-time clustering of childhood malaria at the household level: a dynamic cohort in a Mali village. BMC Public Health. 2006 Nov 21;6:286.


    Gaudart J, Touré O, Dessay N, Dicko AL, Ranque S, Forest L, Demongeot J, Doumbo OK. Modelling malaria incidence with environmental dependency in a locality of Sudanese savannah area, Mali. Malar J. 2009 Apr 10;8:61.


    Gaudart J, Ghassani M, Mintsa J, Rachdi M, Waku J, Demongeot J. Demography and diffusion in epidemics: malaria and black death spread. Acta Biotheor. 2010 Sep;58(2-3):277-305.


  • 10 avril 2014 : 15h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Fragments de mathématiques discrètes’‘
    by Michelangelo Bucci (Postdoc LIRMM, Montpellier)
    See abstract

    A la frontière entre l’informatique et les mathématiques, les mathématiques discrètes sont un domaine de recherche fascinant qui a des liens avec de nombreuses branches des deux disciplines. L’un des aspects les plus intéressants des mathématiques discrètes est en fait leur nature multidisciplinaire. Au cours du séminaire j’essayerai de mettre en évidence la façon dont cet aspect donne souvent de bons résultats lorsque les mathématiques discrètes entrent en contact avec d’autres domaines de recherche.

    Dans la première partie du séminaire, nous allons voir comment des résultats même très abstraits peuvent avoir de surprenantes applications pratiques et comment, vice-versa, les domaines d’application peuvent être une source d’inspiration pour le développement de nouvelles questions mathématiques.

    Dans la deuxième partie du séminaire, nous allons discuter de certains outils et des questions qui pourraient prendre avantage de la mise au point de nouveaux outils mathématiques discrets.

    Le séminaire mettra l’accent, en particulier, sur le domaine de la combinatoire des mots et de la théorie des réseaux, avec une attention particulière aux problèmes d’intérêt biologique et médical.

    Aucune connaissance mathématique particulière ne sera nécessaire, seulement des connaissances d’algèbre de base.

  • 13 mars 2014 : 10h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Modeling the expression waves during the mouse segmentation’‘
    by Aitor Gonzalez (Postdoc TAGC, AMU)
    See abstract

    The vertebrate segmentation relies on oscillation of gene expression in presomitic mesodermal (PSM) cells that are synchronized by Notch pathway-dependent coupling. The phase of these oscillations is delayed in the anterior PSM cells relative to the posterior PSM cells (called here anterior phase shift). This anterior phase shift is commonly attributed to an anteriorly increasing period profile. In mouse, a crucial mechanism of the oscillators is the autoinhibitory feedback with delay of the Hes7 gene. However it is unclear how the anterior phase shift is regulated. Here, we find that a coupled delay differential equation (DDE) model of Hes7 reproduces the anterior phase shift if we assume an anterior-posterior gradient of coupling strength, intercellular delay or transcription rate. This model predicts smaller anterior phase shift for lower anterior values of these parameters, and this agrees with timelapse imaging of Hes7 promoter activity in Lfng KO embryos. This model also predicts longer segmentation period and smaller phase shift if the gradient of these parameters is shifted posteriorly. In agreement with these predictions, Fgf inhibitors shift the anterior-posterior Dll1 mRNA gradient posteriorly, increase the segmentation period and decrease the anterior phase shift. In summary, coupling and an anterior-posterior gradient of the Notch pathway might be important elements to explain the anterior phase shift of the segmentation clock.

  • 06 mars 2014 : 10h30 at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Reaction networks with delays applied to toxicity analysis’‘
    by Cinzia Di Giusto (Postdoc IBISC, Évry)
    See abstract

    Toxicology studies the adverse effects of the exposures to chemicals at various levels of living entities. I will propose a framework that aims at discovering the molecular mechanisms of toxicity. More precisely, I will introduce a modular modelling environment, called RaNDy for Reaction Networks with Delays. In RaNDy, systems consist of a set of species present in the environment at a given level. Species can degrade as time passes by and their presence is governed by a set of rules (reactions). In a reaction, species can have the role of reactants, inhibitors or products. A reaction has a given duration, and it can take place only if all reactants are available and all inhibitors are not for the whole duration of the reaction. Depending on the type of reaction, products levels are either increased or decreased. I will show how to model toxicogenomics problems, namely deregulation of homoeostatic processes, into formulae of a suitable temporal logic like CTL. The approach is applied to the study of the impact of the aspartame assimilation into the blood glucose regulation process.

  • 17 décembre 2013 : 15h at Salle de séminaire du LIF (TPR1, entree G, 6e etage)
    ‘‘Auto-assemblage non-coopératif de chemins et de carrés’‘
    by Pierre-Étienne Meunier (Postdoc LIAFA, Paris)
    See abstract

    L’auto-assemblage est un modèle de formation de structures moléculaires, capable de calcul Turing, mais aussi implémentable en pratique à l’aide de brins d’ADN. Dans cet exposé, je m’intéresserai à la variante non-coopérative de ce modèle, qui modélise une forme de croissance de cristaux par formation de branches. Enfin, je prouverai une vieille conjecture de Rothemund et Winfree : on ne peut pas assembler des carrés de taille n x n avec moins de 2n-1 tuiles. Cet exposé est basé sur le papier suivant : http://hal.archives-ouvertes.fr/hal-00912937.



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

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