Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111987
Title: Complexity of the Identity Checking Problem for Finite Semigroups
Authors: Almeida, J.
Volkov, M. V.
Goldberg, S. V.
Issue Date: 2009
Publisher: Springer Science and Business Media LLC
Citation: Almeida J. Complexity of the Identity Checking Problem for Finite Semigroups / J. Almeida, M. V. Volkov, S. V. Goldberg // Journal of Mathematical Sciences. — 2009. — Vol. 158. — Iss. 5. — P. 605-614.
Abstract: 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.
URI: http://hdl.handle.net/10995/111987
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 67349207363
ISSN: 1072-3374
metadata.dc.description.sponsorship: The first author acknowledges the support of the Centro de Matematica da Universidade do Porto, financed by FCT through the programmes POCTI and POSI, with Portuguese and European Community structural funds, as well as the support of the FCT project PTDC/MAT/65481/2006. The second and the third authors were supported by the Russian Foundation for Basic Research, grant 05-01-00540.
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-67349207363.pdf233,54 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.