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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Correlation of regularity of two-dimensional and corresponding one-dimensional languages

N. N. Korneeva, L. A. Gizatullina
Mathematics and Theoretical Computer Science
DNA and Biological Computing
article

Correlation of regularity of two-dimensional and corresponding one-dimensional languages

N. N. Korneeva, L. A. Gizatullina
article en

Abstract

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.

Mathematics and Theoretical Computer ScienceVol. 3(2)
Kazan Federal University (RU)
Openalex Percentile: Top 84%
DNA and Biological Computing
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.