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

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 as well. Furthermore, restricted forms of SREU are strongly related to word equations and finite tree automata. 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. So second-order unification plays the same fundamental role as SREU in automated reasoning in logic with equality. We exploit this connection and use finite tree automata techniques to present a very elementary undecidability proof of second-order unification, by reduction from the halting problem for Turing machines. It follows from that proof that second-order unification is undecidable for all nonmonadic second-order term languages having at least two second-order variables with sufficiently high arities

In  Proceedings of the 13th Annual IEEE Symposium on Logic in Computer Science (LICS'98)

Publisher  IEEE Computer Society
Copyright © 2007 IEEE. Reprinted from IEEE Computer Society. This material is posted here with permission of the IEEE. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to By choosing to view this document, you agree to all provisions of the copyright laws protecting it.



Previous Versions

Margus Veanes. The Relation Between Second-Order Unification and Simultaneous Rigid E-Unification, February 1998.

> Publications > The relation between second-order unification and simultaneous rigid E-unification