Matching Modulo Associativity and Idempotency is NP-Complete

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Science. Official publication website can be found on muni.cz.

Authors	KLÍMA Ondřej SRBA Jiří
Year of publication	2000
Type	Article in Proceedings
Conference	Mathematical Foundation of Computer Science 2000, 25th International Symposium
MU Faculty or unit	Faculty of Science
Citation
Field	General mathematics
Description	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.
Related projects:	Infinite state concurrent systems - models and verification Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing Mathematical structures of algebra and geometry