Matching 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 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:	Nekonečně stavové souběžné systémy - modely a verifikace Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů Matematické struktury algebry a geometrie