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 → 2Y (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(ae) = F(ae)†(G(ae)) for all inputs ae e X. Here P denotes a certain powerdomain operator, and † 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 determinate processes and “infinity-fair merge” processes.