Связь регулярности двумерных и соответствующих им одномерных языков
https://doi.org/10.26907/2949-3919.2025.2.32-57
Аннотация
Доказаны соотношения между регулярностью двумерных и одномерных языков. Каждому двумерному языку ставятся в соответствие две последовательности одномерных языков, соответствующие строкам и столбцам двумерного языка. Для каждого из приведенных условий доказано существование как регулярных, так и нерегулярных двумерных языков: все строчные и все столбцовые языки регулярны; все строчные языки регулярны, все столбцовые языки нерегулярны; все столбцовые языки регулярны, все строчные языки нерегулярны; и все строчные, и все столбцовые языки нерегулярны.
Ключевые слова
Об авторах
Н. Н. Корнеева
Казанский (Приволжский) федеральный университет
Россия
Наталья Николаевна Корнеева
Россия
Наталья Николаевна Корнеева
ул. Кремлевская, д. 18, г. Казань, 420008
Л. А. Гизатуллина
Казанский (Приволжский) федеральный университет
Россия
Лилия Альбирусовна Гизатуллина
Россия
Лилия Альбирусовна Гизатуллина
ул. Кремлевская, д. 18, г. Казань, 420008
Список литературы
1. D. 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_4
2. M. 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.6
3. K. 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-8
4. A. 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-N
5. M. 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:2006008
6. N. 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/5739
7. D. Giammarresi, A. Restivo, Recognizable picture languages, Int. J. Pattern Recognit. Artif. Intell. 6 (2–3), 241–256 (1992). DOI: https://doi.org/10.1142/S021800149200014X
8. K. 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/S0218001494000255
9. S. Eilenberg, Automata, languages and machines, Vol. A, in: Pure Appl. Math. 58, New York, Academic Press, 1974.
10. 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.0018
11. J.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.19600060105
12. K. 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-6
13. Д. Хопкрофт, Р. Мотвани, Дж. Ульман, Введение в теорию автоматов, языков и вычислений, Издательский дом “Вильямс”, М., 2008.
14. 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).
Рецензия
Для цитирования:
Корнеева Н.Н., Гизатуллина Л.А. Связь регулярности двумерных и соответствующих им одномерных языков. Математика и теоретические компьютерные науки. 2025;3(2):32-47. https://doi.org/10.26907/2949-3919.2025.2.32-57
For citation:
Korneeva N.N., Gizatullina L.A. Correlation of regularity of two-dimensional and corresponding one-dimensional languages. Mathematics and Theoretical Computer Science. 2025;3(2):32-47. (In Russ.) https://doi.org/10.26907/2949-3919.2025.2.32-57
Просмотров:
51
Послать статью по эл. почте 