Unification Modulo Associativity and Idempotency Is NP-complete

Warning

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

KLÍMA Ondřej

Year of publication 2002
Type Article in Proceedings
Conference Mathematical Foundations of Computer Science 2002:27th International Symposium
MU Faculty or unit

Faculty of Science

Citation
Field General mathematics
Keywords unification; free idempotent semigroups; equations
Description We show that the unification problem for the theory of one associative and idempotent function symbol (AI-unification), i.e. solving 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.