Geodesic
On theory of finite subsets monoid for one torsion abelian group
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 2 (2021), pp. 39-55 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Earlier it was proved the following claim. Let G be a non-torsion abelian group and G be the semigroup of finite subsets of G. Then elementary arithmetic can be interpreted in $G^*$, so the theory of $G^*$ is undecidable. Here we prove the same result for one torsion group, the multiplicative group of all roots of unity.
Mots-clés : torsion group
Keywords: semigroup of subsets, elementary arithmetic, undecidability. 
@article{VTPMK_2021_2_a3,
     author = {S. M. Dudakov},
     title = {On theory of finite subsets monoid for one torsion abelian group},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {39--55},
     year = {2021},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2021_2_a3/}
}
TY  - JOUR
AU  - S. M. Dudakov
TI  - On theory of finite subsets monoid for one torsion abelian group
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2021
SP  - 39
EP  - 55
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2021_2_a3/
LA  - ru
ID  - VTPMK_2021_2_a3
ER  - 
%0 Journal Article
%A S. M. Dudakov
%T On theory of finite subsets monoid for one torsion abelian group
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2021
%P 39-55
%N 2
%U http://geodesic.mathdoc.fr/item/VTPMK_2021_2_a3/
%G ru
%F VTPMK_2021_2_a3
S. M. Dudakov. On theory of finite subsets monoid for one torsion abelian group. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 2 (2021), pp. 39-55. http://geodesic.mathdoc.fr/item/VTPMK_2021_2_a3/

[1] Dudakov S. M., “On algorithmic properties of finite subset algebra for some unoids”, Herald of Tver State University. Series: Applied Mathematics, 2019, no. 4, 108–116 (in Russian) | DOI

[2] Dudakov S. M., “On definability of one-symbol languages in the monoid of finite languages with concatenation”, Herald of Tver State University. Series: Applied Mathematics, 2020, no. 4, 5–13 (in Russian) | DOI

[3] Boolos G. S., Burgess J. P., Jeffrey R. C., Computability and Logic, 5th edition, Cambridge University Press, New York, 2007, 364 pp. | MR | Zbl

[4] Codd E. F., “Relational completeness of data base sublanguages”, Database Systems, ed. R. Rustin, Prentice-Hall, 1972, 33–64

[5] Dudakov S. M., “On undecidability of concatenation theory for one-symbol languages”, Lobachevskii Journal of Mathematics, 40:2 (2020), 168–175 | DOI | MR

[6] Dudakov S. M., Karlov B. N., “On Decidability of Regular Languages Theories”, Proc. of 14th International Computer Science Symposium in Russia, CSR 2019, v. 11532, LNCS, 2019, 119–130 | MR | Zbl

[7] Dudakov S., Karlov B., “On decidability of theories of regular languages”, Theory of Computing Systems, 65 (2021), 462–478 | DOI | MR | Zbl

[8] Dudakov S. M., “On Undecidability of Subset Theory for Some Monoids”, Journal of Physics: Conference Series, 1902:1 (2021), 012060 | DOI

[9] Hopcroft J. E., Motwani R., Ullman J. D., Introduction to Automata Theory, Languages, and Computation, Pearson, Harlow, 2013, 560 pp. | MR

[10] Kanellakis P., Kuper G., Revesz P., “Constraint query languages”, Journal of Computer and System Sciences, 51 (1995), 26–52 | DOI | MR

[11] Mostowski A., “On direct products of theories”, The Journal of Symbolic Logic, 17:3 (1952), 1–31 | DOI | MR | Zbl

[12] Rogers H., Theory of Recursive Functions and Effective Computability, MIT Press, Cambridge, 1987, 506 pp. | MR