Geodesic
On finite subsets monoid with decidable theory
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 2 (2024), pp. 27-38 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In our previous works, we have proved for various associative algebras that the finite subsets theory allows to interpret elementary arithmetic, in particular, such theory is undecidable. For example, this is proved for all infinite Abelian groups. A natural question arises: can we generalize this result to a wider class of algebras, for example, all commutative monoids. In some cases, we also have proved analogous result: for commutative cancellative monoids with an element of infinite order, or arbitrary Abelian groups. In this paper we prove that this is not true for arbitrary commutative monoids. Moreover, we propose a method that allows to construct such algebras by various original algebras. Also, we have found a limitation of this method.
Keywords: subset algebra, algorithmic decidability, automatic structure. 
@article{VTPMK_2024_2_a2,
     author = {S. M. Dudakov},
     title = {On finite subsets monoid with decidable theory},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {27--38},
     year = {2024},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2024_2_a2/}
}
TY  - JOUR
AU  - S. M. Dudakov
TI  - On finite subsets monoid with decidable theory
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2024
SP  - 27
EP  - 38
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2024_2_a2/
LA  - ru
ID  - VTPMK_2024_2_a2
ER  - 
%0 Journal Article
%A S. M. Dudakov
%T On finite subsets monoid with decidable theory
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2024
%P 27-38
%N 2
%U http://geodesic.mathdoc.fr/item/VTPMK_2024_2_a2/
%G ru
%F VTPMK_2024_2_a2
S. M. Dudakov. On finite subsets monoid with decidable theory. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 2 (2024), pp. 27-38. http://geodesic.mathdoc.fr/item/VTPMK_2024_2_a2/

[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] Blumensath A., Graedel E., “Automatic structures”, Proceedings of 15th IEEE Symposium on Logic in Computer Science LICS 2000, IEEE Computer Society, Los Alamitos, CA, USA, 2000, 51–62 | MR

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

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

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

[6] Dudakov S. M., “On Undecidability of Finite Subsets Theory for Torsion Abelian Groups”, Mathematics, 10:3 (2022), 533 | DOI

[7] Rabin M. O., “Decidability of second-order theories and automata on infinite trees”, Transactions of the American Mathematical Society, 141:7 (1969), 1–35 | MR | Zbl

[8] Tamura T., Shafer J., “Power semigroups”, Mathematicae Japonicae, 12 (1967), 25–32 | MR | Zbl