Publication details
Unification Modulo Associativity and Idempotency Is NP-complete
| Authors | |
|---|---|
| Year of publication | 2002 |
| Type | Article in Proceedings |
| Conference | Mathematical Foundations of Computer Science 2002:27th International Symposium |
| MU Faculty or unit | |
| Citation | |
| Field | General mathematics |
| Keywords | unification; free idempotent semigroups; equations |
| Description | We show that the unification problem for the theory of one associative and idempotent function symbol (AI-unification), i.e. solving word equations in free idempotent semigroups, is NP-complete. |
| Related projects: |