Matching Modulo Associativity and Idempotency is NP-Complete

Ondrej Klima; Jirí Srba

doi:10.7146/brics.v7i13.20140

Matching Modulo Associativity and Idempotency is NP-Complete

Authors

Ondrej Klima
Jirí Srba

DOI:

https://doi.org/10.7146/brics.v7i13.20140

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

Downloads

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