Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-98-2-002

Unification in extensions of shallow equational theories

Jacquemard, Florent and Meyer, Christoph and Weidenbach, Christoph

MPI-I-98-2-002. December 1998, 31 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.

Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-98-2-002.ps.gz139 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-2-002

Hide details for BibTeXBibTeX
@TECHREPORT{JacquemardMeyerWeidenbach98,
  AUTHOR = {Jacquemard, Florent and Meyer, Christoph and Weidenbach, Christoph},
  TITLE = {Unification in extensions of shallow equational theories},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-98-2-002},
  MONTH = {December},
  YEAR = {1998},
  ISSN = {0946-011X},
}