|
|
|
|
References
|
|
| |
| 1. |
M. Geri, D. Dzhonson, Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982  |
| 2. |
M. I. Kargapolov, Yu. I. Merzlyakov, Osnovy teorii grupp, Nauka, M., 1972  |
| 3. |
R. Lindon, P. Shupp, Kombinatornaya teoriya grupp, Mir, M., 1980 |
| 4. |
S. V. Plescheva, V. Verteshi, “Slozhnost zadachi proverki tozhdestv v 0-prostoi polugruppe”, Izv. Ural. gos. un-ta, 2006, no. 43, Kompyuternye nauki informatsionnye tekhnologii, Vyp. 1, 72–102 |
| 5. |
E. P. Simelgor, “Tozhdestva v konechnoi simmetricheskoi polugruppe”, Sovremen. algebra, 1974, no. 1, 174–188 |
| 6. |
J. Almeida, S. V. Plescheva, M. V. Volkov, “An application of group generic implicit operators to
the complexity of identity checking in finite semigroups”, Mezhdunar. algebraich. konf., posvyaschennaya stoletiyu so dnya
rozhdeniya P. G. Kontorovicha i 70-letiyu L. N. Shevrina, Tez. dokl., Izd-vo Ural. un-ta, Ekaterinburg, 2005, 16–17 |
| 7. |
J. Almeida, M. V. Volkov, “Subword complexity of profinite words and subgroups of free profinite
semigroups”, Int. J. Algebra and Computation, 16:2 (2006), 221–258  |
| 8. |
C. Bergman, G. Slutzki, “Complexity of some problems concerning varieties and quasi-varieties
of algebras”, SIAM J. Comput., 30:2 (2000), 359–382 |
| 9. |
S. Burris, J. Lawrence, “The equivalence problem for finite rings”, J. Symbolic Computation, 15:1 (1993), 67–71 |
| 10. |
S. Burris, J. Lawrence, “Results on the equivalence problem for finite groups”, Algebra Universalis, 52:4 (2005), 495–500 |
| 11. |
C. C. Edmunds, “On certain finitely based varieties of semigroups”, Semigroup Forum, 15:1 (1977), 21–39 |
| 12. |
G. Horváth, J. Lawrence, L. Mérai, Cs. Szabó, “The complexity of the equivalence problem for nonsolvable groups”, Bull. London Math. Soc., 39:3 (2007), 433–438 |
| 13. |
G. Horváth, Cs. Szabó, “The complexity of checking identities over finite groups”, Int. J. Algebra and Computation, 16:5 (2006), 931–939 |
| 14. |
H. B. Hunt III, R. E. Stearns, “The complexity of equivalence for commutative rings”, J. Symbolic Computation, 10:5 (1990), 411–436 |
| 15. |
M. Jackson, R. McKenzie, “Interpreting graph colorability in finite semigroups”, Int. J. Algebra and Computation, 16:1 (2006), 119–140 |
| 16. |
J. Kalicki, “On comparison of finite algebras”, Proc. Amer. Math. Soc., 3:1 (1952), 36–40 |
| 17. |
O. G. Kharlampovich, M. V. Sapir, “Algorithmic problems in varieties”, Int. J. Algebra and Computation, 5:4–5 (1995), 379–602 |
| 18. |
A. Kisielewicz, “Complexity of semigroup identity checking”, Int. J. Algebra and Computation, 14:4 (2004), 455–464 |
| 19. |
O. Klíma, “Complexity issues of checking identities in finite monoids”, Semigroup Forum (to appear) |
| 20. |
M. Kozik, On Some Complexity Problems in Finite Algebras, PhD Dissertation, Vanderbilt University, Nashville, 2004 |
| 21. |
M. Kozik, “Computationally and algebraically complex finite algebra membership
problems”, Int. J. Algebra and Computation, 17:8 (2007), 1635–1666 |
| 22. |
M. Kozik, “Varietal membership problem is 2-EXPTIME complete” (to appear) |
| 23. |
C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, Reading–Menlo Park–New York, 1994 |
| 24. |
J.-E. Pin, Varieties of Formal Languages, North Oxford Academic, Oxford; Plenum, New York, 1986 |
| 25. |
S. Seif, “The Perkins semigroup has co-NP-complete term-equivalence problem”, Int. J. Algebra and Computation, 15:2 (2005), 317–326  |
| 26. |
S. Seif, Cs. Szabó, “Computational complexity of checking identities in 0-simple semigroups
and matrix semigroups over finite fields”, Semigroup Forum, 72:2 (2006), 207–222 |
| 27. |
Cs. Szabó, V. Vértesi, “The complexity of the word-problem for finite matrix rings”, Proc. Amer. Math. Soc., 132:12 (2004), 3689–3695 |
| 28. |
Cs. Szabó, V. Vértesi, “The complexity of checking identities for finite matrix rings”, Algebra Universalis, 51:4 (2004), 439–445 |
| 29. |
Cs. Szabó, V. Vértesi, “The identity checking problem in finite rings” (to appear) |
| 30. |
Z. Székely, “Computational complexity of the finite algebra membership problem
for varieties”, Int. J. Algebra and Computation, 12:6 (2002), 811–823 |
| 31. |
P. Tesson, Computational Complexity Questions Related to Finite Monoids
and Semigroups, PhD Thesis, McGill University, Montréal, 2003 |
