J 2012

Identity checking problem for transformation monoids

KLÍMA, Ondřej

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

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

UT WoS

000306590200005

Klíčová slova anglicky

Checking identities; Finite semigroups; Complexity

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 10. 4. 2013 18:35, Ing. Andrea Mikešková

Anotace

ORIG CZ

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.

Č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