Identity checking problem for transformation monoids
| KLÍMA, Ondřej. Identity checking problem for transformation monoids. Semigroup Forum. Springer-Verlag, roč. 84, č. 3, s. 487-498. ISSN 0037-1912. doi:10.1007/s00233-012-9401-7. 2012. |
|
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 | 10101 Pure mathematics |
| Stát vydavatele | Spojené státy |
| 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 VaV | Název: Algebraické metody v teorii automatů a formálních jazyků II |
| Investor: Grantová agentura ČR, Algebraické metody v teorii automatů a formálních jazyků II | |
| 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: 19. 4. 2024 10:47