de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

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

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45662

Veanes,  Margus
Programming Logics, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

1998-2-005
(beliebiger Volltext), 11KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Veanes, M.(1998). The relation between second-order unification and simultaneous rigid \sl E-unification (MPI-I-1998-2-005). Saarbrücken: Max-Planck-Institut für Informatik.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-7B4E-2
Zusammenfassung
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 unification than the previously known proofs exposing that already a very small fragment of second-order unification has the universal computational power.