Geodesic
On decidable and undecidable theories of languages
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 4 (2024), pp. 30-39
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper we study some theories of languages with different operations. We prove the decidability of such theories with the operations of complement, reversal, and cyclic shift, and also the decidability of some fragments of concatenation theory when one of the languages is fixed. We establish the undecidability of the theory of orthogonal concatenation.
Keywords: formal language, theory, decidability, unar, orthogonal concatenation. 
@article{VTPMK_2024_4_a2,
     author = {B. N. Karlov},
     title = {On decidable and undecidable theories of languages},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {30--39},
     year = {2024},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2024_4_a2/}
}
TY  - JOUR
AU  - B. N. Karlov
TI  - On decidable and undecidable theories of languages
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2024
SP  - 30
EP  - 39
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2024_4_a2/
LA  - ru
ID  - VTPMK_2024_4_a2
ER  - 
%0 Journal Article
%A B. N. Karlov
%T On decidable and undecidable theories of languages
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2024
%P 30-39
%N 4
%U http://geodesic.mathdoc.fr/item/VTPMK_2024_4_a2/
%G ru
%F VTPMK_2024_4_a2
B. N. Karlov. On decidable and undecidable theories of languages. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 4 (2024), pp. 30-39. http://geodesic.mathdoc.fr/item/VTPMK_2024_4_a2/

[1] Karlov B. N., “On elementary equivalence of some unoids and unoids of their subsets”, Herald of Tver State University. Series: Applied Mathematics, 2021, no. 3, 18–32 (in Russian) | DOI | MR

[2] Karlov B. N., “On undecidability of subset theories of some unars”, Doklady Mathematics, 109:2 (2024), 112–116 | DOI | DOI | MR | Zbl

[3] Karlov B. N., “On the theory of concatenation of one class of languages”, Proceedings of the international conference “Algebra and Mathematical Logic: Theory and Applications”, KFU, Kazan, 2024, 206–207 (in Russian)

[4] Anselmo M., Restivo A., “On languages factorizing the free monoid”, International Journal of Algebra and Computation, 6:4 (1996), 413–427 | DOI | MR | Zbl

[5] Daley M., Domaratzki M., Salomaa K., “Orthogonal concatenation: language equations and state complexity”, Journal of Universal Computer Science, 16:5 (2010), 653–675 | DOI | MR | Zbl

[6] Dudakov S. M., “On undecidability of concatenation theory for one-symbol languages”, Lobachevskii Journal of Mathematics, 41:2 (2020), 168–175 | DOI | 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] Monk J. D., Mathematical logic, Springer-Verlag, New York, Heidelberg, Berlin, 1976, 542 pp. | MR | Zbl