HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Unification in Extensions of Shallow Equational Theories

Florent Jacquemard 1 Christoph Meyer Christoph Weidenbach
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We show that unification in certain extensions of shallow equational theories is decidable. Our extensions generalize the known classes of shallow or standard equational theories. In order to prove decidability of unification in the extensions, a class of Horn clause sets called sorted shallow equational theories is introduced. This class is a natural extension of tree automata with equality constraints between brother subterms as well as shallow sort theories. We show that saturation under sorted superposition is effective on sorted shallow equational theories. So called semi-linear equational theories can be effectively transformed into equivalent sorted shallow equational theories and generalize the classes of shallow and standard equational theories.
Document type :
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 8:22:19 AM
Last modification on : Friday, February 4, 2022 - 3:21:43 AM
Long-term archiving on: : Friday, November 25, 2016 - 11:38:35 AM


  • HAL Id : inria-00098740, version 1



Florent Jacquemard, Christoph Meyer, Christoph Weidenbach. Unification in Extensions of Shallow Equational Theories. [Intern report] 98-R-387 || jacquemard98a, 1998, 33 p. ⟨inria-00098740⟩



Record views


Files downloads