On the Relations Computable by a Class of Concurrent Automata

Abstract

We consider monotone input/output automata, which model a usefully large class of dataflow networks of indeterminate (or nonfunctional) processes. We obtain a characterization of the relations computable by these automata, which states that a relation R : X ! 2 Y (viewed as a "nondeterministic function") is the input /output relation of an automaton iff there exists a certain kind of Scott domain D, a continuous function F : X ! [D ! Y ] and a continuous function G : X ! P(D), such that R(x) = F (x) y (G(x)) for all inputs x 2 X. Here P denotes a certain powerdomain operator, and y denotes the pointwise extension to the powerdomain of a function on the underlying domain. An attractive feature of this result is that it specializes to two subclasses of automata, determinate automata, for which G is single-valued, and semi-determinate automata, for which G is a constant function. A corollary of the latter result is the impossibility of implementing "angelic merge" by a network of de...