|
This article is cited in 1 scientific paper (total in 1 paper)
Theoretical Foundations of Computer Science
On definability of one-symbol languages in the monoid of finite languages with concatenation
S. M. Dudakov Tver State University, Tver
Abstract:
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.
Received: 08.10.2020 Revised: 20.10.2020
Citation:
S. M. Dudakov, “On definability of one-symbol languages in the monoid of finite languages with concatenation”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2020, no. 4, 5–13
Linking options:
https://www.mathnet.ru/eng/vtpmk601 https://www.mathnet.ru/eng/vtpmk/y2020/i4/p5
|
Statistics & downloads: |
Abstract page: | 206 | Full-text PDF : | 133 | References: | 20 |
|