Abstract of Paper

AI-matching is NP-complete
by Ondrej Klima, Jiri Srba

Abstract:

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.