Matching Modulo Associativity and Idempotency is NP-Complete

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. 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:

You are running an old browser version. We recommend updating your browser to its latest version.