61 avenue due Président Wilson
Funding is available for a 3-year PhD thesis in the INRIA team MEXICO at the LSV lab, ENS Paris-Saclay, on
Eco-System Causal Analysis Using PEtri Net Unfoldings,
or ESCAPE for short.
Please contact the addresses below asap, and no later than April 30, 2020, since the selection will be made in early may, 2020; expected begin of the thesis is in the fall of 2020.
CONTEXT: To understand the long-term dynamics of ecosystems, several concepts have emerged in ecology, in particular ``basins of attraction'' to express resilience, and ``tipping points'' that express sharp change in an ecosystem's behaviour.
However, these temporal features remain difficult to identify and quantify because current models in ecology usually focus only on a part of the whole ecosystem behaviour; the PhD thesis will pursue a holistic approach instead.
The goal is to develop and exploit discrete concurrent network models, based on
Boolean and Thomas networks, and Petri nets.
Recently, Gaucherel and Pommereau [GP19] have added to this family an original class of discrete models designed to comprehensively characterize ecosystem dynamics over the long term. Their modelling language that can be expressed both textually (a set of guarded actions on Boolean variables) and graphically (an hypergraph linking the variables through the rules that read/write them).
It turns out that the latter representation, so called an ecosystem hypergraph, can be seen as a 1-safe Petri net using various extensions (read arcs, inhibitor arcs, reset arcs, and transitions priorities).
One of the strength of Petri nets is the possibility of analyzing dynamic properties on compact, finite partial order representations of the possible system evolutions, known as unfoldings or, more precisely, the complete prefixes thereof. An immediate advantage lies in the reduced size of the data structure compared to global-state transition system; more importantly perhaps is that unfoldings exhibit the fine-grained causal relationships that govern complex processes. Paulevé et al. [CHJ+14] have carried out the exhaustive computation of a biological network's attractors (long-run stable behaviours) via unfoldings, yielding a causal picture of the internal dynamics of each cyclic attractor. Currently, research at LSV is studying reprogramming [MSH+19] of dynamical systems as a control problem whose objective is to steer a system into desired attractors and away from undesirable ones, in the context of cell regulation with high potential for cross-fertilisation with the proposed research on ecological systems.
Research topics to be addressed also include:
- Exploration of the Most Permissive Semantics, which we recently introduced [CHK+19][CHP18a][CHP18b] to generalize existing update modes in biological network models, inspired by a corresponding non-atomic semantics we had introduced in contextual Petri nets ; it subsumes all the usual updating modes, while enabling new behaviours. Moreover,
reachability can be assessed in a polynomial number of iterations (instead of being PSPACE-complete). Current investigations into the MP semantics suggest that it presents a passageway allowing to connect any continuous system satisfying suitable nondegeneracy conditions to discrete models, and vice versa.
-Causal Impact Analysis, Blaming, and Control:
Analyzing the impact of particular components, events, or species is known to be supported by causal partial order models. LSV and its partners side has successfully developped and exploited this methodology in the context of fault diagnosis [GHKS15][HRS13][BFHJ03], where the occurrence of a non-observable fault is deduced from a stream of partial observations of system events and a causal model for interaction and fault propagation. Another important methodology for causal ascription, or blaming, has been proposed by Goessler et al., with a closely related formal framework of generalized event structures. A challenging task is to unify these approaches and developping sound and powerful algorithms for ascribing the 'responsability' for a particular phenomenon to events, components, species, or action patterns.
In a further extension, combining the above with the analysis of the systems attractor basins, the tipping points and the determinants that lead the system into particular attractors, will eventually give access to synthesizing control strategies, for objectives such as maintaining an ecosystem healthy under environmental stress.
The candidate is expected to have a strong background in formal models in computer science. The PhD research will be performed within the Mexico team (INRIA) in the LSV lab at Ecole Normale Supérieure Paris-Saclay, with regular meetings and exchange visits to and from IBISC lab / Univ. Evry, and in cooperation with Cédric Gaucherel, researcher in ecology at AMAP/INRA in Montpellier.
Please send all inquiries about the subject, working conditions, selection modalities etc etc to
- Franck Pommereau
- Stefan Haar
[CHJ+14] Thomas Chatain, Stefan Haar, Loïg Jezequel, Loïc Paulevé, and Stefan Schwoon. Characterization of reachable attractors using Petri net unfoldings. Proc. CMSB’14, volume 8859 of Lecture Notes in Bioinformatics, pages 129–142, Springer.
[MSH+19] Hugues Mandon, Cui Su, Stefan Haar, Jun Pang, and Loïc Paulevé. Sequential reprogramming of boolean networks made practical. CMSB’19, volume 11773 of Lecture
Notes in Bioinformatics, pages 3–19,Springer-Verlag.
[CHK+19] Thomas Chatain, Stefan Haar, Juraj Kolcák, Loïc Paulevé, and Aalok Thakkar. Concurrency in Boolean networks. Natural Computing, 2019.
[CHP18a] Thomas Chatain, Stefan Haar, and Loïc Paulevé. Boolean Networks: Beyond Generalized Asynchronicity. AUTOMATA’18, LNCS 10875 , pages 29–42, Springer.
[CHP18b] Thomas Chatain, Stefan Haar, and Loïc Paulevé. Most permissive semantics of boolean networks. Research Report 1808.10240, Computing Research Repository, Aug. 2018.
[GHKS15] Vasileios Germanos, Stefan Haar, Victor Khomenko, and Stefan Schwoon. Diagnosability under weak fairness. ACM Trans. Embedded Comput. Syst., 14(4):69:1–69:19, 2015.
[HRS13] Stefan Haar, César Rodríguez, and Stefan Schwoon. Reveal your faults: It’s only fair! ACSD 2013, pages 120–129.
[BFHJ03] A. Benveniste, E. Fabre, S. Haar, and C. Jard. Diagnosis of asynchronous discrete-event systems: a net unfolding approach. IEEE Trans. Automat. Contr., 48(5):714–727, 2003.
[GM15] Gregor Gößler and Daniel Le Métayer. A general framework for blaming in component-based systems. Sci. Comput. Program., 113:223–235, 2015.
[GP19] Cedric Gaucherel and Franck Pommereau. Using discrete systems to exhaustively characterize the dynamics of an integrated ecosystem. Methods in Ecology and Evolution, 10(9):1615–1627, 2019.