Complexity of the identity checking problem for finite semigroups

• Tipo: Artigo em Revista Científica Internacional
• Data: 2009

Autores

Almeida, J (Autor) FCUP; Volkov, MV (Autor) Outra; Goldberg, SV (Autor) Outra

Revista

Título: Journal of Mathematical Sciences

Vol. 158

Páginas: 605-614

ISSN: 1072-3374

Editora: Springer Nature

Indexação

ISI Web of Knowledge

Scopus - 12 Citações

Outras Informações

ID Authenticus: P-007-QA2

DOI: 10.1007/s10958-009-9397-z

Abstract (EN): We prove that the identity checking problem in a finite semigroup S is co-NP-complete whenever S has a nonsolvable subgroup or S is the semigroup of all transformations on a 3-element set. Bibliography: 31 titles. © 2009 Springer Science+Business Media, Inc.

Idioma: Inglês

Tipo (Avaliação Docente): Científica