KLÍMA, Ondřej. Unification Modulo Associativity and Idempotency Is NP-complete. In Mathematical Foundations of Computer Science 2002:27th International Symposium. Berlin: Springer-Verlag. s. 423-432. Lecture Notes in Computer Science, 2420. ISBN 3-540-44040-2. 2002.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Unification Modulo Associativity and Idempotency Is NP-complete
Autoři KLÍMA, Ondřej (203 Česká republika, garant).
Vydání Berlin, Mathematical Foundations of Computer Science 2002:27th International Symposium, s. 423-432, Lecture Notes in Computer Science, 2420, 2002.
Nakladatel Springer-Verlag
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 10101 Pure mathematics
Stát vydavatele Polsko
Utajení není předmětem státního či obchodního tajemství
Kód RIV RIV/00216224:14310/02:00007266
Organizační jednotka Přírodovědecká fakulta
ISBN 3-540-44040-2
UT WoS 000181442200035
Klíčová slova anglicky unification; free idempotent semigroups; equations
Štítky equations, free idempotent semigroups, unification
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: doc. Mgr. Ondřej Klíma, Ph.D., učo 3868. Změněno: 21. 11. 2006 17:47.
Anotace
We show that the unification problem for the theory of one associative and idempotent function symbol (AI-unification), i.e. solving word equations in free idempotent semigroups, is NP-complete.
Návaznosti
MSM 143100009, záměrNázev: Matematické struktury algebry a geometrie
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Matematické struktury algebry a geometrie
VytisknoutZobrazeno: 20. 4. 2024 16:03