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 metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/inria-00456848
Contributor : Tony Bourdier <>
Submitted on : Saturday, April 17, 2010 - 7:24:41 PM
Last modification on : Thursday, January 11, 2018 - 6:22:10 AM
Long-term archiving on : Thursday, September 23, 2010 - 12:55:18 PM

File

short.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00456848, version 2

Collections

Citation

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

Share

Metrics

Record views

295

Files downloads

117