Effective decomposability of sequential behaviours

Authors
Citation
A. Kucera, Effective decomposability of sequential behaviours, THEOR COMP, 242(1-2), 2000, pp. 71-89
Citations number
15
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
242
Issue
1-2
Year of publication
2000
Pages
71 - 89
Database
ISI
SICI code
0304-3975(20000706)242:1-2<71:EDOSB>2.0.ZU;2-W
Abstract
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.