Matching Modulo Associativity and Idempotency is NP-Complete
AbstractWe 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  and a revision of .
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
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.