Unification Modulo Associativity and Idempotency Is NP-complete

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Science. Official publication website can be found on muni.cz.

Authors	KLÍMA Ondřej
Year of publication	2002
Type	Article in Proceedings
Conference	Mathematical Foundations of Computer Science 2002:27th International Symposium
MU Faculty or unit	Faculty of Science
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:	Mathematical structures of algebra and geometry