TY - JOUR

T1 - A theory for nondeterminism, parallelism, communication, and concurrency

AU - Broy, Manfred

PY - 1986

Y1 - 1986

N2 - An applicative language is introduced for representing concurrent programs and communicating systems in the form of mutually recursive systems of nondeterministic equations for functions and streams. Mathematical semantics is defined by associating particular fixed points with such systems. These fixed points are chosen using a combination of several complete partial orderings. Operational semantics is described in the form of term rewriting rules, consistent with the mathematical semantics. It represents data-driven reduction semantics for usual expressions and data-driven data flow semantics in the case of recursive stream equations. So the language allows to treat the basic semantic notions of nondeterminism, parallelism, communication, and concurrency for multiprogramming in a completely formal, applicative framework. In particular, it provides a semantic theory for networks of loosely coupled, nondeterministic, communicating, stream processing functions. Finally, the relationship of the presented language to partial recursive functions and nonconventional computational models such as data flow and reduction machines is shown.

AB - An applicative language is introduced for representing concurrent programs and communicating systems in the form of mutually recursive systems of nondeterministic equations for functions and streams. Mathematical semantics is defined by associating particular fixed points with such systems. These fixed points are chosen using a combination of several complete partial orderings. Operational semantics is described in the form of term rewriting rules, consistent with the mathematical semantics. It represents data-driven reduction semantics for usual expressions and data-driven data flow semantics in the case of recursive stream equations. So the language allows to treat the basic semantic notions of nondeterminism, parallelism, communication, and concurrency for multiprogramming in a completely formal, applicative framework. In particular, it provides a semantic theory for networks of loosely coupled, nondeterministic, communicating, stream processing functions. Finally, the relationship of the presented language to partial recursive functions and nonconventional computational models such as data flow and reduction machines is shown.

UR - http://www.scopus.com/inward/record.url?scp=0022875062&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(86)90040-X

DO - 10.1016/0304-3975(86)90040-X

M3 - Review article

AN - SCOPUS:0022875062

SN - 0304-3975

VL - 45

SP - 1

EP - 61

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - C

ER -