Non-primitive recursive complexity andundecidability for Petri net equivalences

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F01%3A00001047" target="_blank" >RIV/61989100:27240/01:00001047 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Non-primitive recursive complexity andundecidability for Petri net equivalences
Popis výsledku v původním jazyce
Firstly, it is shown that the previous undecidability result for bisimilarity can be immediately extended for the whole range of equivalences (and preorders) on labelled Petri nets. Secondly, it is shown that restricting our attention to nets with finitereachable space, the respective (decidable) problems are nonprimitive recursive; this approach also applies to Mayr and Meyer's result for the reachability set equality, yielding a more direct proof.
Název v anglickém jazyce
Non-primitive recursive complexity andundecidability for Petri net equivalences
Popis výsledku anglicky
Firstly, it is shown that the previous undecidability result for bisimilarity can be immediately extended for the whole range of equivalences (and preorders) on labelled Petri nets. Secondly, it is shown that restricting our attention to nets with finitereachable space, the respective (decidable) problems are nonprimitive recursive; this approach also applies to Mayr and Meyer's result for the reachability set equality, yielding a more direct proof.

Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BD - Teorie informace
OECD FORD obor
—

Projekt
<a href="/cs/project/GA201%2F97%2F0456" target="_blank" >GA201/97/0456: Meze algoritmické verifikovatelnosti nekonečně stavových systémů</a><br>
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění
2001
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)