Complexity issues of checking identities in finite monoids

KLÍMA, Ondřej. Complexity issues of checking identities in finite monoids. Semigroup Forum. Springer-Verlag, 2009, roč. 79, č. 3, s. 435-444. ISSN 0037-1912.

Základní údaje

• Originální název: Complexity issues of checking identities in finite monoids
• Název česky: Složitost kontroly identit v konečných monoidech
• Autoři: KLÍMA, Ondřej (203 Česká republika, garant).
• Vydání: Semigroup Forum, Springer-Verlag, 2009, 0037-1912.

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Článek v odborném periodiku
• Obor: 10101 Pure mathematics
• Stát vydavatele: Německo
• Utajení: není předmětem státního či obchodního tajemství
• Impakt faktor: Impact factor: 0.597
• Kód RIV: RIV/00216224:14310/09:00029605
• Organizační jednotka: Přírodovědecká fakulta
• UT WoS: 000271737700002
• Klíčová slova anglicky: Checking identities Finite semigroups Complexity
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

We study the computational complexity of checking identities in a fixed finite monoid. We find the smallest monoid for which this problem is coNPcomplete and describe a significant class of finite monoids for which the problem is tractable.

Anotace česky

Studujeme výpočetní složitost problému kontroly identit v pevně daném konečném monoidu. Nalezli jsme nejmenší monoid pro který je tento problém coNPúplný a popsali zásadní třídu konečných monoidů pro které je problém efektivně řešitelný.

Návaznosti

• GA201/06/0936, projekt VaV: Název: Algebraické metody v teorii automatů a formálních jazyků

Investor: Grantová agentura ČR, Algebraické metody v teorii automatů a formálních jazyků

• MSM0021622409, záměr: Název: Matematické struktury a jejich fyzikální aplikace

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Matematické struktury a jejich fyzikální aplikace

• 1M0545, projekt VaV: Název: Institut Teoretické Informatiky

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky