Unification Modulo Associativity and Idempotency Is NP-complete
| Autoři | |
|---|---|
| Rok publikování | 2002 |
| Druh | Článek ve sborníku |
| Konference | Mathematical Foundations of Computer Science 2002:27th International Symposium |
| Fakulta / Pracoviště MU | |
| Citace | |
| Obor | Obecná matematika |
| Klíčová slova | unification; free idempotent semigroups; equations |
| Popis | 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. |
| Související projekty: |