Geodesic
Finitely presented expansions of computably enumerable semigroups
Algebra i logika, Tome 51 (2012) no. 5, pp. 652-667.

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

Every computable universal algebra has a finitely presented expansion. On the other hand, there are examples of finitely generated, computably enumerable universal algebras with no finitely presented expansions. It is natural to ask whether such examples can be found in well-known classes of algebras such as groups and semigroups. Here we build an example of a finitely generated, infinite, computably enumerable semigroup with no finitely presented expansions.We also discuss other interesting computability-theoretic properties of this semigroup.
Keywords: computably enumerable semigroup, finitely presented expansion. 
@article{AL_2012_51_5_a5,
     author = {D. R. Hirschfeldt and B. Khoussainov},
     title = {Finitely presented expansions of computably enumerable semigroups},
     journal = {Algebra i logika},
     pages = {652--667},
     publisher = {mathdoc},
     volume = {51},
     number = {5},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2012_51_5_a5/}
}
TY  - JOUR
AU  - D. R. Hirschfeldt
AU  - B. Khoussainov
TI  - Finitely presented expansions of computably enumerable semigroups
JO  - Algebra i logika
PY  - 2012
SP  - 652
EP  - 667
VL  - 51
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2012_51_5_a5/
LA  - ru
ID  - AL_2012_51_5_a5
ER  - 
%0 Journal Article
%A D. R. Hirschfeldt
%A B. Khoussainov
%T Finitely presented expansions of computably enumerable semigroups
%J Algebra i logika
%D 2012
%P 652-667
%V 51
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2012_51_5_a5/
%G ru
%F AL_2012_51_5_a5
D. R. Hirschfeldt; B. Khoussainov. Finitely presented expansions of computably enumerable semigroups. Algebra i logika, Tome 51 (2012) no. 5, pp. 652-667. http://geodesic.mathdoc.fr/item/AL_2012_51_5_a5/

[1] J. A. Bergstra, J. V. Tucker, “Initial and final algebra semantics for data type specifications: two characterization theorems”, SIAM J. Comput., 12 (1983), 366–387 | DOI | MR | Zbl

[2] J. A. Bergstra, J. V. Tucker, “Algebraic specifications of computable and semicomputable data types”, Theoret. Comput. Sci., 50 (1987), 137–181 | DOI | MR | Zbl

[3] Yu. L. Ershov, S. S. Goncharov (red.), Logicheskaya tetrad, Nereshennye voprosy matematicheskoi logiki (operativnyi informatsionnyi material), In-t matem. SO AN SSSR, Novosibirsk, 1986 | MR

[4] G. Grätzer, Universal Algebra, revised reprint of the 2nd ed., Springer-Verlag, New York, 2008 | MR

[5] Yu. L. Ershov, S. S. Goncharov, A. Nerode, J. B. Remmel, V. W. Marek (eds.), Handbook of recursive mathematics, v. 1, Stud. Log. Found. Math., 138, Recursive model theory, Elsevier, Amsterdam, 1998 | MR

[6] A. I. Maltsev, “Konstruktivnye algebry. 1”, UMN, 16:3 (1961), 3–60 | MR | Zbl

[7] N. Kh. Kasymov, “Algebry s finitno-approksimiruemymi pozitivno predstavimymi obogascheniyami”, Algebra i logika, 26:6 (1987), 715–730 | MR | Zbl

[8] B. Khoussainov, “Randomness, computability, and algebraic specifications”, Ann. Pure Appl. Logic, 91:1 (1998), 1–15 | DOI | MR | Zbl

[9] B. Khoussainov, A. Miasnikov, On finitely presented expansions of algebras and groups, in preparation

[10] E. S. Golod, I. R. Shafarevich, “O bashne polei klassov”, Izv. AN SSSR, cer. matem., 28:2 (1964), 261–272 | MR | Zbl

[11] D. Cenzer, S. A. Dashti, J. L. F. King, “Computable symbolic dynamics”, Math. Log. Q., 54:5 (2008), 460–469 | DOI | MR | Zbl

[12] J. S. Miller, “Two notes on subshifts”, Proc. Am. Math. Soc., 140:5 (2012), 1617–1622 | MR

[13] R. I. Soare, Recursively enumerable sets and degrees, Perspect. Math. Log., Omega Series, Springer-Verlag, Heidelberg a.o., 1987 ; R. I. Soar, Vychislimo perechislimye mnozhestva i stepeni, Kazanskoe matem. ob-vo, Kazan, 2000 | MR | MR | Zbl

[14] I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain, “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264:2 (2003), 665–694 | DOI | MR | Zbl