Reducibility of synchronization structures (Q1085606)

This paper is concerned with synchronization structures (or 'purely parallel' control structures), i.e., control structures with (2-way) forks and (2-way) joins as only control nodes. A synchronization structure is reducible iff it can be converted into an equivalent structured version, obtainable from a set of simpler ('primitive') structures. This paper derives necessary and sufficient conditions for a synchronization structure to be reducible and exhibits infinite families of irreducible synchronization structures. Posets associated with synchronization structures and a particular type of homomorphism ('structuring function') between posets play an important role in this paper.