On the Power of Labels in Transition Systems
The result's identifiers
Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
On the Power of Labels in Transition Systems
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BD - Information theory
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA201%2F00%2F0400" target="_blank" >GA201/00/0400: Infinite state concurrent systems - models and verification</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2001
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of 12th International Conference on Concurrency Theory (CONCUR'01)
ISBN
—
ISSN
—
e-ISSN
—
Number of pages
291
Pages from-to
277
Publisher name
Springer-Verlag
Place of publication
Holland
Event location
Holland
Event date
Jan 1, 2001
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—