Change search
ReferencesLink to record
Permanent link

Direct link
The Expressive Power of Parallelism
Number of Authors: 1
1990 (English)Report (Refereed)
Abstract [en]

We explore an algebraic language for networks consisting of a fixed number of reactive units, communicating synchronously over a fixed linking structure. The language has only two operators: disjoint parallelism, where two networks are composed in parallel without any interconnection, and linking, where an interconnection is formed between two ports. The intention is that these operators corresponds to the primitive steps when constructing networks, and that they therefore are conceptually simpler than the operators in existing process algebras. We investigate the expressive power of our language. The results are: (1) Definability of behaviours: with only three simple processing units, every finite-state behaviour can be constructed. (2) Definability of operators: we characterize the network operators which are definable within the language; these turn out to include most operators previously suggested for describing parallelism. Our results hold for any congruence between trace equivalence and observation equivalence.

Place, publisher, year, edition, pages
Kista, Sweden: Swedish Institute of Computer Science , 1990, 1. , 43 p.
SICS Research Report, ISSN 0283-3638 ; R90:16
National Category
Computer and Information Science
URN: urn:nbn:se:ri:diva-14038OAI: diva2:1035321
Original report number R90016. (Revised and extended version of the paper "The Expressive power of simple parallelism" in the proceedings of PARLE '89 Vol. II, Eindhoven, June 1989, publ. as Springer Verlag LNCS 366 pages 389-405.)Available from: 2016-10-13 Created: 2016-10-13

Open Access in DiVA

fulltext(4558 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 4558 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

ReferencesLink to record
Permanent link

Direct link