uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the Upward/Downward Closures of Petri Nets∗
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
TU Braunschweig, Germany.
TU Braunschweig, Germany.
TU Braunschweig, Germany.
2017 (English)In: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) / [ed] Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin, Dagstuhl, Germany, 2017, Vol. 83, p. 49:1-49:14Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Dagstuhl, Germany, 2017. Vol. 83, p. 49:1-49:14
Series
Leibniz International Proceedings in Informatics (LIPIcs), ISSN 1868-8969 ; 83
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:uu:diva-337130DOI: 10.4230/LIPIcs.MFCS.2017.49ISBN: 978-3-95977-046-0 (print)OAI: oai:DiVA.org:uu-337130DiVA, id: diva2:1168335
Conference
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Projects
UPMARCAvailable from: 2017-12-20 Created: 2017-12-20 Last updated: 2018-01-13

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full texthttp://drops.dagstuhl.de/opus/volltexte/2017/8127

Search in DiVA

By author/editor
Atig, Mohamed Faouzi
By organisation
Computer Systems
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 52 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf