Identity checking problem for transformation monoids
| KLÍMA, Ondřej. Identity checking problem for transformation monoids. Semigroup Forum. Springer-Verlag, 2012, vol. 84, No 3, p. 487-498. ISSN 0037-1912. Available from: https://dx.doi.org/10.1007/s00233-012-9401-7. |
|
Other formats:
BibTeX
LaTeX
RIS
|
| Basic information | |
|---|---|
| Original name | Identity checking problem for transformation monoids |
| Name in Czech | Problém kontroly identit v transformačních monoidech |
| Authors | KLÍMA, Ondřej (203 Czech Republic, guarantor, belonging to the institution). |
| Edition | Semigroup Forum, Springer-Verlag, 2012, 0037-1912. |
| Other information | |
|---|---|
| Original language | English |
| Type of outcome | Article in a journal |
| Field of Study | 10101 Pure mathematics |
| Country of publisher | United States of America |
| Confidentiality degree | is not subject to a state or trade secret |
| Impact factor | Impact factor: 0.455 |
| RIV identification code | RIV/00216224:14310/12:00057566 |
| Organization unit | Faculty of Science |
| Doi | http://dx.doi.org/10.1007/s00233-012-9401-7 |
| UT WoS | 000306590200005 |
| Keywords in English | Checking identities; Finite semigroups; Complexity |
| Tags | AKR, rivok |
| Tags | International impact, Reviewed |
| Changed by | Changed by: Ing. Andrea Mikešková, učo 137293. Changed: 10/4/2013 18:35. |
| Abstract |
|---|
| 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. |
| Abstract (in Czech) |
|---|
| 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. |
| Links | |
|---|---|
| GA201/09/1313, research and development project | Name: Algebraické metody v teorii automatů a formálních jazyků II |
| Investor: Czech Science Foundation, Algebraic Methods in Automata and Formal Language Theory II | |
| MSM0021622409, plan (intention) | Name: Matematické struktury a jejich fyzikální aplikace |
| Investor: Ministry of Education, Youth and Sports of the CR, Mathematical structures and their physical applications | |
| 1M0545, research and development project | Name: Institut Teoretické Informatiky |
| Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science | |
PrintDisplayed: 7/5/2024 05:11