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


The relation between second-order unification and simultaneous rigid \sl E-unification

Veanes, Margus

MPI-I-98-2-005. February 1998, 26 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
Simultaneous rigid E-unification, or SREU for short, is a fundamental
problem that arises in global methods
of automated theorem proving in classical logic with equality.
In order to do proof search in intuitionistic logic with equality one
has to handle SREU. Furthermore,
restricted forms of SREU are strongly related to word equations
and finite tree automata. Higher-order unification has applications
in proof theory, computational linguistics, program transformation,
and also in theorem proving.
It was recently shown that second-order unification has a very natural
reduction to simultaneous rigid $E$-unification, which constituted
probably the most transparent undecidability proof of SREU.
Here we show that there is also a natural encoding of
SREU in second-order unification. It follows
that the problems are logspace equivalent.
We exploit this connection and use finite tree automata techniques
to prove that second-order unification is undecidable
in more restricted cases than known before.
We present a more elementary undecidability proof of second-order
than the previously known proofs
exposing that already a very small fragment of second-order unification
has the universal computational power.
Extended version of a paper accepted for LICS'98
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-005.ps249 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:
Hide details for BibTeXBibTeX
  AUTHOR = {Veanes, Margus},
  TITLE = {The relation between second-order unification and simultaneous rigid {\sl E}-unification},
  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-005},
  MONTH = {February},
  YEAR = {1998},
  ISSN = {0946-011X},
  NOTE = {Extended version of a paper accepted for LICS'98},