Path category for free - Open morphisms from coalgebras with non-deterministic branching
Path category for free - Open morphisms from coalgebras with non-deterministic branching
复制标题
免费路径类别 - 来自具有非确定性分支的余代数的开放态射
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
I. Hasuo
中科院分区：
文献类型：
--
作者：
Thorsten Wißmann;Jérémy Dubut;Shin;I. Hasuo
对于变迁系统的变体及其互模拟，存在不同的分类方法。一种是针对函子\(G\)的余代数，其中互模拟被定义为\(G\) - 余代数同态的一个跨度。另一种是依据路径范畴和开态射，其中互模拟被定义为开态射的一个跨度。这种相似性并非偶然：给定一个满足特定条件的函子\(G\)，我们为带点的\(G\) - 余代数和宽松同态导出一个路径范畴，使得开态射恰好是\(G\) - 余代数同态。上述构造为不同类型的变迁系统免费提供了路径范畴和迹语义：（1）非确定性树自动机；（2）正则非确定性名称自动机（RNNA），一种存在于名称集合中的表达性自动机概念；（3）多类变迁系统。最后这个实例与拉索塔（Lasota）的构造相关，不过方向相反。
There are different categorical approaches to variations of transition systems and their bisimulations. One is coalgebra for a functor G, where a bisimulation is defined as a span of G-coalgebra homomorphism. Another one is in terms of path categories and open morphisms, where a bisimulation is defined as a span of open morphisms. This similarity is no coincidence: given a functor G, fulfilling certain conditions, we derive a path-category for pointed G-coalgebras and lax homomorphisms, such that the open morphisms turn out to be precisely the G-coalgebra homomorphisms. The above construction provides path-categories and trace semantics for free for different flavours of transition systems: (1) non-deterministic tree automata (2) regular nondeterministic nominal automata (RNNA), an expressive automata notion living in nominal sets (3) multisorted transition systems. This last instance relates to Lasota’s construction, which is in the converse direction.