Effective decomposability of sequential behaviours
A process is prime if it cannot be equivalently expressed as a parallel composition of nonempty processes. We characterize all non-prime normed BPA processes together with their prime decompositions by means of normal forms which are designed in this paper. Using this result we demonstrate decidability of the problem whether a given normed BPA process is prime; moreover, we show that non-prime normed BPA processes can be decomposed into primes effectively. Finally, we prove that bisimilarity is decidable in a natural subclass of normed PA processes. (C) 2000 Elsevier Science B.V. All rights reserved.
parallelization bisimilarity concurrency infinite-state systems