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í

Označené pro přenos do RIV

Ano

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ů