Huet unification algorithm
E265288
algorithm in automated theorem proving
algorithm in lambda calculus
algorithm in type theory
higher-order unification algorithm
unification procedure
The Huet unification algorithm is a higher-order unification procedure introduced by Gérard Huet that generalizes first-order unification to handle lambda calculus terms and plays a key role in type theory and automated theorem proving.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Huet unification algorithm canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T2419094 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Huet unification algorithm Context triple: [Gérard Huet, knownFor, Huet unification algorithm]
-
A.
Thompson's algorithm
Thompson's algorithm is a classic computer science method for converting regular expressions into nondeterministic finite automata (NFAs), widely used in pattern matching and lexical analysis.
-
B.
Marzullo's algorithm
Marzullo's algorithm is a method for selecting the most likely correct time interval from multiple, possibly conflicting time sources, commonly used in clock synchronization systems.
-
C.
Procrustes
Procrustes is a figure from Greek mythology known as a cruel bandit who mutilated travelers to force them to fit his iron bed, until he was slain by the hero Theseus.
-
D.
Knuth–Bendix completion algorithm
The Knuth–Bendix completion algorithm is a procedure in term rewriting and automated theorem proving that transforms a set of equations into a confluent rewriting system, enabling decision of word problems in algebraic structures.
-
E.
Minkowski sum
The Minkowski sum is a fundamental operation in geometry and convex analysis that combines two sets by adding every vector in one set to every vector in the other, widely used in areas such as optimization, robotics, and computational geometry.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Huet unification algorithm Target entity description: The Huet unification algorithm is a higher-order unification procedure introduced by Gérard Huet that generalizes first-order unification to handle lambda calculus terms and plays a key role in type theory and automated theorem proving.
-
A.
Thompson's algorithm
Thompson's algorithm is a classic computer science method for converting regular expressions into nondeterministic finite automata (NFAs), widely used in pattern matching and lexical analysis.
-
B.
Marzullo's algorithm
Marzullo's algorithm is a method for selecting the most likely correct time interval from multiple, possibly conflicting time sources, commonly used in clock synchronization systems.
-
C.
Procrustes
Procrustes is a figure from Greek mythology known as a cruel bandit who mutilated travelers to force them to fit his iron bed, until he was slain by the hero Theseus.
-
D.
Knuth–Bendix completion algorithm
The Knuth–Bendix completion algorithm is a procedure in term rewriting and automated theorem proving that transforms a set of equations into a confluent rewriting system, enabling decision of word problems in algebraic structures.
-
E.
Minkowski sum
The Minkowski sum is a fundamental operation in geometry and convex analysis that combines two sets by adding every vector in one set to every vector in the other, widely used in areas such as optimization, robotics, and computational geometry.
- F. None of above. chosen
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
algorithm in automated theorem proving
ⓘ
algorithm in lambda calculus ⓘ algorithm in type theory ⓘ higher-order unification algorithm ⓘ unification procedure ⓘ |
| assumes | typed lambda calculus in many formulations ⓘ |
| comparedTo | first-order unification for its higher complexity ⓘ |
| complexity | undecidable in general for higher-order unification ⓘ |
| field |
automated theorem proving
ⓘ
higher-order logic ⓘ lambda calculus ⓘ type theory ⓘ |
| generalizes | first-order unification ⓘ |
| goal |
find substitutions for higher-order variables
ⓘ
solve higher-order unification problems ⓘ |
| handles |
flex-flex pairs
ⓘ
flex-rigid pairs ⓘ rigid-rigid pairs ⓘ |
| influenced |
design of higher-order logic provers
ⓘ
development of proof assistants like Coq ⓘ |
| introducedBy | Gérard Huet ⓘ |
| involves |
expansion of meta-variables
ⓘ
imitation rules ⓘ projection rules ⓘ search in a space of unification problems ⓘ |
| namedAfter | Gérard Huet ⓘ |
| operatesOn |
higher-order terms
ⓘ
lambda calculus terms ⓘ |
| property |
backtracking-based
ⓘ
may have infinitely many unifiers ⓘ non-unitary in general ⓘ search-based ⓘ semi-decidable ⓘ |
| relatedTo |
Robinson unification algorithm
ⓘ
first-order unification ⓘ lambda calculus ⓘ simply typed lambda calculus ⓘ |
| supports |
beta-eta conversion
ⓘ
function variables ⓘ higher-order variables ⓘ lambda abstraction ⓘ unification modulo beta-eta equivalence ⓘ |
| usedIn |
automated theorem provers
ⓘ
interactive theorem provers ⓘ proof assistants ⓘ type inference for higher-order logics ⓘ |
| uses |
beta-reduction
ⓘ
eta-conversion ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Huet unification algorithm Description of subject: The Huet unification algorithm is a higher-order unification procedure introduced by Gérard Huet that generalizes first-order unification to handle lambda calculus terms and plays a key role in type theory and automated theorem proving.
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.