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.