Matching Modulo Associativity and Idempotency is NP-Complete

  • Ondrej Klima
  • Jirí 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.
Note: this is a full version of the paper [9] and a revision of [8].
Published
2000-01-13
How to Cite
Klima, O., & Srba, J. (2000). Matching Modulo Associativity and Idempotency is NP-Complete. BRICS Report Series, 7(13). https://doi.org/10.7146/brics.v7i13.20140