matatecsМатематика и теоретические компьютерные наукиMathematics and Theoretical Computer Science2949-3919Казанский (Приволжский) федеральный университет10.26907/2949-3919.2025.2.32-57matatecs-77Research ArticleСТАТЬИСвязь регулярности двумерных и соответствующих им одномерных языковCorrelation of regularity of two-dimensional and corresponding one-dimensional languagesКорнееваН. Н.KorneevaN. N.

ул. Кремлевская, д. 18, г. Казань, 420008

18 Kremlyovskaya str., Kazan 420008

,

Natalia.Korneeva@kpfu.ruГизатуллинаЛ. А.GizatullinaL. A.

ул. Кремлевская, д. 18, г. Казань, 420008

18 Kremlyovskaya str., Kazan 420008

glilia99@mail.ruКазанский (Приволжский) федеральный университетРоссияKazan Federal UniversityRussian Federation202526072025323247Copyright © Корнеева Н.Н., Гизатуллина Л.А., 20252025Корнеева Н.Н., Гизатуллина Л.А.Korneeva N.N., Gizatullina L.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://matatecs.elpub.ru/jour/article/view/77

Доказаны соотношения между регулярностью двумерных и одномерных языков. Каждому двумерному языку ставятся в соответствие две последовательности одномерных языков, соответствующие строкам и столбцам двумерного языка. Для каждого из приведенных условий доказано существование как регулярных, так и нерегулярных двумерных языков: все строчные и все столбцовые языки регулярны; все строчные языки регулярны, все столбцовые языки нерегулярны; все столбцовые языки регулярны, все строчные языки нерегулярны; и все строчные, и все столбцовые языки нерегулярны.

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.

