Correlation of regularity of two-dimensional and corresponding one-dimensional languages
https://doi.org/10.26907/2949-3919.2025.2.32-57
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.
About the Authors
N. N. Korneeva
Kazan Federal University
Russian Federation
Natalia Nikolaevna Korneeva
Russian Federation
Natalia Nikolaevna Korneeva
18 Kremlyovskaya str., Kazan 420008
,
L. A. Gizatullina
Kazan Federal University
Russian Federation
Liliya Albirusovna Gizatullina
Russian Federation
Liliya Albirusovna Gizatullina
18 Kremlyovskaya str., Kazan 420008
References
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, Academic Press, New York, 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 arithmetic and finite 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 finite automata, Information Processing Lett. 7 (1), 49–52 (1978). DOI: https://doi.org/10.1016/0020-0190(78)90040-6
13. J.E. Hopcroft, R. Motwani, J.D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley, MA, 2001.
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).
Review
For citations:
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
Views:
117
Email this article 