inria-00098740, version 1

Unification in Extensions of Shallow Equational Theories

Florent Jacquemard () ^a, 1, Christoph Meyer ^b, Christoph Weidenbach ^b

N° 98-R-387 || jacquemard98a (1998)

• a –  INRIA
• b –  MAX-PLANCK-INSTITUT FUR INFORMATIK, IM STADTWALD, 66123 SAARBRUCKEN, GERMANY
• 1 :  PROTHEO (INRIA Lorraine - LORIA)
• 
  INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL) France

Références bibliographiques

• Type de publication : Rapports
• Domaine : Informatique/Autre
• Titre : Unification in Extensions of Shallow Equational Theories
• Résumé : 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.
• Langue du document : Anglais
• Type de rapport : Interne
• Nombre de pages : 33 p
• Date de publication : 1998
• Mots-clés : e-unification – tree automata – monadic theories – superposition – decidability. || e-unification – automates d'arbres – théories monadiques – décidabilité.
• Commentaire : Rapport interne.
• Référence interne : 98-R-387 || jacquemard98a

• inria-00098740, version 1
• http://hal.inria.fr/inria-00098740
• oai:hal.inria.fr:inria-00098740
• Contributeur : Publications Loria <>
• Soumis le : Mardi 26 Septembre 2006, 08:22:19
• Dernière modification le : Jeudi 28 Septembre 2006, 15:22:44