Comparing Expressibility of Normed BPA and Normed BPP Processes.

Investor logo
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

ČERNÁ Ivana KŘETÍNSKÝ Mojmír KUČERA Antonín

Year of publication 1999
Type Article in Periodical
Magazine / Source Acta informatica
MU Faculty or unit

Faculty of Informatics

Citation
Field Computer hardware and software
Keywords concurrency; bisimilarity; infinite-state systems
Description We present an exact characterization of those transition systems which can be equivalently (up to bisimilarity) defined by the syntax of normed \BPA\ and normed \BPP\ processes. We provide such a characterization for classes of normed BPA and normed BPP processes as well. Next we demonstrate decidability of the problem whether for a given normed \BPA\ process $\Delta$ there is some unspecified normed \BPP\ process $\Delta'$ such that $\Delta$ and $\Delta'$ are bisimilar. The algorithm is polynomial. Furthermore, we show that if the answer to the previous question is positive, then the process $\Delta'$ is effectively constructible. Analogous algorithms are provided for normed \BPP\ processes. Simplified versions of the mentioned algorithms which work for nBPA and nBPP are given too. As a simple consequence we obtain decidability of bisimilarity in the union of normed \BPA\ and normed \BPP\ processes.
Related projects:

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