ISSN: 2310-757X
Please use this identifier to cite or link to this item:
http://elar.urfu.ru/handle/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://elar.urfu.ru/handle/10995/111987 |
| Access: | info:eu-repo/semantics/openAccess |
| SCOPUS ID: | 67349207363 |
| PURE ID: | 7881627 |
| 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 | Size | Format | |
|---|---|---|---|---|
| 2-s2.0-67349207363.pdf | 233,54 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.