Matching Modulo Associativity and Idempotency is NP-Complete

Ondrej Klíma
Jirí Srba

June 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.

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.