Reducibility of synchronization structures
type: Item
instance of: scholarly article
title: Reducibility of synchronization structures
zbMATH Open document ID: 0607.68019
DOI: 10.1016/0304-3975(85)90172-0
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68N25
zbMATH DE Number: 3982503
zbMATH Keywords: structured programming
zbMATH Keywords: parallel programming
zbMATH Keywords: parallel processing
zbMATH Keywords: synchronization structures
zbMATH Keywords: control structures
zbMATH Keywords: posets
author: Abraham Ginzburg
author: Michael Yoeli
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90172-0
OpenAlex ID: W2104289632
cites work: Q3318086
cites work: Structured flowcharts for multiprocessing
cites work: Marked directed graphs
cites work: Q5684216
cites work: A genealogy of control structures
cites work: Q3888511
description: scientific article; zbMATH DE number 3982503