Technical Report CS0350

Title: Reducibility of Syncrhonization Structures
Authors: A. Ginzburg and M. Yoeli
Abstract: This paper is concerned with synchonization 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 fot a synchronization structure to be reducible and exhibits infinite families of irreducible syochrohization structures. Posets associated with synchronization structures, and a particular type of homomorphism ("structuring function") between posets play an important role in the paper.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1985
To the main CS technical reports page

Computer science department, Technion