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

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í

Označené pro přenos do RIV

Ano

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