Mathematical Logic, Algebra, Number Theory and Discrete Mathematics

On decidable and undecidable theories of languages

B. N. Karlov

Tver State University, Tver

Abstract: 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.

UDC: 510.65

Received: 01.12.2024
Revised: 16.12.2024

DOI: 10.26456/vtpmk725

Bibliographic databases:

•