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 | KLÍMA, Ondřej. Unification Modulo Associativity and Idempotency Is NP-complete. In Mathematical Foundations of Computer Science 2002:27th International Symposium. Berlin: Springer-Verlag, 2002, s. 423-432. Lecture Notes in Computer Science, 2420. ISBN 3-540-44040-2. |
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: |