TY - GEN
T1 - Currying second-order unification problems
AU - Levy, Jordi
AU - Villaret, Mateu
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - The Curry form of a term, like f(a, b), allows us to write it, using just a single binary function symbol, as @(@(f, a), b). Using this technique we prove that the signature is not relevant in second-order unification, and conclude that one binary symbol is enough. By currying variable applications, like X(a), as @(X, a), we can transform second-order terms into first-order terms, but we have to add betareduction as a theory. This is roughly what it is done in explicit unification. We prove that by currying only constant applications we can reduce second-order unification to second-order unification with just one binary function symbol. Both problems are already known to be undecidable, but applying the same idea to context unification, for which decidability is still unknown, we reduce the problem to context unification with just one binary function symbol. We also discuss about the difficulties ofapplying the same ideas to third or higher order unification.
AB - The Curry form of a term, like f(a, b), allows us to write it, using just a single binary function symbol, as @(@(f, a), b). Using this technique we prove that the signature is not relevant in second-order unification, and conclude that one binary symbol is enough. By currying variable applications, like X(a), as @(X, a), we can transform second-order terms into first-order terms, but we have to add betareduction as a theory. This is roughly what it is done in explicit unification. We prove that by currying only constant applications we can reduce second-order unification to second-order unification with just one binary function symbol. Both problems are already known to be undecidable, but applying the same idea to context unification, for which decidability is still unknown, we reduce the problem to context unification with just one binary function symbol. We also discuss about the difficulties ofapplying the same ideas to third or higher order unification.
UR - https://www.scopus.com/pages/publications/84947216944
U2 - 10.1007/3-540-45610-4_23
DO - 10.1007/3-540-45610-4_23
M3 - Conference proceeding
AN - SCOPUS:84947216944
SN - 3540439161
SN - 9783540439165
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 326
EP - 339
BT - Rewriting Techniques and Applications - 13th International Conference, RTA 2002, Proceedings
A2 - Tison, Sophie
PB - Springer Verlag
T2 - 13th International Conference on Rewriting Techniques and Applications, RTA 2002
Y2 - 22 July 2002 through 24 July 2002
ER -