Matching Modulo Associativity and Idempotency is NP-Complete

Ondrej Klíma
Jirí Srba

June 2000

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.

Available as PostScript, PDF, DVI.

Last modified: 2003-06-08 by webmaster.