Mathematical Logic, Algebra, Number Theory and Discrete Mathematics

Definability of sets in theories of languages with union and Kleene star

B. N. Karlov

Tver State University, Tver

Abstract: In this paper we study theories of languages in different alphabets with the operations of union and Kleene star. We prove that in the case of one-symbol alphabet such theory allows to define the power operation on singleton languages for an arbitrary fixed exponent. As corollary we establish definability of all finite and cofinite languages. It is proved that in the case of multi-symbol alphabets some finite languages are undefinable. It is established that independently on the alphabet some non-context-free languages are definable.

Keywords: formal language, theory, union, Kleene star, definability.

UDC: 510.67, 519.766

Received: 30.05.2025
Revised: 24.06.2025

DOI: 10.26456/vtpmk734

Bibliographic databases:

•