Proving safety properties of rewrite theories

Camilo Rocha, José Meseguer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Rewrite theories are a general and expressive formalism for specifying concurrent systems in which states are axiomatized by equations and transitions among states are axiomatized by rewrite rules. We present a deductive approach for verifying safety properties of rewrite theories in which all formal temporal reasoning about concurrent transitions is ultimately reduced to purely equational inductive reasoning. Narrowing modulo axioms is extensively used in our inference system to further simplify the equational proof obligations to which all proofs of safety formulas are ultimately reduced. In this way, existing equational reasoning techniques and tools can be directly applied to verify safety properties of concurrent systems. We report on the implementation of this deductive system in the Maude Invariant Analyzer tool, which provides a substantial degree of automation and can automatically discharge many proof obligations without user intervention.

Original languageEnglish (US)
Title of host publicationAlgebra and Coalgebra in Computer Science - 4th International Conference, CALCO 2011, Proceedings
Pages314-328
Number of pages15
DOIs
StatePublished - Sep 26 2011
Event4th International Conference on Algebra and Coalgebra in Computer Science, CALCO 2011 - Winchester, United Kingdom
Duration: Aug 30 2011Sep 2 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6859 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other4th International Conference on Algebra and Coalgebra in Computer Science, CALCO 2011
CountryUnited Kingdom
CityWinchester
Period8/30/119/2/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Proving safety properties of rewrite theories'. Together they form a unique fingerprint.

  • Cite this

    Rocha, C., & Meseguer, J. (2011). Proving safety properties of rewrite theories. In Algebra and Coalgebra in Computer Science - 4th International Conference, CALCO 2011, Proceedings (pp. 314-328). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6859 LNCS). https://doi.org/10.1007/978-3-642-22944-2_22