Relational Semantics of Non-Deterministic Dataflow

  • Thomas Troels Hildebrandt
  • Prakash Panangaden
  • Glynn Winskel

Abstract

We recast dataflow in a modern categorical light using profunctors as a generalization of relations. The well known causal anomalies associated with relational semantics of indeterminate dataflow are avoided, but still we preserve
much of the intuitions of a relational model. The development fits with the view of categories of models for concurrency and the general treatment of bisimulation they provide. In particular it fits with the recent categorical formulation of feedback using traced monoidal categories. The payoffs are: (1) explicit relations to existing models and semantics, especially the
usual axioms of monotone IO automata are read off from the definition of profunctors, (2) a new definition of bisimulation for dataflow, the proof of the congruence of which benefits from the preservation properties associated with open maps and (3) a treatment of higher-order dataflow as a biproduct,
essentially by following the geometry of interaction programme.
Published
1997-06-06
How to Cite
Hildebrandt, T., Panangaden, P., & Winskel, G. (1997). Relational Semantics of Non-Deterministic Dataflow. BRICS Report Series, 4(36). https://doi.org/10.7146/brics.v4i36.18962