Correlation of regularity of two-dimensional and corresponding one-dimensional languages
We prove relations between regularity of two-dimensional and one-dimensional languages. Each two-dimensional language is corresponded to two sequences of one-dimensional languages corresponding to rows and columns of the two-dimensional language. For each of the following conditions the existence of both regular and nonregular two-dimensional languages is proved: all row and all column languages are regular; all row languages are regular, all column languages are nonregular; all column languages are regular, all row languages are nonregular; both all row and all column languages are nonregular.
Authors
- N. N. Korneeva (ORCID: https://orcid.org/0000-0002-0161-806X)
- L. A. Gizatullina
Institutions
- Kazan Federal University (RU)
Publication Details
- Journal
- Mathematics and Theoretical Computer Science
- Published
- 2025-07-26
- DOI
- https://doi.org/10.26907/2949-3919.2025.2.32-57
- Primary Topic
- DNA and Biological Computing
- Type
- article
- Field-Weighted Citation Impact
- 0.00