регулярный языкдвумерный языкконечный автоматдвумерный онлайн-автомат тесселяцииregular languagetwo-dimensional languagefinite automatontwodimensional on-line tessellation automatonReferencesD. Giammarresi, A. Restivo, Two-dimensional languages, in: G. Rozenberg, A. Salomaa (eds), Handbook of formal languages, Vol. 3, Springer, Berlin, 215–267 (1997). DOI: https://doi.org/10.1007/978-3-642-59126-6_4D. Giammarresi, A. Restivo, Two-dimensional languages, in: G. Rozenberg, A. Salomaa (eds), Handbook of formal languages, Vol. 3, Springer, Berlin, 215–267 (1997). DOI: https://doi.org/10.1007/978-3-642-59126-6_4M. Blum, C. Hewitt, Automata on a 2-dimensional tape, Proceedings of the 8th Annual Symposium on Switching and Automata Theory, IEEE Computer Society, Washington, 155–160 (1967). DOI: https://doi.org/10.1109/FOCS.1967.6M. Blum, C. Hewitt, Automata on a 2-dimensional tape, Proceedings of the 8th Annual Symposium on Switching and Automata Theory, IEEE Computer Society, Washington, 155–160 (1967). DOI: https://doi.org/10.1109/FOCS.1967.6K. Inoue, A. Nakamura, Some properties of two-dimensional on-line tessellation acceptors, Inform. Sci. 13 (2), 95–121 (1977). DOI: https://doi.org/10.1016/0020-0255(77)90023-8K. Inoue, A. Nakamura, Some properties of two-dimensional on-line tessellation acceptors, Inform. Sci. 13 (2), 95–121 (1977). DOI: https://doi.org/10.1016/0020-0255(77)90023-8A. Szepietowski, Two-dimensional on-line tessellation acceptors are not closed under complement, Inform. Sci. 64 (1–2), 115–120 (1992). DOI: https://doi.org/10.1016/0020-0255(92)90114-NA. Szepietowski, Two-dimensional on-line tessellation acceptors are not closed under complement, Inform. Sci. 64 (1–2), 115–120 (1992). DOI: https://doi.org/10.1016/0020-0255(92)90114-NM. Anselmo, D. Giammarresi, M. Madonia, A. Restivo, Unambiguous recognizable twodimensional languages, RAIRO Theor. Inform. Appl. 40 (2), 277–293 (2006). DOI: https://doi.org/10.1051/ita:2006008M. Anselmo, D. Giammarresi, M. Madonia, A. Restivo, Unambiguous recognizable twodimensional languages, RAIRO Theor. Inform. Appl. 40 (2), 277–293 (2006). DOI: https://doi.org/10.1051/ita:2006008N. Vijayaraghavan, N. Jansirani, V.R. Dare, Two dimensional rough online tesselation automaton and its properties, J. Math. Comput. Sci. 11 (3), 3482-3495 (2021). DOI: https://doi.org/10.28919/jmcs/5739N. Vijayaraghavan, N. Jansirani, V.R. Dare, Two dimensional rough online tesselation automaton and its properties, J. Math. Comput. Sci. 11 (3), 3482-3495 (2021). DOI: https://doi.org/10.28919/jmcs/5739D. Giammarresi, A. Restivo, Recognizable picture languages, Int. J. Pattern Recognit. Artif. Intell. 6 (2–3), 241–256 (1992). DOI: https://doi.org/10.1142/S021800149200014XD. Giammarresi, A. Restivo, Recognizable picture languages, Int. J. Pattern Recognit. Artif. Intell. 6 (2–3), 241–256 (1992). DOI: https://doi.org/10.1142/S021800149200014XK. Inoue, I. Takanami, A characterization of recognizable picture, Int. J. Pattern Recognit. Artif. Intell. 8 (2), 501–508 (1994). DOI: https://doi.org/10.1142/S0218001494000255K. Inoue, I. Takanami, A characterization of recognizable picture, Int. J. Pattern Recognit. Artif. Intell. 8 (2), 501–508 (1994). DOI: https://doi.org/10.1142/S0218001494000255S. Eilenberg, Automata, languages and machines, Vol. A, in: Pure Appl. Math. 58, New York, Academic Press, 1974.S. Eilenberg, Automata, languages and machines, Vol. A, in: Pure Appl. Math. 58, Academic Press, New York, 1974.D. Giammarresi, A. Restivo, S. Seibert, W. Thomas, Monadic second order logic over rectangular pictures and recognizability by tiling systems, Inform. and Comput. 125 (1), 32–45 (1996). DOI: https://doi.org/10.1006/inco.1996.0018D. Giammarresi, A. Restivo, S. Seibert, W. Thomas, Monadic second order logic over rectangular pictures and recognizability by tiling systems, Inform. and Comput. 125 (1), 32–45 (1996). DOI: https://doi.org/10.1006/inco.1996.0018J.R. Bu¨chi, Weak second-order arithmetic and fi automata, Z. Math. Logik Grundlagen Math. 6, 66–92 (1960). DOI: https://doi.org/10.1002/malq.19600060105J.R. Bu¨chi, Weak second-order arithmetic and arithmetic and finite automata, Z. Math. Logik Grundlagen Math. 6, 66–92 (1960). DOI: https://doi.org/10.1002/malq.19600060105K. Inoue, I. Takanami, A. Nakamura, A note on two-dimensional fi automata, Information Processing Lett. 7 (1), 49–52 (1978). DOI: https://doi.org/10.1016/0020-0190(78)90040-6K. Inoue, I. Takanami, A. Nakamura, A note on two-dimensional finite automata, Information Processing Lett. 7 (1), 49–52 (1978). DOI: https://doi.org/10.1016/0020-0190(78)90040-6Д. Хопкрофт, Р. Мотвани, Дж. Ульман, Введение в теорию автоматов, языков и вычислений, Издательский дом “Вильямс”, М., 2008.J.E. Hopcroft, R. Motwani, J.D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley, MA, 2001.K. Inoue, A. Nakamura, Nonclosure properties of two-dimensional on-line tessellation acceptors and one way parallel sequential array acceptors, Proc. IECE of Japan Trans. (E) 60 (9), 475–476 (1977).K. Inoue, A. Nakamura, Nonclosure properties of two-dimensional on-line tessellation acceptors and one way parallel sequential array acceptors, Proc. IECE of Japan Trans. (E) 60 (9), 475–476 (1977).

The authors declare that there are no conflicts of interest present.