Afficher la notice abrégée

dc.contributor.authorHaddad, Serge
dc.contributor.authorRecalde, Laura
dc.contributor.authorSilva, Manuel
dc.date.accessioned2010-12-09T11:02:54Z
dc.date.available2010-12-09T11:02:54Z
dc.date.issued2006
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5257
dc.language.isoenen
dc.subjectExpressivenessen
dc.subjectSimulationen
dc.subjectCoverabilityen
dc.subjectReachabilityen
dc.subjectSteady-state Analysisen
dc.subjectTime Differentiable Petri Nets (TDPN)en
dc.subjectdynamical systemsen
dc.subject.ddc004en
dc.titleOn the Computational Power of Timed Differentiable Petri Netsen
dc.typeCommunication / Conférence
dc.description.abstractenWell-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.en
dc.identifier.citationpages230-244en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber4202
dc.relation.ispartoftitleFormal Modeling and Analysis of Timed Systems 4th International Conference, FORMATS 2006, Paris, France, September 25-27, 2006, Proceedingsen
dc.relation.ispartofeditorAsarin, Eugene
dc.relation.ispartofeditorBouyer, Patricia
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2006
dc.relation.ispartofpages369en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/11867340en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelInformatique généraleen
dc.relation.ispartofisbn978-3-540-45026-9en
dc.relation.conftitle4th International Conference on Formal Modelling and Analysis of Timed Systems (FORMATS'06)en
dc.relation.confdate2006-09
dc.relation.confcityParisen
dc.relation.confcountryFranceen
dc.identifier.doihttp://dx.doi.org/10.1007/11867340_17


Fichiers attachés à cette notice

Thumbnail

Ce document fait partie de la (des) collection(s) suivante(s)

Afficher la notice abrégée