CANA : Natural Computation
Courriel : firstname.lastname@example.org
Courriel : email@example.com
Courriel : firstname.lastname@example.org
Courriel : email@example.com
Courriel : firstname.lastname@example.org
Courriel : email@example.com
Courriel : firstname.lastname@example.org
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.
Year of production
- Viet-Ha Nguyen, Kévin Perrot, Mathieu Vallet. NP-completeness of the game Kingdomino. Theoretical Computer Science, Elsevier, 2020, 822, pp.23-35. ⟨10.1016/j.tcs.2020.04.007⟩. ⟨hal-03121418⟩
- Balthazar Casalé, Giuseppe Di Molfetta, Hachem Kadri, Liva Ralaivola. Quantum bandits. Quantum Machine Intelligence, 2020, 2 (1), ⟨10.1007/s42484-020-00024-8⟩. ⟨hal-03118185⟩
- Pablo Arrighi, Simon Martiel, Simon Perdrix. Reversible causal graph dynamics: invertibility, block representation, vertex-preservation. Natural Computing, Springer Verlag, 2019, ⟨10.1007/s11047-019-09768-0⟩. ⟨hal-02400095⟩
- Mathilde Noual, Sylvain Sené. Synchronism versus asynchronism in monotonic Boolean automata networks. Natural Computing, Springer Verlag, 2018, 17 (2), pp.393-402. ⟨hal-01479438⟩
- Pablo Arrighi, S. Martiel, V. Nesme. Cellular automata over generalized Cayley graphs. Mathematical Structures in Computer Science, Cambridge University Press (CUP), 2018, 18, pp.340-383. ⟨hal-01785458⟩
- Jacques Demongeot, Sylvain Sené. Phase transitions in stochastic non-linear threshold Boolean automata networks on Z²: the boundary impact. Advances in Applied Mathematics, Elsevier, 2018, 98, pp.77--99. ⟨hal-01785459⟩
- Pablo Arrighi, Giuseppe Di Molfetta, Stefano Facchini. Quantum walking in curved spacetime: discrete metric. Quantum, 2018, 2, pp.84. ⟨10.22331/q-2018-08-22-84⟩. ⟨hal-02093395⟩
- Giuseppe Di Molfetta, Diogo O. Soares-Pinto, S'ılvio M. Duarte Queirós. Elephant quantum walk. Physical Review A, American Physical Society, 2018, 97, pp.062112. ⟨10.1103/PhysRevA.97.062112⟩. ⟨hal-02093396⟩
- Eurico L. P. Ruivo, Marco Montalva-Medel, Pedro P. B. Oliveira, Kévin Perrot. Characterisation of the elementary cellular automata in terms of their maximum sensitivity to all possible asynchronous updates. Chaos, Solitons and Fractals, Elsevier, 2018, 113, pp.209--220. ⟨10.1016/j.chaos.2018.06.004⟩. ⟨hal-02093397⟩
- Enrico Formenti, Kévin Perrot, Eric Rémila. Computational complexity of the avalanche problem for one dimensional decreasing sandpiles. Journal of Cellular Automata, Old City Publishing, 2018, 13 (3), pp. 215-228. ⟨halshs-01417248⟩
- Xiaojian Li, L. Lachmanski, S. Safi, S. Sene, C. Serre, et al.. New insights into the degradation mechanism of metal-organic frameworks drug carriers. Scientific Reports, Nature Publishing Group, 2017, 7 (1), ⟨10.1038/s41598-017-13323-1⟩. ⟨hal-01868346⟩
- Loïc Paulevé, Sylvain Sené. Non-deterministic updates of Boolean networks. AUTOMATA 2021 (27th International Workshop on Cellular Automata and Discrete Complex Systems), 2021, Marseille, France. ⟨hal-03210805⟩
- José Luis Vilchis Medina, Pierre Siegel, Vincent Risch, Andrei Doncescu. Intelligent and Adaptive System based on a Non-monotonic Logic for an Autonomous Motor-glider. 15th International Conference on Control, Automation, Robotics and Vision (ICARCV 2018), Nov 2018, Singapore, Singapore. pp.442--447, ⟨10.1109/ICARCV.2018.8581107⟩. ⟨hal-02093392⟩
- Pierre Siegel, Andrei Doncescu, Vincent Risch, Sylvain Sené. Towards a Boolean dynamical system representation in a nonmonotonic modal logic. International Workshop on Non-Monotonic Reasoning (NMR'18), Oct 2018, Tempe, United States. pp.53--62. ⟨hal-02093398⟩
- Viet-Ha Nguyen, Kévin Perrot. Any Shape Can Ultimately Cross Information on Two-Dimensional Abelian Sandpile Models. 24th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2018, Ghent, Belgium. pp.127-142, ⟨10.1007/978-3-319-92675-9_10⟩. ⟨hal-01824872⟩
- Pablo Arrighi, Giuseppe Molfetta, Nathanaël Eon. A Gauge-Invariant Reversible Cellular Automaton. 24th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2018, Ghent, Belgium. pp.1-12, ⟨10.1007/978-3-319-92675-9_1⟩. ⟨hal-01824869⟩
- G. Ruz, E. Goles, S. Sené. Reconstruction of Boolean regulatory models of flower development through an evolution strategy. Proceedings of CEC'18, 2018, Unknown, Unknown Region. ⟨hal-01785460⟩
- P. Arrighi, C. Chouteau, S. Facchini, S. Martiel. Causal dynamics of discrete manifolds. Proceedings of NCMA'2018, 2018, Kosice, Slovakia. ⟨hal-02093393⟩
- Tarek Khaled, Belaid Benhamou, Pierre Siegel. Vers une nouvelle méthode de calcul de modèles stables et extensions en programmation logique. Actes des Quatorzièmes Journées Francophones de Programmation par Contraintes (JFPC'2018), 2018, Amiens, France. pp.63-72. ⟨hal-02093400⟩
- Kévin Perrot, Cédric Berenger, Peter Niebert. Balanced Connected Partitioning of Unweighted Grid Graphs. Proceedings of MFCS'2018, 2018, Liverpool, United Kingdom. pp.39:1--39:18, ⟨10.4230/LIPIcs.MFCS.2018.39⟩. ⟨hal-02093978⟩
- Kévin Perrot, Pacôme Perrotin, Sylvain Sené. A framework for (de)composing with Boolean automata networks. International Conference on Machines, Computations, and Universality (MCU'2018), 2018, Fontainebleau, France. ⟨hal-01654221v2⟩
- Alberto Leporati, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron. A Turing machine simulation by P systems without charges. Proceedings of ACMC'2018, 2018, Auckland, New Zealand. pp.213--221. ⟨hal-02093391⟩
- Pablo Arrighi, Simon Martiel, Simon Perdrix. Reversible Causal Graph Dynamics. Reversible Computation, Jul 2016, Bologna, Italy. pp.73-88, ⟨10.1007/978-3-319-40578-0_5⟩. ⟨hal-01361427⟩
Preprints, Working Papers
- Kévin Perrot, Marco Montalva-Medel, Pedro de Oliveira, Eurico Ruivo. Maximum sensitivity to update schedules of elementary cellular automata over periodic configurations. 2019. ⟨hal-02179732⟩