Adventures in associative-commutative unification (A summary)
| Autor: | Jim Christian, Patrick Lincoln |
|---|---|
| Rok vydání: | 2005 |
| Předmět: |
Theoretical computer science
Matching (graph theory) Unification Diophantine set Diophantine equation Cornacchia's algorithm Algebra Prolog TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Computer Science::Programming Languages computer Commutative property Associative property computer.programming_language Mathematics |
| Zdroj: | 9th International Conference on Automated Deduction ISBN: 354019343X CADE |
| Popis: | We have discovered an efficient algorithm for matching and unification in associative-commutative (AC) and associative-commutative-idempotent (ACI) equational theories. In most cases of AC unification and in all cases of ACI unification our method obviates the need for solving diophantine equations, and thus avoids one of the bottlenecks of other associative-commutative unification techniques. The algorithm efficiently utilizes powerful constraints to eliminate much of the search involved in generating valid substitutions. Moreover, it is able to generate solutions lazily, enabling its use in an SLD-resolution-based environment like Prolog. We have found the method to run much faster and use less space than other associative-commutative unification procedures on many commonly encountered AC problems. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|