Unification Modulo Associativity and Idempotency Is NP-complete

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.

Autoři	KLÍMA Ondřej
Rok publikování	2002
Druh	Článek ve sborníku
Konference	Mathematical Foundations of Computer Science 2002:27th International Symposium
Fakulta / Pracoviště MU	Přírodovědecká fakulta
Citace
Obor	Obecná matematika
Klíčová slova	unification; free idempotent semigroups; equations
Popis	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.
Související projekty:	Matematické struktury algebry a geometrie