Unique decomposition of processes
A process is irreducible (with respect to \(\|)\) if whenever \(P=Q\| R\), we have that either \(Q=0\) or \(R=0\). An irreducible process is prime if it is not equal to 0. A multiset \(\{A_ 1,\dots,A_ n\}\) of primes is a decomposition of \(P\) if \(P=A_ 1\| A_ 2\|\cdots\| A_ n\). It is shown that any finite process (with CCS like parallel operator without communications) can be uniquely decomposed into prime processes with respect to bisimulation equivalence. A presented proof is non- constructive. Counterexamples to such result for both failure (testing) equivalence and trace equivalence are presented. Moreover it is shown that prime decomposition cannot exist for arbitrary infinite processes.
- scientific article; zbMATH DE number 4777
- Mathematical Foundations of Computer Science 2003
- On unique decomposition of processes in the applied -calculus
- On the existence and decidability of unique decompositions of processes in the applied \(\pi\)-calculus
- Effective decomposability of sequential behaviours
- A Theory of Communicating Sequential Processes
- scientific article; zbMATH DE number 3716792 (Why is no real title available?)
- scientific article; zbMATH DE number 23767 (Why is no real title available?)
- scientific article; zbMATH DE number 42752 (Why is no real title available?)
- Testing equivalences for processes
- A polynomial algorithm for deciding bisimilarity of normed context-free processes
- Effective decomposability of sequential behaviours
- CCS with Hennessy's merge has no finite-equational axiomatization
- Decomposition orders -- another generalisation of the fundamental theorem of arithmetic
- Timing and causality in process algebra
- Team bisimilarity, and its associated modal logic, for BPP nets
- HOCore in Coq
- Distribution of behaviour into parallel communicating subsystems
- A geometric approach to the problem of unique decomposition of processes
- scientific article; zbMATH DE number 4005594 (Why is no real title available?)
- scientific article; zbMATH DE number 4777 (Why is no real title available?)
- A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
- On unique decomposition of processes in the applied -calculus
- Unique parallel decomposition for the \(\pi\)-calculus
- Are Two Binary Operators Necessary to Obtain a Finite Axiomatisation of Parallel Composition?
- Pushdown automata, multiset automata, and Petri nets
- How to Parallelize sequential processes
- Compositional learning for interleaving parallel automata
- Infinite results
- On the expressiveness and decidability of higher-order process calculi
- Decidability results in automata and process theory
- Realisability of global models of interaction
- On decidability of the bisimilarity on higher-order processes with parameterization
- Axiomatising weak bisimulation congruences over CCS with left merge and communication merge
- Unique parallel decomposition in branching and weak bisimulation semantics
- On the existence and decidability of unique decompositions of processes in the applied \(\pi\)-calculus
This page was built for publication: Unique decomposition of processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1208422)
