Skip to main navigation Skip to search Skip to main content

Currying second-order unification problems

  • CSIC - Research Institute of Artificial Intelligence
  • IMA

Research output: Chapter in Book/Conference proceedingConference proceedingpeer-review

13 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationRewriting Techniques and Applications - 13th International Conference, RTA 2002, Proceedings
EditorsSophie Tison
PublisherSpringer Verlag
Pages326-339
Number of pages14
ISBN (Print)3540439161, 9783540439165
DOIs
Publication statusPublished - 2002
Externally publishedYes
Event13th International Conference on Rewriting Techniques and Applications, RTA 2002 - Copenhagen, Denmark
Duration: 22 Jul 200224 Jul 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2378
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Conference on Rewriting Techniques and Applications, RTA 2002
Country/TerritoryDenmark
CityCopenhagen
Period22/07/0224/07/02

Fingerprint

Dive into the research topics of 'Currying second-order unification problems'. Together they form a unique fingerprint.

Cite this