uu.seUppsala universitets publikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
On the Upward/Downward Closures of Petri Nets∗
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
TU Braunschweig, Germany.
TU Braunschweig, Germany.
TU Braunschweig, Germany.
2017 (engelsk)Inngår i: 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, s. 49:1-49:14Konferansepaper, Publicerat paper (Fagfellevurdert)
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.

sted, utgiver, år, opplag, sider
Dagstuhl, Germany, 2017. Vol. 83, s. 49:1-49:14
Serie
Leibniz International Proceedings in Informatics (LIPIcs), ISSN 1868-8969 ; 83
HSV kategori
Identifikatorer
URN: urn:nbn:se:uu:diva-337130DOI: 10.4230/LIPIcs.MFCS.2017.49ISBN: 978-3-95977-046-0 (tryckt)OAI: oai:DiVA.org:uu-337130DiVA, id: diva2:1168335
Konferanse
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Prosjekter
UPMARCTilgjengelig fra: 2017-12-20 Laget: 2017-12-20 Sist oppdatert: 2018-01-13

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fullteksthttp://drops.dagstuhl.de/opus/volltexte/2017/8127

Søk i DiVA

Av forfatter/redaktør
Atig, Mohamed Faouzi
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 134 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf