KLÍMA, Ondřej a Jiří SRBA. Matching Modulo Associativity and Idempotency is NP-Complete. In Mathematical Foundation of Computer Science 2000, 25th International Symposium. Berlin: Springer-Verlag, 2000. s. 456-466. Lecture Notes in Computer Science, 1893. ISBN 3-540-67901-4.
Další formáty:   BibTeX LaTeX RIS
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
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 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ěnil Změnil: doc. Mgr. Ondřej Klíma, Ph.D., učo 3868. Změněno: 10. 1. 2001 12:13.
Anotace
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 VaVNázev: Nekonečně stavové souběžné systémy - modely a verifikace
Investor: Grantová agentura ČR, Standardní projekty
MSM 143100009, záměrNázev: Matematické struktury algebry a geometrie
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumné záměry
MSM 143300001, záměrNá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, Výzkumné záměry
VytisknoutZobrazeno: 18. 8. 2019 19:51