Geodesic
A~minimal infinitely based semigroup whose variety is polynomially recognizable
Fundamentalʹnaâ i prikladnaâ matematika, Tome 16 (2010) no. 3, pp. 105-122.

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

We exhibit a six-element semigroup that has no finite identity basis but nevertheless generates a variety whose finite membership problem admits a polynomial algorithm. 
@article{FPM_2010_16_3_a3,
     author = {M. V. Volkov and S. V. Goldberg and S. I. Kublanovsky},
     title = {A~minimal infinitely based semigroup whose variety is polynomially recognizable},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {105--122},
     publisher = {mathdoc},
     volume = {16},
     number = {3},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2010_16_3_a3/}
}
TY  - JOUR
AU  - M. V. Volkov
AU  - S. V. Goldberg
AU  - S. I. Kublanovsky
TI  - A~minimal infinitely based semigroup whose variety is polynomially recognizable
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2010
SP  - 105
EP  - 122
VL  - 16
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/FPM_2010_16_3_a3/
LA  - ru
ID  - FPM_2010_16_3_a3
ER  - 
%0 Journal Article
%A M. V. Volkov
%A S. V. Goldberg
%A S. I. Kublanovsky
%T A~minimal infinitely based semigroup whose variety is polynomially recognizable
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2010
%P 105-122
%V 16
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/FPM_2010_16_3_a3/
%G ru
%F FPM_2010_16_3_a3
M. V. Volkov; S. V. Goldberg; S. I. Kublanovsky. A~minimal infinitely based semigroup whose variety is polynomially recognizable. Fundamentalʹnaâ i prikladnaâ matematika, Tome 16 (2010) no. 3, pp. 105-122. http://geodesic.mathdoc.fr/item/FPM_2010_16_3_a3/

[1] Volkov M. V., “O konechnoi baziruemosti mnogoobrazii polugrupp”, Mat. zametki, 45:3 (1989), 12–23 | MR | Zbl

[2] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR

[3] Kleiman Yu. G., “O bazise proizvedeniya mnogoobrazii grupp”, Izv. AN SSSR. Ser. mat., 37:1 (1973), 95–97 | MR | Zbl

[4] Klifford A., Preston G., Algebraicheskaya teoriya polugrupp, v. 1, Mir, M., 1972 | Zbl

[5] Mashevitskii G. I., “O tozhdestvakh v mnogoobraziyakh vpolne prostykh polugrupp nad abelevymi gruppami”, Sovremennaya algebra, Respublik. sb. nauch. tr., Leningr. gos. ped. in-t, L., 1978, 81–89

[6] Mashevitskii G. I., “Primer konechnoi polugruppy, ne imeyuschei neprivodimogo bazisa tozhdestv v klasse vpolne 0-prostykh polugrupp”, Uspekhi mat. nauk, 38:2 (1983), 211–213 | MR | Zbl

[7] Mashevitskii G. I., “Mnogoobraziya, porozhdënnye vpolne 0-prostymi polugruppami”, Polugruppy i ikh gomomorfizmy, Mezhvuz. sb. nauch. tr., RGPU im. A. I. Gertsena, L., 1991, 53–62 | MR

[8] Ore O., Teoriya grafov, Nauka, M., 1980 | MR

[9] Trakhtman A. N., Grafy tozhdestv odnoi vpolne 0-prostoi pyatielementnoi polugruppy, Dep. v VINITI 07.12.81; No 5558, Ural. politekhn. in-t, Sverdlovsk, 1981

[10] Trakhtman A. N., “Konechnost bazisa tozhdestv pyatielementnykh polugrupp”, Polugruppy i ikh gomomorfizmy, Mezhvuz. sb. nauch. tr., RGPU im. A. I. Gertsena, L., 1991, 76–97 | MR

[11] Shevrin L. N., Volkov M. V., “Tozhdestva polugrupp”, Izv. vyssh. uchebn. zaved. Matematika, 1985, no. 11, 3–47 | MR | Zbl

[12] Bergman C., Slutzki G., “Complexity of some problems concerning varieties and quasi-varieties of algebras”, SIAM J. Comput., 30:2 (2000), 359–382 | DOI | MR | Zbl

[13] Burris S., Sankappanavar H. P., A Course in Universal Algebra, Springer, Berlin, 1981 | MR | Zbl

