Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Continuous Reachability for Unordered Data Petri Nets is in PTime

Uproszczony widok
cris.lastimport.scopus2024-02-12T19:38:48Z
dc.abstract.enUnordered data Petri nets (UDPN) are an extension of classical Petri nets with tokens that carry data from an infinite domain and where transitions may check equality and disequality of tokens. UDPN are well-structured, so the coverability and termination problems are decidable, but with higher complexity than for Petri nets. On the other hand, the problem of reachability for UDPN is surprisingly complex, and its decidability status remains open. In this paper, we consider the continuous reachability problem for UDPN, which can be seen as an over-approximation of the reachability problem. Our main result is a characterization of continuous reachability for UDPN and polynomial time algorithm for solving it. This is a consequence of a combinatorial argument, which shows that if continuous reachability holds then there exists a run using only polynomially many data values.
dc.affiliationUniwersytet Warszawski
dc.conference.countryCzechy
dc.conference.datefinish2019-04-11
dc.conference.datestart2019-04-06
dc.conference.placePrague
dc.conference.seriesFoundations of Software Science and Computational Structures
dc.conference.seriesFoundations of Software Science and Computational Structures
dc.conference.seriesshortcutFOSSACS
dc.conference.shortcutFoSSaCS 2019
dc.conference.weblinkhttps://etaps.org/2019/fossacs
dc.contributor.authorShah, Preey
dc.contributor.authorAkshay, S.
dc.contributor.authorGupta, Utkarsh
dc.contributor.authorHofman, Piotr
dc.date.accessioned2024-01-24T20:47:01Z
dc.date.available2024-01-24T20:47:01Z
dc.date.issued2019
dc.description.financeNie dotyczy
dc.identifier.doi10.1007/978-3-030-17127-8_15
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/103689
dc.identifier.weblinkhttps://link.springer.com/chapter/10.1007%2F978-3-030-17127-8_15#aboutcontent
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages260-276
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enPetri nets
dc.subject.enContinuous reachability
dc.subject.enUnordered data
dc.subject.enPolynomial time
dc.titleContinuous Reachability for Unordered Data Petri Nets is in PTime
dc.typeJournalArticle
dspace.entity.typePublication