D 2002

Unification Modulo Associativity and Idempotency Is NP-complete

KLÍMA, Ondřej

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

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

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 21. 11. 2006 17:47, doc. Mgr. Ondřej Klíma, Ph.D.

Anotace

V originále

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ěr
Název: Matematické struktury algebry a geometrie
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Matematické struktury algebry a geometrie