Unification (2018)
6 days ago
- #algorithm
- #logic-programming
- #unification
- Unification is a process in logic and computer science for solving equations between symbolic terms.
- It has applications in logic programming and type inference.
- Terms are built from constants, variables, and function applications.
- Pattern matching is a simpler case of unification where only one term contains variables.
- Unification generalizes pattern matching by allowing both terms to contain variables.
- The most general unifier (mgu) is the simplest substitution that makes two terms equivalent.
- The unification algorithm must handle recursive checks to avoid infinite unifiers.
- The presented algorithm is correct but not optimized for performance.
- Efficiency can be improved with advanced techniques like those by Martelli and Montanari.