Unique Decomposition of Processes

Robin Milner, Faron Moller

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper, we examine questions about the prime decomposability of processes, where we define a process to be prime whenever it cannot be decomposed into nontrivial components.

We show that any finite process can be uniquely decomposed into prime processes with respect to bisimulation equivalence, and demonstrate counterexamples to such a result for both failures (testing) equivalence and trace equivalence.

Although we show that prime decompositions cannot exist for arbitrary infinite processes, we motivate but leave as open a conjecture on the unique decomposability of a wide subclass of infinite behaviours.
Original languageEnglish
Pages (from-to)357-363
Number of pages7
JournalTheoretical Computer Science
Volume107
Issue number2
DOIs
Publication statusPublished - Jan 1993

Fingerprint

Dive into the research topics of 'Unique Decomposition of Processes'. Together they form a unique fingerprint.

Cite this