Weak Bisimilarity between Finite-State Systems and BPA or normed BPP is Decidable in Polynomial Time

Investor logo

Warning

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

KUČERA Antonín MAYR Richard

Year of publication 2002
Type Article in Periodical
Magazine / Source Theoretical Computer Science
MU Faculty or unit

Faculty of Informatics

Citation
Field Computer hardware and software
Keywords concurrency; infinite-state systems; bisimilarity
Description We prove that weak bisimilarity is decidable in polynomial time between finite-state systems and several classes of infinite-state systems: context-free processes (BPA) and normed Basic Parallel Processes (normed BPP). To the best of our knowledge, these are the first polynomial algorithms for weak bisimilarity problems involving infinite-state systems.
Related projects:

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