On the Power of Labels in Transition Systems
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F01%3A00004560" target="_blank" >RIV/00216224:14330/01:00004560 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On the Power of Labels in Transition Systems
Popis výsledku v původním jazyce
In this paper we discuss the role of labels in transition systems with regard to bisimilarity and model checking problems. We suggest a general reduction from labelled transition systems to unlabelled ones, preserving bisimilarity and satisfiability of $mu$-calculus formulas. We apply the reduction to the class of transition systems generated by Petri nets and pushdown automata, and obtain several decidability/complexity corollaries for unlabelled systems. Probably the most interesting result is undecidability of strong bisimilarity for unlabelled Petri nets.
Název v anglickém jazyce
On the Power of Labels in Transition Systems
Popis výsledku anglicky
In this paper we discuss the role of labels in transition systems with regard to bisimilarity and model checking problems. We suggest a general reduction from labelled transition systems to unlabelled ones, preserving bisimilarity and satisfiability of $mu$-calculus formulas. We apply the reduction to the class of transition systems generated by Petri nets and pushdown automata, and obtain several decidability/complexity corollaries for unlabelled systems. Probably the most interesting result is undecidability of strong bisimilarity for unlabelled Petri nets.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
BD - Teorie informace
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GA201%2F00%2F0400" target="_blank" >GA201/00/0400: Nekonečně stavové souběžné systémy - modely a verifikace</a><br>
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Proceedings of 12th International Conference on Concurrency Theory (CONCUR'01)
ISBN
—
ISSN
—
e-ISSN
—
Počet stran výsledku
291
Strana od-do
277
Název nakladatele
Springer-Verlag
Místo vydání
Holland
Místo konání akce
Holland
Datum konání akce
1. 1. 2001
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—