On the Power of Labels in Transition Systems

Investor logo

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

SRBA Jiří

Year of publication 2001
Type Article in Proceedings
Conference Proceedings of 12th International Conference on Concurrency Theory (CONCUR'01)
MU Faculty or unit

Faculty of Informatics

Citation
Field Information theory
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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info