D 2000

Matching Modulo Associativity and Idempotency is NP-Complete

KLÍMA, Ondřej a Jiří SRBA

Základní údaje

Originální název

Matching Modulo Associativity and Idempotency is NP-Complete

Autoři

KLÍMA, Ondřej a Jiří SRBA

Vydání

Berlin, Mathematical Foundation of Computer Science 2000, 25th International Symposium, s. 456-466, Lecture Notes in Computer Science, 1893, 2000

Nakladatel

Springer-Verlag

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10101 Pure mathematics

Stát vydavatele

Slovensko

Utajení

není předmětem státního či obchodního tajemství

Kód RIV

RIV/00216224:14310/00:00002108

Organizační jednotka

Přírodovědecká fakulta

ISBN

3-540-67901-4
Změněno: 10. 1. 2001 12:13, doc. Mgr. Ondřej Klíma, Ph.D.

Anotace

V originále

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.

Návaznosti

GA201/00/0400, projekt VaV
Název: Nekonečně stavové souběžné systémy - modely a verifikace
Investor: Grantová agentura ČR, Nekonečně stavové souběžné systémy - modely a verifikace
MSM 143100009, záměr
Název: Matematické struktury algebry a geometrie
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Matematické struktury algebry a geometrie
MSM 143300001, záměr
Název: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Nesekvenční modely výpočtů -- kvantové a souběžné distribuované modely výpočetních procesů