[14] Eilenberg S., Automata, Languages and Machines, v. B, Academic Press, New York, 1976 | MR | Zbl

[15] Hall T. E., Kublanovskii S. I., Margolis S., Sapir M. V., Trotter P. G., “Algorithmic problems for finite groups and finite 0-simple semigroups”, J. Pure Appl. Algebra, 119:1 (1997), 75–96 | DOI | MR | Zbl

[16] Houghton C. H., “Completely 0-simple semigroups and their associated graphs and groups”, Semigroup Forum, 14:1 (1977), 41–67 | DOI | MR | Zbl

[17] Jackson M., McKenzie R., “Interpreting graph colorability in finite semigroups”, Int. J. Algebra Comput., 16:1 (2006), 119–140 | DOI | MR | Zbl

[18] Kalicki J., “On comparison of finite algebras”, Proc. Amer. Math. Soc., 3:1 (1952), 36–40 | DOI | MR | Zbl

[19] Kharlampovich O. G., Sapir M. V., “Algorithmic problems in varieties”, Int. J. Algebra Comput., 5:4–5 (1995), 379–602 | DOI | MR | Zbl

[20] Klíma O., “Complexity issues of checking identities in finite monoids”, Semigroup Forum, 79:3 (2009), 435–444 | DOI | MR | Zbl

[21] Kozik M., On some complexity problems in finite algebras, Ph. D. Thesis, Vanderbilt Univ., Nashville, 2004 | MR

[22] Kozik M., “Computationally and algebraically complex finite algebra membership problems”, Int. J. Algebra Comput., 17:8 (2007), 1635–1666 | DOI | MR | Zbl

[23] Kozik M., “A 2EXPTIME complete varietal membership problem”, SIAM J. Comput., 38:6 (2009), 2443–2467 | DOI | MR | Zbl

[24] Lee E. W. H., “Identity bases for some non-exact varieties”, Semigroup Forum, 68:3 (2004), 445–457 | DOI | MR | Zbl

[25] Lee E. W. H., Volkov M. V., “On the structure of the lattice of combinatorial Rees–Sishkevich varieties”, Proc. int. conf. “Semigroups and Formal Languages” in honour of the 65th birthday of Donald B. McAlister, World Scientific, New Jersey, 2007, 164–187 | DOI | MR | Zbl

[26] Lee E. W. H., Volkov M. V., “Limit varieties generated by completely 0-simple semigroups” (to appear)

[27] Mashevitsky G. I., “Matrix rank 1 semigroup identities”, Commun. Algebra, 22:9 (1994), 3553–3562 | DOI | MR

[28] Mashevitsky G. I., “The pseudovariety generated by completely 0-simple semigroups”, Semigroup Forum, 54:1 (1997), 83–91 | DOI | MR

[29] Oates S., Powell M. B., “Identical relations in finite groups”, J. Algebra, 1:1 (1964), 11–39 | DOI | MR | Zbl

[30] Papadimitriou C. H., Computational Complexity, Addison-Wesley, Reading, 1994 | MR | Zbl

[31] Perkins P., “Bases for equational theories of semigroups”, J. Algebra, 11:2 (1969), 298–314 | DOI | MR | Zbl

[32] Pollák G., “Arithmetics in free semigroups”, Acta Sci. Math. (Szeged), 68:1–2 (2002), 107–115 | MR | Zbl

[33] Sapir M. V., “On Cross semigroup varieties and related questions”, Semigroup Forum, 42:1 (1991), 345–364 | DOI | MR | Zbl

[34] Seif S., “The Perkins semigroup has co-NP-complete term-equivalence problem”, Int. J. Algebra Comput., 15:2 (2005), 317–326 | DOI | MR | Zbl

[35] Székely Z., “Computational complexity of the finite algebra membership problem for varieties”, Int. J. Algebra Comput., 12:6 (2002), 811–823 | DOI | MR | Zbl

[36] Trahtman A. N., “The finite basis question for semigroups of order less than six”, Semigroup Forum, 27:1–4 (1983), 387–389 | DOI | MR | Zbl

[37] Trahtman A. N., “Identities of a five-element $0$-simple semigroup”, Semigroup Forum, 48:3 (1994), 385–387 | DOI | MR

[38] Volkov M. V., “The finite basis problem for finite semigroups”, Sci. Math. Japon., 53:1 (2001), 171–199 | MR | Zbl