Formal Methods in Software Engineering

Automatic equivalence proofs for non-deterministic coalgebras

Year2013
TypeJournal
StatusPublished
AuthorsMarcello Bonsangue, Georgiana Caltais, Eugen Goriac, Dorel Lucanu, Jan Rutten, Alexandra Silva

Links

Abstract

A notion of generalized regular expressions for a large class of systems modeled as coalgebras, and an analog 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 labeled transition systems. 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 labeled transition systems.

BibTeX

@Article{name, author = {M. Bonsangue and G. Caltais and E.-L. Goriac and D. Lucanu and J. Rutten and A. Silva}, title = {Automatic equivalence proofs for non-deterministic coalgebras}, journal = {Science of Computer Programming}, volume = {78}, number = {9}, pages = {1324 -- 1345}, year = {2013}, month = {}, publisher = {Elsevier}, url_publisher = {http://www.sciencedirect.com/}, url = {http://www.sciencedirect.com/science/article/pii/S0167642312001207 [SCP]} }