Technical Reports

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.

FIMU-RS-96-05. Available as Postscript, PDF.

Abstract:

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.