Comparing Expressibility of Normed BPA and Normed BPP Processes.
| Authors | |
|---|---|
| Year of publication | 1999 |
| Type | Article in Periodical |
| Magazine / Source | Acta informatica |
| MU Faculty or unit | |
| 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: |