Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951399 | Journal of Logical and Algebraic Methods in Programming | 2017 | 22 Pages |
Abstract
Multirelations provide a semantic domain for computing systems that involve two dual kinds of nondeterminism. This paper presents relational formalisations of Kleisli, Parikh and Peleg compositions and liftings of multirelations. These liftings are similar to those that arise in the Kleisli category of the powerset monad. We show that Kleisli composition of multirelations is associative, but need not have units. Parikh composition may neither be associative nor have units, but yields a category on the subclass of up-closed multirelations. Finally, Peleg composition has units, but need not be associative; a category is obtained when multirelations are union-closed.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hitoshi Furusawa, Yasuo Kawahara, Georg Struth, Norihiro Tsumagari,