Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

On the computation of the span of regular languages under alphabetic coding

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
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover