Monoid labeled transition systems
by
H. Peter Gumm
Philipps Universitaet Marburg, Germany
Coauthors: Tobias Schröder

We consider L-labeled transition systems as coalgebras of an appropriate type functor L(-). When L is a lattice, models include Kripke structures (for L=D₂) and fuzzy transition systems (for L the real interval [0, 1]). We describe simulations and bisimulations of L-coalgebras and show that L(-) weakly preserves kernel pairs iff it weakly preserves pullbacks iff L is join-infinitely-distributive (JID).

When (L, +, 0) is an arbitrary commutative monoid, we define a finitary modification L*(-) of the type functor. L*-coalgebras then generalize, e.g., image finite transition systems. We show that every congruence is a bisimulation, if and only L is ``refinable'' in the following sense:

Whenever a₁ + ... + a_m = b₁ + ... + b_n, then there exists an m ×n-matrix M, so that for all i, j the i-th row sums to a_i and the j-th column sums to b_j.

http://www.Mathematik.uni-marburg.de/~gumm/Papers/publ.html

Date received: December 28, 2000