Killing epsilons with a dagger: A coalgebraic study of systems with algebraic label structure

详细信息    查看全文

• 作者：Filippo Bonchi^a ; ^{filippo.bonchi@ens-lyon.fr" class="auth_mail" title="E-mail the corresponding author} ; Stefan Milius^b ; ¹ ; ^{mail@stefan-milius.eu" class="auth_mail" title="E-mail the corresponding author} ; Alexandra Silva^c ; ^d ; ^e ; ^{alexandra@cs.ru.nl" class="auth_mail" title="E-mail the corresponding author} ; Fabio Zanasi^a ; ^{fabio.zanasi@ens-lyon.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Coalgebras on Kleisli categories ; Parametrized fixpoint operator ; Trace semantics ; Epsilon transitions ; Mazurkiewicz traces ; Non-deterministic transducers
• 刊名：Theoretical Computer Science
• 出版年：2015
• 出版时间：2 November 2015
• 年：2015
• 卷：604
• 期：Complete
• 页码：102-126
• 全文大小：669 K

文摘

We propose an abstract framework for modelling state-based systems with internal behaviour as e.g. given by silent or ϵ-transitions. Our approach employs monads with a parametrized fixpoint operator † to give a semantics to those systems and implement a sound procedure of abstraction of the internal transitions, whose labels are seen as the unit of a free monoid. More broadly, our approach extends the standard coalgebraic framework for state-based systems by taking into account the algebraic structure of the labels of their transitions. This allows to consider a wide range of other examples, including Mazurkiewicz traces for concurrent systems and non-deterministic transducers.