Markov Properties of Burnside Varieties of Semigroups

V. Yu. Popov

Algebra i logika, Tome 42 (2003) no. 1, pp. 94-106.

Résumé

It is proved that every Markov property of semigroups finitely presented in a variety given by the identity $x^{r_1}=x^{r_2}$, where $r_1>r_2\geqslant 2$, which a one-element semigroup enjoys, is algorithmically non-recognizable.

Détail

Keywords: Burnside variety of semigroups, Markov property, finitely presented semigroup, algorithmic non-recognizability of properties.

Bibliographie

[1] S. I. Adyan, V. G. Durnev, “Algoritmicheskie problemy dlya grupp i polugrupp”, Uspekhi matem. nauk, 55:2 (2000), 3–95 | MR

[2] A. A. Markov, “Teoriya algorifmov”, Trudy matem. in-ta AN SSSR, 42, 1954, 3–375 | MR | Zbl

[3] S. I. Adyan, “Algoritmicheskaya nerazreshimost problem raspoznavaniya nekotorykh svoistv grupp”, Dokl. AN SSSR, 103:4 (1955), 533–535 | MR | Zbl

[4] S. I. Adyan, “Nerazreshimost nekotorykh algoritmicheskikh problem teorii grupp”, Trudy MMO, 6, 1957, 231–298 | MR | Zbl

[5] S. I. Adyan, “Konechno-opredelennye gruppy i algoritmy”, Dokl. AN SSSR, 117:1 (1957), 9–12 | MR | Zbl

[6] S. I. Adyan, “Ob algoritmicheskikh problemakh i effektivno-polnykh klassakh grupp”, Dokl. AN SSSR, 123:1 (1958), 13–16 | MR | Zbl

[7] M. O. Rabin, “Recursive unsolvability of group theoretic problems”, Ann. Math., 67:1 (1958), 172–194 | DOI | MR | Zbl

[8] L. A. Bokut, “Nerazreshimost nekotorykh algoritmicheskikh problem dlya assotsiativnykh kolets”, Algebra i logika, 9:2 (1970), 137–144 | MR | Zbl

[9] L. A. Bokut, “Nerazreshimost nekotorykh algoritmicheskikh problem dlya algebr Li”, Algebra i logika, 13:2 (1974), 145–152 | MR

[10] R. D. Pavlov, “K probleme raspoznavaniya gruppovykh svoistv”, Matem. zametki, 10:2 (1971), 169–180 | MR | Zbl

[11] G. S. Tseitin, “Otnositelno problemy raspoznavaniya svoistv assotsiativnykh ischislenii”, Dokl. AN SSSR, 107:2 (1956), 209–212

[12] J. W. Addison, One some points of the theory of recursive functions, Dissertation, Univ. Wisconsin, 1954

[13] Yu. M. Vazhenin, Ob algoritmicheskoi neraspoznavaemosti markovskikh svoistv dlya nekotorykh klassov polugrupp, Vtoroi Vsesoyuz. simp. teorii polugrupp, Sverdlovsk, 1978, 14

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

[15] W. Burnside, “On an unsettled question in the theory of discontinuous groups”, Q. J. Pure Appl. Math., 33 (1902), 230–237

[16] S. I. Adyan, Problema Bernsaida i tozhdestva v gruppakh, Nauka, M., 1975 | MR | Zbl

[17] M. V. Sapir, “Problemy bernsaidovskogo tipa i konechnaya baziruemost v mnogoobraziyakh polugrupp”, Izv. AN SSSR, ser. matem., 51:2 (1987), 319–340 | Zbl

[18] A. de Luca, S. Varricchio, “On a conjecture of Brown”, Semigroup Forum, 46:1 (1993), 116–119 | DOI | MR | Zbl

[19] V. S. Guba, “The word problem for relatively free Burnside semigroup satisfying $T^m=T^{m+n}$, with $m>4$ or $m=3$, $n=1$”, Int. J. Algebra Comput., 3:2 (1993), 125–140 | DOI | MR | Zbl

[20] V. S. Guba, “The word problem for relatively free semigroup satisfying $T^m=T^{m+n}$, $m\geqslant3$”, Int. J. Algebra Comput., 3:3 (1993), 335–347 | DOI | MR | Zbl

[21] V. Yu. Popov, “Ob ekvatsionalnykh teoriyakh klassov konechnykh polugrupp”, Algebra i logika, 40:1 (2001), 91–116 | MR