The report FIMU-RS-96-05
How to Parallelize Sequential Processes
by Antonín Kučera, Accepted to the 8th International Conference on Concurrency Theory (CONCUR`97). December 1996, 24 pages.
A process is prime if it cannot be decomposed into a parallel product of nontrivial processes. We characterize all non-prime normed BPA processes together with their decompositions in terms of normal forms which are designed in this paper. Then we show that it is decidable whether a given normed BPA process is prime and if not, its decomposition can be effectively constructed. This brings other positive decidability results. Finally, we prove that bisimilarity is decidable in a large subclass of normed PA processes.
Please install a newer browser for this site to function properly.