Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BYCC-BY - Uznanie autorstwa
 

Timed Basic Parallel Processes

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:25:34Z
dc.abstract.enTimed basic parallel processes (TBPP) extend communication-free Petri nets (aka. BPP or commutative context-free grammars) by a global notion of time. TBPP can be seen as an extension of timed automata (TA) with context-free branching rules, and as such may be used to model networks of independent timed automata with process creation. We show that the coverability and reachability problems (with unary encoded target multiplicities) are PSPACE-complete and EXPTIME-complete, respectively. For the special case of 1-clock TBPP, both are NP-complete and hence not more complex than for untimed BPP. This contrasts with known super-Ackermannian-completeness and undecidability results for general timed Petri nets. As a result of independent interest, and basis for our NP upper bounds, we show that the reachability relation of 1-clock TA can be expressed by a formula of polynomial size in the existential fragment of linear arithmetic, which improves on recent results from the literature.
dc.affiliationUniwersytet Warszawski
dc.conference.countryHolandia
dc.conference.datefinish2019-08-31
dc.conference.datestart2019-08-26
dc.conference.placeAmsterdam
dc.conference.seriesInternational Conference on Concurrency Theory
dc.conference.seriesInternational Conference on Concurrency Theory
dc.conference.seriesshortcutCONCUR
dc.conference.shortcutCONCUR 2019
dc.conference.weblinkhttps://event.cwi.nl/concur2019/
dc.contributor.authorClemente, Lorenzo
dc.contributor.authorTotzke, Patrick
dc.contributor.authorHofman, Piotr
dc.date.accessioned2024-01-26T10:53:31Z
dc.date.available2024-01-26T10:53:31Z
dc.date.copyright2019-08-20
dc.date.issued2019
dc.description.accesstimeAT_PUBLICATION
dc.description.financeNie dotyczy
dc.description.versionFINAL_PUBLISHED
dc.identifier.doi10.4230/LIPICS.CONCUR.2019.15
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/123421
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2019/10917/pdf/LIPIcs-CONCUR-2019-15.pdf
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages1-16
dc.rightsCC-BY
dc.sciencecloudnosend
dc.titleTimed Basic Parallel Processes
dc.typeJournalArticle
dspace.entity.typePublication