Title: On the computational power of time differentiable Petri nets (joint work with L. Recalde and M. Silva)
Lecturer: Serge Haddad (University of Paris-Dauphine, LAMSADE)
February 24, 9:30, Seminario del DIIS, Edificio Ada Byron
Abstract: Two kinds of well studied dynamical systems are state and time discrete (very important in Computer Science) and state and time continuous ones (heavily considered in classical Automatic Control). Whereas in the discrete setting, the analysis of computational power of models has led to well-known hierarchies, the situation is more confused in the continuous case. A possible way to discriminate between these models is to state whether they can simulate Turing machine (or others equivalent models like Counter Machine). For instance, it is known that continuous systems described by ordinary differential equations (ODE) have this power. However, since the involved ODE is defined by overlapping local ODEs inside an infinite number of regions, this result has no significant application for differentiable models whose ODE is defined by an explicit representation. In this work, we have considerably strengthened this result by showing that time differentiable Petri nets can simulate Turing machine. The ODE ruling this model is particularly simple. First its expression is a linear expression enlarged with the "min" operator. Second, it can be decomposed into a finite number of linear ODE inside polyhedra. We will also present different simulations in order to fulfill additional requirements like robustness (allowing some perturbation on the simulation mapping) and boundedness of the simulating net system. Finally, by modifying the simulation, we will prove that coverability, reachability and also the existence of a steady-state are undecidable.