KLÍMA, Ondřej. Identity checking problem for transformation monoids. Semigroup Forum, Springer-Verlag, 2012, roč. 84, č. 3, s. 487-498. ISSN 0037-1912. doi:10.1007/s00233-012-9401-7.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Identity checking problem for transformation monoids
Název česky Problém kontroly identit v transformačních monoidech
Autoři KLÍMA, Ondřej (203 Česká republika, garant, domácí).
Vydání Semigroup Forum, Springer-Verlag, 2012, 0037-1912.
Další údaje
Originální jazyk angličtina
Typ výsledku Článek v odborném periodiku
Obor Pure mathematics
Stát vydavatele Spojené státy americké
Utajení není předmětem státního či obchodního tajemství
Impakt faktor Impact factor: 0.455
Kód RIV RIV/00216224:14310/12:00057566
Organizační jednotka Přírodovědecká fakulta
Doi http://dx.doi.org/10.1007/s00233-012-9401-7
UT WoS 000306590200005
Klíčová slova anglicky Checking identities; Finite semigroups; Complexity
Štítky AKR, rivok
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnila: Ing. Andrea Mikešková, učo 137293. Změněno: 10. 4. 2013 18:35.
Anotace
We study the computational complexity of checking identities in a fixed finite monoid. We prove that this problem is coNP-complete for the monoid of all full transformations of a 4-element set. This result completes the description of the complexity of checking identities in the transformation monoids.
Anotace česky
Studujeme výpočetní složitost problému kontroly identit v pevně daném konečném monoidu. Dokázali jsem, že tento problém je coNP-těžký pro transformační monoid čtyřprvkové množiny. Tím jsme dokončili popis složitosti problému kontroly identit v transformačních monoidech.
Návaznosti
GA201/09/1313, projekt VaVNázev: Algebraické metody v teorii automatů a formálních jazyků II
Investor: Grantová agentura ČR, Standardní projekty
MSM0021622409, záměrNázev: Matematické struktury a jejich fyzikální aplikace
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumné záměry
1M0545, projekt VaVNázev: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumná centra (Národní program výzkumu)
VytisknoutZobrazeno: 24. 8. 2019 20:07