Unification Modulo Associativity and Idempotency Is NP-complete

Varování

Publikace nespadá pod Filozofickou 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.