2012
Identity checking problem for transformation monoids
KLÍMA, OndřejBasic 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
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
UT WoS
000306590200005
Keywords in English
Checking identities; Finite semigroups; Complexity
Tags
International impact, Reviewed
Changed: 10/4/2013 18:35, Ing. Andrea Mikešková
V originále
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.
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 |
| ||
| MSM0021622409, plan (intention) |
| ||
| 1M0545, research and development project |
|