文章基本信息

标题：Matching Modulo Associativity and Idempotency is NP-Complete
本地全文：下载
作者：Ondrej Klima ; Jirí Srba
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：2000
卷号：7
期号：13
出版社：Aarhus University
摘要：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].