Open AccessMatching Modulo Associativity and Idempotency is NP-Complete
Author(s) -
Ondřej Klíma,
Jiřı́ Srba
Publication year - 2000
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v7i13.20140
Subject(s) - idempotence , modulo , associative property , mathematics , matching (statistics) , symbol (formal) , combinatorics , arithmetic , function (biology) , word (group theory) , discrete mathematics , pure mathematics , computer science , statistics , geometry , evolutionary biology , biology , programming language
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].