A decision procedure for bisimilarity of generalized regular expressions

A notion of generalized regular expressions for a large class of systems modeled as coalgebras, and an analogue of Kleene’s theorem and Kleene algebra, were recently proposed by a subset of the authors of this paper. Examples of the systems covered include infinite streams, deterministic automata, Mealy machines and labelled transition sytems.
In this paper, we present a novel algorithm to decide whether two expressions
are bisimilar or not. The procedure is implemented in the automatic
theorem prover CIRC, by reducing coinduction to an entailment
relation between an algebraic specification and an appropriate set of
equations. We illustrate the generality of the tool with three examples:
infinite streams of real numbers, Mealy machines and labelled transition
systems.

Sidebar