Unification Modulo Associativity and Idempotency Is NP-complete

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, 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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.