Full Abstraction for Nondeterministic Dataflow Networks

Abstract

We discuss the problem of finding fully abstract semantic models for nondeterministic dataflow networks. We present the result that there exist nondeterministic networks using only bounded choice for which the input-output relation is not compositional. We go on to show that the trace semantics is fully abstract for all nondeterministic as well as deterministic networks.