A Semiring Approach to Equivalences, Bisimulations and Control

erschienen 2009 in R. Berghammer, A. M. Jaoua, B. Möller (eds.): Relations and Kleene Algebra in Computer Science, LNCS 5827.
pp. 134-149, 2009.

Abstract:
Equivalences, partitions and (bi)simulations are usually tackled using concrete relations. There are only few treatments by abstract relation algebra or category theory. We give an approach based on the theory of semirings and quantales. This allows applying the results directly to structures such as path and tree algebras which is not as straightforward in the other approaches mentioned. Also, the amount of higher-order formulations used is low and only a one-sorted algebra is used. This makes the theory suitable for fully automated first-order proof systems. As a small application we show how to use the algebra to construct a simple control policy for infinite-state transition systems.