Comparing expressibility of normed BPA and normed BPP processes
We present an exact characterization of those transition systems which can be equivalently (up to bisimilarity) defined by the syntax of normed \(\text{BPA}_\tau\) and normed \(\text{BPP}_\tau\) processes. We give such a characterization for the subclasses of normed BPA and normed BPP processes as well. Next, we demonstrate the decidability of the problem whether for a given normed \(\text{BPA}_\tau\) process \(\Delta\) there is some unspecified normed \(\text{BPP}_\tau\) 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 (an example of) the process \(\Delta'\) is effectively constructible. Analogous algorithms are provided for normed \(\text{BPP}_\tau\) processes. Simplified versions of the mentioned algorithms which work for normed BPA and normed BPP are given, too. As a simple consequence we obtain the decidability of bisimilarity in the union of normed \(\text{BPA}_\tau\) and normed \(\text{BPP}_\tau\) processes.
- Complexity of deciding bisimilarity between normed BPA and normed BPP
- Regularity of normed PA processes
- Selected Ideas Used for Decidability and Undecidability of Bisimilarity
- Normed BPA vs. Normed BPP Revisited
- Deciding bisimilarity between BPA and BPP processes.
- Deciding bisimulation-like equivalences with finite-state processes
- Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time
This page was built for publication: Comparing expressibility of normed BPA and normed BPP processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1306565)
