J 2009

Complexity issues of checking identities in finite monoids

KLÍMA, Ondřej

Základní údaje

Originální název

Complexity issues of checking identities in finite monoids

Název česky

Složitost kontroly identit v konečných monoidech

Autoři

KLÍMA, Ondřej (203 Česká republika, garant)

Vydání

Semigroup Forum, Springer-Verlag, 2009, 0037-1912

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10101 Pure mathematics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.597

Kód RIV

RIV/00216224:14310/09:00029605

Organizační jednotka

Přírodovědecká fakulta

UT WoS

000271737700002

Klíčová slova anglicky

Checking identities Finite semigroups Complexity

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 30. 3. 2010 14:01, doc. Mgr. Ondřej Klíma, Ph.D.

Anotace

ORIG CZ

V originále

We study the computational complexity of checking identities in a fixed finite monoid. We find the smallest monoid for which this problem is coNPcomplete and describe a significant class of finite monoids for which the problem is tractable.

Česky

Studujeme výpočetní složitost problému kontroly identit v pevně daném konečném monoidu. Nalezli jsme nejmenší monoid pro který je tento problém coNPúplný a popsali zásadní třídu konečných monoidů pro které je problém efektivně řešitelný.

Návaznosti

GA201/06/0936, projekt VaV
Název: Algebraické metody v teorii automatů a formálních jazyků
Investor: Grantová agentura ČR, Algebraické metody v teorii automatů a formálních jazyků
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