Search

• < Previous
• 1
• Next >

---

Quasilinear-time Computation of Generic Modal Witnesses for Behavioural Inequivalence

Thorsten Wißmann ; Stefan Milius ; Lutz Schröder.

We provide a generic algorithm for constructing formulae that distinguish behaviourally inequivalent states in systems of various transition types such as nondeterministic, probabilistic or weighted; genericity over the transition type is achieved by working with coalgebras for a set functor in the&nbsp;[&hellip;]

---

Semantics of Higher-Order Recursion Schemes

Jiri Adamek ; Stefan Milius ; Jiri Velebil.

Higher-order recursion schemes are recursive equations defining new operations from given ones called "terminals". Every such recursion scheme is proved to have a least interpreted semantics in every Scott's model of \lambda-calculus in which the terminals are interpreted as continuous operations.&nbsp;[&hellip;]

---

Abstract GSOS Rules and a Modular Treatment of Recursive Definitions

Stefan Milius ; Lawrence S Moss ; Daniel Schwencke.

Terminal coalgebras for a functor serve as semantic domains for state-based systems of various types. For example, behaviors of CCS processes, streams, infinite trees, formal languages and non-well-founded sets form terminal coalgebras. We present a uniform account of the semantics of recursive&nbsp;[&hellip;]

---

Elgot Algebras

Jiri Adamek ; Stefan Milius ; Jiri Velebil.

Denotational semantics can be based on algebras with additional structure (order, metric, etc.) which makes it possible to interpret recursive specifications. It was the idea of Elgot to base denotational semantics on iterative theories instead, i.e., theories in which abstract recursive&nbsp;[&hellip;]

---

Well-Pointed Coalgebras

Jiří Adámek ; Stefan Milius ; Lawrence S Moss ; Lurdes Sousa.

For endofunctors of varieties preserving intersections, a new description of the final coalgebra and the initial algebra is presented: the former consists of all well-pointed coalgebras. These are the pointed coalgebras having no proper subobject and no proper quotient. The initial algebra consists&nbsp;[&hellip;]

---

Corecursive Algebras, Corecursive Monads and Bloom Monads

Jiří Adámek ; Mahdie Haddadi ; Stefan Milius.

An algebra is called corecursive if from every coalgebra a unique coalgebra-to-algebra homomorphism exists into it. We prove that free corecursive algebras are obtained as coproducts of the terminal coalgebra (considered as an algebra) and free algebras. The monad of free corecursive algebras is&nbsp;[&hellip;]

---

Proper Functors and Fixed Points for Finite Behaviour

Stefan Milius.

The rational fixed point of a set functor is well-known to capture the behaviour of finite coalgebras. In this paper we consider functors on algebraic categories. For them the rational fixed point may no longer be fully abstract, i.e. a subcoalgebra of the final coalgebra. Inspired by \'Esik and&nbsp;[&hellip;]

---

A Categorical Approach to Syntactic Monoids

Jiří Adamek ; Stefan Milius ; Henning Urbat.

The syntactic monoid of a language is generalized to the level of a symmetric monoidal closed category $\mathcal D$. This allows for a uniform treatment of several notions of syntactic algebras known in the literature, including the syntactic monoids of Rabin and Scott ($\mathcal D=$ sets), the&nbsp;[&hellip;]

---

Efficient and Modular Coalgebraic Partition Refinement

Thorsten Wißmann ; Ulrich Dorsch ; Stefan Milius ; Lutz Schröder.

We present a generic partition refinement algorithm that quotients coalgebraic systems by behavioural equivalence, an important task in system analysis and verification. Coalgebraic generality allows us to cover not only classical relational systems but also, e.g. various forms of weighted systems&nbsp;[&hellip;]

---