Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

Constrained rewriting in recognizable theories

Tony Bourdier 1 Horatiu Cirstea 1 
1 PAREO - Formal islands: foundations and applications
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Rewriting has long been shown useful for equational reasoning but its expressive power is not always appropriate for certain situations, as for instance for specifying partial functions and exceptions or when dealing with relations over terms. That is why some generalizations of rewriting, such as ordered rewriting, class rewriting, strategic rewriting, conditional or constrained rewriting, have emerged. In particular, constraints over terms are very suitable to define sets of terms thanks to logic formulae. Most of the works on constrained rewriting focus on order, equality, disequality and membership constraints. We extend in this paper the usual notion of constrained rewrite systems by constraining rules not only with classical constraints but with any first order formula and perform rewriting according to an interpretation of functional and predicate symbols. We then show that the specification of such interpretations with tree automata offers us a framework sufficiently powerful to build an algorithm for solving a particular case of constrained matching.
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Tony Bourdier Connect in order to contact the contributor
Submitted on : Saturday, April 17, 2010 - 7:24:41 PM
Last modification on : Wednesday, February 2, 2022 - 3:51:40 PM
Long-term archiving on: : Thursday, September 23, 2010 - 12:55:18 PM


Files produced by the author(s)


  • HAL Id : inria-00456848, version 2



Tony Bourdier, Horatiu Cirstea. Constrained rewriting in recognizable theories. {date}. ⟨inria-00456848v2⟩



Record views


Files downloads