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. |
Další formáty:
BibTeX
LaTeX
RIS
|
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 |
Změnil | Změnil: doc. Mgr. Ondřej Klíma, Ph.D., učo 3868. Změněno: 30. 3. 2010 14:01. |
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 |
VytisknoutZobrazeno: 21. 9. 2024 19:40