CANA


Natural computation research group

Description

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.

Keywords

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

Institutional links



Members

Permanent team members

Associate team members

Non-permanent team members

2016-2017 2015-2016 2014-2015 2013-2014

Projects



Publications

[32] J.L. Vilchis Medina, P. Siegel, and A. Doncescu. Autonomous aerial vehicle - based on non-monotonic logic. In Proceedings of the 3rd International Conference on Vehicle Technology and Intelligent Transport Systems, volume 1, pages 236--241. INSTICC, ScitePress, 2017. [ bib | DOI ]
[31] I. Márquez-Martín, G. Di Molfetta, and A. Pérez. Fermion confinement via quantum walks in (2+1)-dimensional and (3+1)-dimensional space-time. Phys. Rev. A, 95:042112, 2017. [ bib | DOI | http ]
[30] Mathilde Noual and Sylvain Sené. Synchronism versus asynchronism in monotonic Boolean automata networks. Natural Computing, 2017. In press. [ bib | DOI ]
[29] Florian Bridoux, 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, volume 10185 of LNCS, pages 112--128. Springer, 2017. [ bib | DOI ]
[28] Pablo Arrighi, Vincent Nesme, and Reinhard F. Werner. Bounds on the speedup in quantum signaling. Phys. Rev. A, 95:012331--012341, 2017. [ bib ]
[27] Kévin Perrot and Eric Rémila. Strong emergence of wave patterns on Kadanoff sandpiles. Electronic Journal of Combinatorics, 24(2), 2017. freely available at http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p4. [ bib ]
[26] Tarek Melliti, Damien Regnault, Adrien Richard, and Sylvain Sené. Asynchronous simulation of Boolean networks by monotone Boolean networks. In Proceedings of ACRI'16, volume 9863 of LNCS, pages 182--191. Springer, 2016. [ bib ]
[25] Pablo Arrighi, Stefano Facchini, and Marcelo Forets. Quantum walking in curved spacetime. Quantum Information Processing, 15(8):3467--3486, 2016. [ bib | DOI | http ]
[24] Pablo Arrighi and Simon Perdrix. Modèles de calcul quantiques. In Étienne Baudrier and Loïc Mazo, editors, Informatique Mathématique - une photographie en 2016. CNRS Editions, 2016. [ bib | .pdf ]
[23] Thanh Nguyen, Andrei Doncescu, and Pierre Siegel. Performance Comparison of ADTree and Naive Bayes Algorithms for Spam Filtering. International Journal of Mathematical, Computational, Physical, Electrical and Computer Engineering, 10(5):269--274, 2016. [ bib ]
[22] Pablo Arrighi and Gilles Dowek. Free fall and cellular automata. In César A. Muñoz and Jorge A. Pérez, editors, Proceedings of DCM'2015, volume 204 of EPTCS, pages 1--10. Open Publishing Association, 2016. [ bib ]
[21] Pablo Arrighi, Simon Martiel, and Simon Perdrix. Reversible causal graph dynamics. In Proceedings of RC'2016, volume 9720 of LNCS, pages 73--88. Springer, 2016. [ bib ]
[20] Giuseppe Di Molfetta and Armando Pérez. Quantum walks as simulators of neutrino oscillations in a vacuum and matter. New Journal of Physics, 18(10):103038, 2016. [ bib ]
[19] Luis A. Bru, Germán J. de Valcárcel, Giuseppe Di Molfetta, Armando Pérez, Eugenio Roldán, and Fernando Silva. Quantum walk on a cylinder. Phys. Rev. A, 94:032328, 2016. [ bib | DOI | http ]
[18] Kévin Perrot and Trung Van Pham. Chip-firing game and partial Tutte polynomial for Eulerian digraphs. Electronic Journal of Combinatorics, 23(1), 2016. [ bib ]
[17] Aurore Alcolei, Kévin Perrot, and Sylvain Sené. On the flora of asynchronous locally non-monotonic Boolean automata networks. In Proceedings of SASB'15, volume 326 of ENTCS, pages 3--25. Elsevier, 2016. [ bib ]
[16] Pablo Arrighi and Gilles Dowek. Discrete geodesics and cellular automata. In Proceedings TPNC'2015, volume 9477 of LNCS, pages 137--149. Springer, 2015. [ bib ]
[15] Pablo Arrighi, Alejandro Diaz-Caro, and Benoît Valiron. The vectorial lambda-calculus. Information and Computation, 2015. to appear. [ bib ]
[14] Pablo Arrighi, Simon Martiel, and Simon Perdrix. Block representation of reversible causal graph dynamics. In Proceedings of FCT'2015, volume 9210 of LNCS, pages 351--363. Springer, 2015. [ bib ]
[13] Pablo Arrighi and Simon Perdrix. La décohérence, une alliée pour la simulation. La Recherche, 501-502:66--68, 2015. [ bib ]
[12] Tarek Melliti, Mathilde Noual, Damien Regnault, Sylvain Sené, and Jérémy Sobieraj. Asynchronous dynamics of Boolean automata double-cycles. In Proceedings of UCNC'2015, volume 9252 of LNCS, pages 250--262. Springer, 2015. [ bib ]
[11] Nazim Fatès and Sylvain Sené, editors. Automates cellulaires et réseaux d'automates : le rôle central de l'irrégularité, volume 35 of Technique et Science Informatiques. Lavoisier, 2015. [ bib ]
[10] Tarek Melliti, 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:401--430, 2015. [ bib ]
[9] Kévin Perrot and Éric Rémila. Piles de sable décroissantes 1D : classification expérimentale d'émergences. Technique et Science Informatiques -- Automates cellulaires et réseaux d'automates : le rôle central de l'irrégularité, 2015. [ bib ]
[8] Andrei Doncescu and Pierre Siegel. Emerging Trends in Computational Biology, Bioinformatics, and Systems Biology , chapter DNA Double-Strand BreakÐBased Nonmonotonic Logic , pages 409--527. Elsevier, 2015. [ bib ]
[7] Kévin Perrot and Éric Rémila. Emergence on decreasing sandpile models. In Proceedings of MFCS'2015, volume 9234 of LNCS, pages 419--431. Springer, 2015. [ bib ]
[6] Christophe Crespelle, 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, volume 9214 of LNCS, pages 212--223. Springer, 2015. [ bib ]
[5] Kévin Perrot 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:373--396, 2015. [ bib ]
[4] Georgia Barlovatz-Meimon and Sylvain Sené. Culture de cellules animales (3e édition), chapter Méthodes informatiques en biologie. Lavoisier, 2014. [ bib ]
[3] Kévin Perrot and Éric Rémila. Emergence of regularities on decreasing sandpile models. In Proceedings of 15th Mons Theoretical Computer Science Days, 2014. [ bib ]
[2] Andrei Doncescu, Pierre Siegel, and Tan Le. Representation and efficient algorithms for the study of cell signaling pathways. In Proceedings of ICAI'2014, pages 504--510, 2014. [ bib ]
[1] Andrei Doncescu, Pierre Siegel, and Tan Le. Relevance of information in cell signaling pathways using default logic. In Proceedings of BIOCOMP'2014, pages 16--22. CSREA Press, 2014. [ bib ]


Seminars

Subscribe to mailing list.

[43] Benjamin Audoux.
12 septembre 2017 à 14h30.
Salle de réunion du modulaire (Luminy).
[42] Jose Luis Vilchis Medina.
20 juin 2017 à 14h30.
Salle de réunion du modulaire (Luminy).
,
Modélisation d'un système résilient en utilisant une logique non-monotone.
http://www.lif.univ-mrs.fr/evenements/id/441.
[41] Célia Biane (IBISC).
12 juin 2017 à 14h00.
Amphi Herbrand (Luminy).
,
Inférence des causes moléculaires des switches phénotypiques.
http://www.lif.univ-mrs.fr/evenements/id/423.
[40] Laurent Trilling (TIMC-IMAG).
16 mai 2017 à 14h30.
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".
http://www.lif.univ-mrs.fr/evenements/id/422.
[39] Kévin Perrot.
24 avril 2017 à 10h00.
Salle de réunion du modulaire (Luminy).
,
Sandpiles and graph polynomial.
http://www.lif.univ-mrs.fr/evenements/id/417.
[38] Timo Jolivet.
14 février 2017 à 14h15.
Salle de réunion du modulaire (Luminy).
,
Domptage de substitutions bi-dimensionnelles.
http://www.lif.univ-mrs.fr/evenements/id/388.
[37] Pierre Siegel.
31 janvier 2017 à 14h15.
Salle de réunion du modulaire (Luminy).
,
Des logiques non-monotones aux systèmes dynamiques discrets (SDD).
http://www.lif.univ-mrs.fr/evenements/id/382.
[36] Sabrina Ouazzani (LACL).
17 janvier 2017 à 14h30.
Salle de réunion du modulaire (Luminy).
,
Let's compute through infinite time!
http://www.lif.univ-mrs.fr/evenements/id/372.
[35] Christopher Cedzich (University of Hannover).
9 janvier 2017 à 16h30.
Salle de réunion du modulaire (Luminy).
,
The gentleness of perturbations and the topological classification of quantum walks.
http://www.lif.univ-mrs.fr/evenements/id/371.
[34] Adrien Richard (I3S).
13 décembre 2016 à 14h00.
Salle de réunion du 3e étage de la FRUMAM (Saint-Charles).
,
Points fixes dans les réseaux booléens monotones.
http://www.lif.univ-mrs.fr/evenements/id/370.
[33] Mohamed Hatifi (Institut Fresnel).
11 octobre 2016 à 14h00.
Salle de réunion du 6e (TPR1, entrée G, 6e étage)
,
Marches quantiques : simulation d'un fluide relativiste.
http://www.lif.univ-mrs.fr/evenements/id/345.
[32] Ioana Cristescu (Postdoc Harvard Medical School).
4 mai 2016 à 14h00.
Salle de réunion du 6e (TPR1, entrée G, 6e étage)
,
Influence et causalité dans les simulations de Kappa.
http://www.lif.univ-mrs.fr/evenements/id/317.
[31] Svetlana Puzynina (ENS Lyon).
13 avril 2016 à 13h30.
Salle de réunion du 6e (TPR1, entrée G, 6e étage)
,
Self-shuffling words.
http://www.lif.univ-mrs.fr/evenements/id/308.
[30] Maxime Folschette (I3S).
12 avril 2016 à 14h.
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.
http://www.lif.univ-mrs.fr/evenements/id/307.
[29] Simon Martiel (Postdoc LSV, Paris).
11 avril 2016 à 14h.
Salle de réunion du 6e (TPR1, entrée G, 6e étage)
,
Des automates cellulaires réversibles aux transformations causales et quantiques de graphes.
http://www.lif.univ-mrs.fr/evenements/id/309.
[28] Philippe Raynal (National University of Singapore).
5 avril 2016 à 14h45.
Amphi 12, Luminy
,
Optimality of entropic uncertainty relations.
http://www.lif.univ-mrs.fr/evenements/id/303.
[27] Benjamin Momège (Postdoc Inria, Lille).
5 avril 2016 à 10h.
Salle de réunion du 5e (TPR1, entrée G, 5e étage)
,
Autour de la connexité dans les graphes avec conflits.
http://www.lif.univ-mrs.fr/evenements/id/293.
[26] Nicolas Bacquey (ATER GREYC, Caen).
4 avril 2016 à 16h30.
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.
http://www.lif.univ-mrs.fr/evenements/id/304.
[25] Giuseppe Di Molfetta (Postdoc Instituto de Fisica Corpuscular (IFIC), Universitat de València).
21 mars 2016 à 16h30.
Salle de réunion du 6e (TPR1, entrée G, 6e étage)
,
Quantum Walks Gravity Simulation.
http://www.lif.univ-mrs.fr/evenements/id/296.
[24] Sergiu Ivanov (ATER LACL, Paris).
7 mars 2016 à 14h.
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.
http://www.lif.univ-mrs.fr/evenements/id/285.
[23] Benjamin Hellouin (Postdoc Andrés Bello University, Santiago).
23 fevrier 2016 à 10h.
Salle de réunion du 6e (TPR1, entrée G, 6e étage)
,
Calculs universels et comportements asymptotiques en dynamique symbolique.
http://www.lif.univ-mrs.fr/evenements/id/284.
[22] Martin Delacourt (ATER LORIA, Nancy).
22 fevrier 2016 à 14h.
Salle de réunion du 6e (TPR1, entrée G, 6e étage)
,
Directional Dynamics along Arbitrary Curves in Cellular Automata.
http://www.lif.univ-mrs.fr/evenements/id/277.
[21] Simona Olmi (INS, AMU).
16 fevrier 2016 à 10h.
Salle de réunion du 6e (TPR1, entrée G, 6e étage)
,
Coherent activity in excitatory pulse-coupled networks.
http://www.lif.univ-mrs.fr/evenements/id/281.
[20] Julien Degorre (PCQC, Paris).
15 fevrier 2016 à 14h.
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.
http://www.lif.univ-mrs.fr/evenements/id/283.
[19] Belaid Benhamou (LSIS).
8 fevrier 2016 à 14h.
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.
http://www.lif.univ-mrs.fr/evenements/id/276.
[18] Adrien Basso-Blandin (Postdoc ENS Lyon).
1 fevrier 2016 à 14h.
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.
http://www.lif.univ-mrs.fr/evenements/id/262.
[17] Pedro Montealegre (PhD LIFO, Orléans).
16 novembre 2015 à 14h30.
Salle de séminaire du 5e au LIF (TPR1, entree G, 5e etage)
,
Computational complexity of majority boolean networks under different updating schemes.
http://www.lif.univ-mrs.fr/evenements/id/239.
[16] Simon Martiel (PhD I3S, Nice).
16 juin 2015 à 14h.
Amphi 12 (bât. B, Luminy)
,
Intrinsic universality of causal graph dynamics.
http://www.lif.univ-mrs.fr/evenements/id/206.
[15] Cédric Bény (ITP, Hannover).
20 mai 2015 à 14h.
Salle de séminaire du LIF (TPR1, entree G, 6e etage)
,
Quantum processes: an introduction.
http://www.lif.univ-mrs.fr/evenements/id/186.
[14] Pablo Arrighi.
11 mai 2015 à 14h.
Salle de séminaire du LIF (TPR1, entree G, 6e etage)
,
Reversible Causal Graph Dynamics.
http://www.lif.univ-mrs.fr/evenements/id/176.
[13] Pierre-Etienne Meunier (Postdoc Aalto, Helsinki).
27 avril 2015 à 14h.
Salle de séminaire du LIF (TPR1, entree G, 6e etage)
,
l'Oritatami, un modèle de pliage co-transcriptionel.
http://www.lif.univ-mrs.fr/evenements/id/181.
[12] Timo Jolivet (Postdoc IMT, Toulouse).
13 avril 2015 à 14h.
Salle de séminaire du LIF (TPR1, entree G, 6e etage)
,
Fractals, indécidabilité et automates à plusieurs rubans.
http://www.lif.univ-mrs.fr/evenements/id/175.
[11] Vincent Risch (LSIS).
23 mars 2015 à 14h.
Salle de séminaire du LIF (TPR1, entree G, 6e etage)
,
Une (petite) promenade formelle sur les chemins du raisonnement et de l'argumentation.
http://www.lif.univ-mrs.fr/evenements/id/168.
[10] Gilles Didier (I2M).
09 mars 2015 à 14h.
Salle de séminaire du LIF (TPR1, entree G, 6e etage)
,
Quelques axes de recherche de l'équipe MEB (Mathématiques, Évolution, Biologie).
http://www.lif.univ-mrs.fr/evenements/id/152.
[9] Pierre Siegel.
19 janvier 2015 à 14h.
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.
http://www.lif.univ-mrs.fr/evenements/id/143.
[8] Sylvain Sené.
12 janvier 2015 à 14h.
Salle de séminaire du LIF (TPR1, entree G, 6e etage)
,
Réseaux d’automates et questions diverses .
http://www.lif.univ-mrs.fr/evenements/id/140.
[7] Lina Ye (Postdoc INRIA CONVECS, Grenoble).
17 avril 2014 à 10h30.
Salle de séminaire du LIF (TPR1, entree G, 6e etage)
,
Joint Diagnosability of Distributed Discrete Event Systems.
http://www.lif.univ-mrs.fr/evenements/id/77.
[6] Martin Delacourt (Postdoc CMM UChile, Santiago).
15 avril 2014 à 11h.
Salle de séminaire du LIF (TPR1, entree G, 6e etage)
,
Ensembles limites d'automates cellulaires associés à une mesure de probabilité.
http://www.lif.univ-mrs.fr/evenements/id/76.
[5] Jean Gaudart (MCU-PH SESSTIM, AMU).
11 avril 2014 à 9h30.
Salle de séminaire du LIF (TPR1, entree G, 6e etage)
,
Variabilité spatio-temporelle des épidémies: application au paludisme et au choléra.
http://www.lif.univ-mrs.fr/evenements/id/82.
[4] Michelangelo Bucci (Postdoc LIRMM, Montpellier).
10 avril 2014 à 15h.
Salle de séminaire du LIF (TPR1, entree G, 6e etage)
,
Fragments de mathématiques discrètes.
http://www.lif.univ-mrs.fr/evenements/id/81.
[3] Aitor Gonzalez (Postdoc TAGC, AMU).
13 mars 2014 à 10h.
Salle de séminaire du LIF (TPR1, entree G, 6e etage)
,
Modeling the expression waves during the mouse segmentation.
http://www.lif.univ-mrs.fr/evenements/id/58.
[2] Cinzia Di Giusto (Postdoc IBISC, Évry).
06 mars 2014 à 10h30.
Salle de séminaire du LIF (TPR1, entree G, 6e etage)
,
Reaction networks with delays applied to toxicity analysis.
http://www.lif.univ-mrs.fr/evenements/id/57.
[1] Pierre-Étienne Meunier (Postdoc LIAFA, Paris.
17 décembre 2013 à 15h.
Salle de séminaire du LIF (TPR1, entree G, 6e etage)
,
Auto-assemblage non-coopératif de chemins et de carrés.
http://www.lif.univ-mrs.fr/evenements/id/32.


Softwares developed by the group