On the Power of Labels in Transition Systems
| Autoři | |
|---|---|
| Rok publikování | 2001 |
| Druh | Článek ve sborníku |
| Konference | Proceedings of 12th International Conference on Concurrency Theory (CONCUR'01) |
| Fakulta / Pracoviště MU | |
| Citace | |
| Obor | Teorie informace |
| Popis | 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. |
| Související projekty: |