Geodesic
On definability of one-symbol languages in the monoid of finite languages with concatenation
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 4 (2020), pp. 5-13 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider an algebra of all finite languages with the concatenation operation. For one-symbol languages it is known that its theory is equivalent to the first-order arithmetic. Earlier it was proved that for regular languages a one-symbol algebra can be interpreted in multi-symbol algebras. Here we show how to define a one-symbol subalgebra in multi-symbol algebras for finite languages.
Keywords: language, finite language, concatenation, first-order arithmetic. 
@article{VTPMK_2020_4_a0,
     author = {S. M. Dudakov},
     title = {On definability of one-symbol languages in the monoid of finite languages with concatenation},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {5--13},
     year = {2020},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2020_4_a0/}
}
TY  - JOUR
AU  - S. M. Dudakov
TI  - On definability of one-symbol languages in the monoid of finite languages with concatenation
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2020
SP  - 5
EP  - 13
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2020_4_a0/
LA  - ru
ID  - VTPMK_2020_4_a0
ER  - 
%0 Journal Article
%A S. M. Dudakov
%T On definability of one-symbol languages in the monoid of finite languages with concatenation
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2020
%P 5-13
%N 4
%U http://geodesic.mathdoc.fr/item/VTPMK_2020_4_a0/
%G ru
%F VTPMK_2020_4_a0
S. M. Dudakov. On definability of one-symbol languages in the monoid of finite languages with concatenation. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 4 (2020), pp. 5-13. http://geodesic.mathdoc.fr/item/VTPMK_2020_4_a0/

[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)

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

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

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

[5] 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

[6] Dudakov S., Karlov B., “On decidability of theories of regular languages”, Theory of Computing Systems, 2020 | DOI | MR | Zbl

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

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

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