*For the most recent entries see the
Petri Nets Newsletter.*

## On the Computational Power of Timed Differentiable Petri Nets.

Haddad, Serge;
Recalde, Laura;
Silva, Manuel
In:
*Lecture Notes in Computer Science : Formal Modeling and Analysis of Timed Systems, Volume 4202, 2006*, pages 230-244.
2006.
URL: `http://dx.doi.org/10.1007/11867340`_{1}7.

Abstract:
Well-known hierarchies discriminate between the computational power of
discrete time and space dynamical systems. A contrario the situation is
more confused for dynamical systems when time and space are continuous. A
possible way to discriminate between these models is to state whether they
can simulate Turing machine. For instance, it is known that continuous
systems described by an ordinary differential equation (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 considerably strengthen this result by
showing that Time Differentiable Petri Nets (TDPN) can simulate Turing
machines. Indeed the ODE ruling this model is expressed by an explicit
linear expression enlarged with the minimum operator. More precisely, we
present two simulations of a two counter machine by a TDPN in order to
fulfill opposite requirements: robustness and boundedness. These
simulations are performed by nets whose dimension of associated ODEs is
constant. At last, we prove that marking coverability, submarking
reachability and the existence of a steady-state are undecidable for TDPNs.

*Do you need a refined search? Try our search engine
which allows complex field-based queries.*
*Back to the Petri Nets Bibliography*