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 BPA(ta u) and normed BPPtau processes. We give such a characterization for the sub classes of normed BPA and normed BPP processes as well. Next we demonstrate the decidability of the problem whether for a given nor med BPA(tau) process Delta there is some unspecified normed BPPtau process Delta' such that Delta and Delta' are bisimilar. The algorithm is polynomia l. Furthermore, we show that if the answer to the previous question is posi tive, then tan example of) the process Delta' is effectively constructible. Analogous algorithms are provided for normed BPPtau processes. Simplified versions of the mentioned algorithms which work for normed BPA and normed B PP are given too. As a simple consequence we obtain the decidability of bis imilarity in the union of normed BPA(tau) and normed BPPtau processes.