Geodesic
Complexity of the identity checking problem for finite semigroups
Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 5-22

Voir la notice de l'article provenant de la source Math-Net.Ru

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. Bibl. – 31 titles. 
@article{ZNSL_2008_358_a0,
     author = {J. Almeida and M. V. Volkov and S. V. Gol'dberg},
     title = {Complexity of the identity checking problem for finite semigroups},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {5--22},
     publisher = {mathdoc},
     volume = {358},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a0/}
}
TY  - JOUR
AU  - J. Almeida
AU  - M. V. Volkov
AU  - S. V. Gol'dberg
TI  - Complexity of the identity checking problem for finite semigroups
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2008
SP  - 5
EP  - 22
VL  - 358
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a0/
LA  - ru
ID  - ZNSL_2008_358_a0
ER  - 
%0 Journal Article
%A J. Almeida
%A M. V. Volkov
%A S. V. Gol'dberg
%T Complexity of the identity checking problem for finite semigroups
%J Zapiski Nauchnykh Seminarov POMI
%D 2008
%P 5-22
%V 358
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a0/
%G ru
%F ZNSL_2008_358_a0
J. Almeida; M. V. Volkov; S. V. Gol'dberg. Complexity of the identity checking problem for finite semigroups. Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part XI, Tome 358 (2008), pp. 5-22. http://geodesic.mathdoc.fr/item/ZNSL_2008_358_a0/