Computer Science – Logic in Computer Science
Scientific paper
2011-04-14
Computer Science
Logic in Computer Science
Scientific paper
Coalgebras provide a uniform framework to study dynamical systems, including several types of automata. In this paper, we make use of the coalgebraic view on systems to investigate, in a uniform way, under which conditions calculi that are sound and complete with respect to behavioral equivalence can be extended to a coarser coalgebraic language equivalence, which arises from a generalised powerset construction that determinises coalgebras. We show that soundness and completeness are established by proving that expressions modulo axioms of a calculus form the rational fixpoint of the given type functor. Our main result is that the rational fixpoint of the functor $FT$, where $T$ is a monad describing the branching of the systems (e.g. non-determinism, weights, probability etc.), has as a quotient the rational fixpoint of the "determinised" type functor $\bar F$, a lifting of $F$ to the category of $T$-algebras. We apply our framework to the concrete example of weighted automata, for which we present a new sound and complete calculus for weighted language equivalence. As a special case, we obtain non-deterministic automata, where we recover Rabinovich's sound and complete calculus for language equivalence.
Bonsangue Marcello M.
Milius Stefan
Silva Alexandra
No associations
LandOfFree
Sound and complete axiomatizations of coalgebraic language equivalence does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Sound and complete axiomatizations of coalgebraic language equivalence, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sound and complete axiomatizations of coalgebraic language equivalence will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-166953