2026-07-24T03:00:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8127 2024-03-06T10:40:55Z ddc:004 open_access

On the Upward/Downward Closures of Petri Nets Atig, Mohamed Faouzi Meyer, Roland Muskalla, Sebastian Saivasan, Prakash Petri nets BPP nets downward closure upward closure We study the size and the complexity of computing finite state automata (FSA) representing and approximating the downward and the upward closure of Petri net languages with coverability as the acceptance condition. We show how to construct an FSA recognizing the upward closure of a Petri net language in doubly-exponential time, and therefore the size is at most doubly exponential. For downward closures, we prove that the size of the minimal automata can be non-primitive recursive. In the case of BPP nets, a well-known subclass of Petri nets, we show that an FSA accepting the downward/upward closure can be constructed in exponential time. Furthermore, we consider the problem of checking whether a simple regular language is included in the downward/upward closure of a Petri net/BPP net language. We show that this problem is EXPSPACE-complete (resp. NP-complete) in the case of Petri nets (resp. BPP nets). Finally, we show that it is decidable whether a Petri net language is upward/downward closed. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mohamed Faouzi Atig and Roland Meyer and Sebastian Muskalla and Prakash Saivasan 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.49 urn:nbn:de:0030-drops-81278 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.49 eng https://creativecommons.org/licenses/by/3.0/legalcode