×

A Church-Rosser checker tool for conditional order-sorted equational Maude specifications. (English) Zbl 1306.68065

Ölveczky, Peter Csaba (ed.), Rewriting logic and its applications. 8th international workshop, WRLA 2010, held as a satellite event of ETAPS 2010, Paphos, Cyprus, March 20–21, 2010. Revised selected papers. Berlin: Springer (ISBN 978-3-642-16309-8/pbk). Lecture Notes in Computer Science 6381, 69-85 (2010).
Summary: The Church-Rosser property, together with termination, is essential for an equational specification to have good executability conditions, and also for having a complete agreement between the specification’s initial algebra, mathematical semantics, and its operational semantics by rewriting. Checking this property for expressive specifications that are order-sorted, conditional with possibly extra variables in their condition, and whose equations can be applied modulo different combinations of associativity, commutativity and identity axioms is challenging. In particular, the resulting conditional critical pairs that cannot be joined have often an intuitively unsatisfiable condition or seem intuitively joinable, so that sophisticated tool support is needed to eliminate them. Another challenge is the presence of different combinations of associativity, commutativity and identity axioms, including the very challenging case of associativity without commutativity for which no finitary unification algorithms exist. In this paper we present the foundations and illustrate the design and use of a completely new version of the Maude Church-Rosser Checker tool that addresses all the above-mentioned challenges and can deal effectively with complex conditional specifications modulo axioms.
For the entire collection see [Zbl 1197.68017].

MSC:

68Q42 Grammars and rewriting systems
68Q60 Specification and verification (program logics, model checking, etc.)

Software:

OBJ3; Maude; MTT; CRC 3; ChC 3
PDFBibTeX XMLCite
Full Text: DOI