Composition and decomposition in true-concurrency

Publikationstyp
Conference Paper
Date Issued
2005
Sprache
English
Author(s)
Fröschle, Sibylle B.  orcid-logo
TORE-URI
http://hdl.handle.net/11420/11322
First published in
Lecture notes in computer science  
Number in series
3441 LNCS
Start Page
333
End Page
347
Citation
Lecture Notes in Computer Science 3441: 333-347 (2005)
Contribution to Conference
8th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2005, held as part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2005  
Publisher DOI
10.1007/978-3-540-31982-5_21
Scopus ID
2-s2.0-24644490262
Publisher
Springer
The idea of composition and decomposition to obtain computability results is particularly relevant for true-concurrency. In contrast to the interleaving world, where composition and decomposition must be considered with respect to a process algebra operator, e.g. parallel composition, we can directly recognize whether a truly-concurrent model such as a labelled asynchronous transition system or a 1 -safe Petri net can be dissected into independent 'chunks of behaviour '. In this paper we introduce the corresponding concept 'decomposition into independent components', and investigate how it translates into truly-concurrent bisimulation equivalences. We prove that, under a natural restriction, history preserving (hp), hereditary hp (hhp), and coherent hhp (chhp) bisimilarity are decomposable with respect to prime decompositions. Apart from giving a general proof technique our decomposition theory leads to several coincidence results. In particular, we resolve that hp, hhp, and chhp bisimilarity coincide for 'normal form' basic parallel processes.
DDC Class
004: Informatik