Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-08T14:07:25.016Z Has data issue: false hasContentIssue false

A relational model of non-deterministic dataflow

Published online by Cambridge University Press:  23 September 2004

THOMAS T. HILDEBRANDT
Affiliation:
IT University of Copenhagen, Denmark
PRAKASH PANANGADEN
Affiliation:
McGill University, Montreal, Canada
GLYNN WINSKEL
Affiliation:
University of Cambridge, U.K.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We recast dataflow in a modern categorical light using profunctors as a generalisation 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.

Information

Type
Paper
Copyright
2004 Cambridge University Press