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}.
Get full access to this article
View all access options for this article.