J 2009

Complexity issues of checking identities in finite monoids

KLÍMA, Ondřej

Basic information

Original name

Complexity issues of checking identities in finite monoids

Name in Czech

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

Authors

KLÍMA, Ondřej (203 Czech Republic, guarantor)

Edition

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

Other information

Language

English

Type of outcome

Article in a journal

Field of Study

10101 Pure mathematics

Country of publisher

Germany

Confidentiality degree

is not subject to a state or trade secret

Impact factor

Impact factor: 0.597

RIV identification code

RIV/00216224:14310/09:00029605

Organization unit

Faculty of Science

UT WoS

000271737700002

Keywords in English

Checking identities Finite semigroups Complexity

Tags

International impact, Reviewed
Changed: 30/3/2010 14:01, doc. Mgr. Ondřej Klíma, Ph.D.

Abstract

ORIG CZ

In the original language

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.

In Czech

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ý.

Links

GA201/06/0936, research and development project
Name: Algebraické metody v teorii automatů a formálních jazyků
Investor: Czech Science Foundation, Algebraic Methods in Automata and Formal Language Theory
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