Kleisli, Parikh and Peleg Compositions and Liftings for Multirelations
Kleisli, Parikh and Peleg Compositions and Liftings for Multirelations
复制标题
Kleisli、Parikh 和 Peleg 多重关系的组合和提升
DOI：
10.1016/j.jlamp.2017.04.002
复制
发表时间：
2017
影响因子：
0.9
通讯作者：
Norihiro Tsumagari
中科院分区：
文献类型：
--
作者：
Hitoshi Furusawa;Yasuo Kawahara;Georg Struth;Norihiro Tsumagari
多重关系为涉及两种双重非确定性的计算系统提供了一个语义域。本文介绍了关系形式化的Kleisli，Parikh和Peleg组成和提升的多重关系。这些提升类似于幂集单子的Kleisli范畴中出现的提升。我们表明，Kleisli组成的多重关系是结合的，但不需要有单位。Parikh复合可能既不是结合的，也没有单位，但产生一个上闭多重关系子类的范畴。最后，Peleg复合有单位，但不需要是结合的;当多重关系是并闭的时，得到一个范畴。
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.