On the computation of the span of regular languages under alphabetic coding
Received: 02 Nov 2026 Revised: 03 Nov 2026 Accepted: 04 Nov 2026
Published: 2026, vol. 30, issue 4, pp. 258–261
Abstract
In this paper, we introduce and study the concept of the span of regular languages under alphabetic coding. The main result is a previously unknown dichotomy property of unit and infinite spans for languages of a special iteration-concatenation form in the case of a two-element input alphabet. It is also shown how, based on these results, one can construct an algorithm for computing the span in the general case for such an alphabet (the algorithmic decidability of this computation itself is a known fact).
Keywords: regular language, alphabetic coding, span.
BibTeX
@article{IS-Dergach2026,
author = {Dergach, Peter Sergeevich},
title = {{On the computation of the span of regular languages under alphabetic coding}},
journal = {Intelligent Systems. Theory and Applications},
year = {2026},
volume = {30},
number = {4},
pages = {258--261},
}
AMSBIB
\Bibitem{IS-Dergach2026}
\by P.\,S.~Dergach
\paper On the computation of the span of regular languages under alphabetic coding
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 258--261
\lang In Russian
RU