Matching Modulo Associativity and Idempotency is NP-Complete

Logo poskytovatele

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 SRBA Jiří

Rok publikování 2000
Druh Článek ve sborníku
Konference Mathematical Foundation of Computer Science 2000, 25th International Symposium
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
Obor Obecná matematika
Popis 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.
Související projekty:

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