Effective decomposability of sequential behaviours

A process is prime if it cannot be equivalently expressed as a parallel com position of nonempty processes. We characterize all non-prime normed BPA pr ocesses together with their prime decompositions by means of normal forms w hich are designed in this paper. Using this result we demonstrate decidabil ity of the problem whether a given normed BPA process is prime; moreover, w e show that non-prime normed BPA processes can be decomposed into primes ef fectively. Finally, we prove that bisimilarity is decidable in a natural su bclass of normed PA processes. (C) 2000 Elsevier Science B.V. All rights re served.