Matching Modulo Associativity and Idempotency is NP-Complete - Klima, Ondrej; Srba, Jirí (BRICS Report Series, 2000)
We show that AI-matching (AI denotes the theory of an associative and idempotent function symbol), which is solving matching word equations in free idempotent semigroups, is NP-complete. Note: this is a full version of the paper [9] and a revision of [8].