Concurrent Program Schemes

Article type: Research Article

Authors: Kfoury, A.J.^a | Urzyczyn, P.^b

Affiliations: [a] Computer Science Department, Boston University, Boston, MA 02215, U.S.A. | [b] Institute of Mathematics, University of Warsaw, 00-901 Warszawa, PKiN, Poland

Abstract: We study the programming formalism FD of “flow-diagrams” to which we gradually add various features of concurrency. The weakest form of concurrency is introduced by the construct “and”, which is dual to the nondeterministic choice “or” and plays a role similar to universal states in alternating Turing machines. Stronger (and more realistic) forms of concurrency are obtained when processes are allowed to communicate. We consider communication by channels and communication by messages. We calibrate the computational power of classes of concurrent programs FD+α against that of sequential programs, where α is the addition of one of the following features: {and}, {and, or}, {and, or, channels}, or {and, or, messages}.

DOI: 10.3233/FI-1987-10402

Journal: Fundamenta Informaticae, vol. 10, no. 4, pp. 337-361, 1987