Publication details
Comparing Expressibility of Normed BPA and Normed BPP Processes.
| Basic information | |
|---|---|
| Original title: | Comparing Expressibility of Normed BPA and Normed BPP Processes. |
| Authors: | Ivana Černá, Mojmír Křetínský, Antonín Kučera |
| Further information | |
|---|---|
| Citation: | ČERNÁ, Ivana  - KŘETÍNSKÝ, Mojmír - KUČERA, Antonín. Comparing Expressibility of Normed BPA and Normed BPP Processes. Acta informatica, Berlin, Springer-Verlag, Germany. ISSN 0001-5903, 1999, vol. 36, no. 3, pp. 233-256. |
| Original language: | English |
| Field: | Computer hardware and software |
| Type: | Article in Periodical |
| Keywords: | concurrency; bisimilarity; infinite-state systems |
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:
- Algorithmic Verification Boundaries for Infinite-State Systems
- (Un)decidable Problems in Process Algebras
- Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing
