The authors describe a model of nondeterministic data flow that is abstracted from an underlying asynchronous deterministic behavior, thus representing nondeterminism resulting from a lack of information. For this construction of nondeterminism, a suitable deterministic framework is developed thoroughly.
A deterministic process is a continuous function mapping a history vector and an oracle sequence to an output history vector. Only special modeling processes fulfilling initializing and causality conditions on the input-output behavior are considered. The history vectors consist of a vector of streams of data items and “wait” items that will be discarded for the nondeterministic case. The introduced notion of behavioral equivalence of modeling processes is essentially based on the oracle sequences. In order to allow recursive definitions of processes and to construct networks of processes, a special class of operators on modeling functions is introduced. These modeling operators represent contexts for processes and are shown to preserve the modeling conditions and the behavioral equivalence of processes. A nondeterministic process is defined to be a behavior equivalence class of deterministic modeling processes of corresponding type. Operators on nondeterministic processes are defined accordingly. A main result is the extensionality of nondeterministic processes, that is, processes that have the same input-output relation in each context are equal. An alternative approach based on metric spaces is outlined briefly.
The paper is well organized and carefully written. The presentation is formal and contains all theoretical details. Most technical proofs are given in an appendix. Although a special approach is considered, the paper is self-contained. Related work is analyzed and compared. A good selection of references is also provided. The technical relevance of this work remains unclear.