In this paper, we put forward models that generate two-dimensional palindromic languages with array-rewriting rules. The rewriting rules are of either regular or context-free type with terminals being arrays. The derivation lengths are managed by the array concatenation conditions. These grammars give rise to an extensive variety of palindromic pictures. Different hierarchies that exist between the classes defined are demonstrated. The closure properties have also been evaluated. Applications of these models have been explored by generating a few patterns of kolams.
Citation: Hannah Blasiyus, D. K. Sheena Christy. Two-dimensional array grammars in palindromic languages[J]. AIMS Mathematics, 2024, 9(7): 17305-17318. doi: 10.3934/math.2024841
In this paper, we put forward models that generate two-dimensional palindromic languages with array-rewriting rules. The rewriting rules are of either regular or context-free type with terminals being arrays. The derivation lengths are managed by the array concatenation conditions. These grammars give rise to an extensive variety of palindromic pictures. Different hierarchies that exist between the classes defined are demonstrated. The closure properties have also been evaluated. Applications of these models have been explored by generating a few patterns of kolams.
| [1] | A. Thue, Über unendliche zeichenreihen, Norske Vid Selsk. Skr. I Mat-Nat Kl., 7 (1906), 1–22. |
| [2] | T. Nagell, A. Selberg, S. Selberg, K. Thalberg, Selected mathematical papers of Axel Thue, Universitetsforlaget, 1977. |
| [3] | M. Lothaire, Combinatorics on words, Addison-Wesley, 2 Eds., 1983. https://doi.org/10.1017/CBO9780511566097 |
| [4] |
L. Kari, K. Mahalingam, Involutively bordered words, Int. J. Found. Comput. Sci., 18 (2022), 1089–1106. https://doi.org/10.1142/S0129054107005145 doi: 10.1142/S0129054107005145
|
| [5] |
E. Czeizler, L. Kari, S. Seki, On a special class of primitive words, Theor. Comput. Sci., 411 (2010), 617–630. https://doi.org/10.1016/j.tcs.2009.09.037 doi: 10.1016/j.tcs.2009.09.037
|
| [6] | S. S. Yu, Languages and codes, Department of Computer Science, National Chung-Hsing University, Taichung, 2005. |
| [7] | A. Rosenfeld, Picture languages, formal models for picture recognition, Academic Press, 1979. https://doi.org/10.1016/C2013-0-11407-9 |
| [8] |
R. Narasimhan, Labeling schemata and syntactic description of pictures, Inf. Control, 7 (1964), 151–179. https://doi.org/10.1016/S0019-9958(64)90087-7 doi: 10.1016/S0019-9958(64)90087-7
|
| [9] |
G. Siromoney, R. Siromoney, K. Krithivasan, Abstract families of matrices and picture languages, Comput. Graph. Image Process., 1 (1972), 284–307. https://doi.org/10.1016/S0146-664X(72)80019-4 doi: 10.1016/S0146-664X(72)80019-4
|
| [10] |
G. Siromoney, R. Siromoney, K. Krithivasan, Picture languages with array rewriting rules, Inf. Control, 20 (1973), 447–470. https://doi.org/10.1016/S0019-9958(73)90573-1 doi: 10.1016/S0019-9958(73)90573-1
|
| [11] |
R. Siromoney, K. Krithivasan, G. Siromoney, N-dimensional array languages and description of crystal symmetry-Ⅰ, Proc. Indian Acad. Sci., 78 (1973), 72–88. https://doi.org/10.1007/BF03049472 doi: 10.1007/BF03049472
|
| [12] | M. Tomita, Parsing 2-dimensional language, Carnegy Mellon University, 1989,414–424. |
| [13] |
A. Amir, G. Benson, Two-dimensional periodicity in rectangular arrays, SIAM J. Comput., 27 (1998), 90–106. https://doi.org/10.1137/S0097539795298321 doi: 10.1137/S0097539795298321
|
| [14] | M. Kulkarni, K. Mahalingam, Two-dimensional palindromes and their properties, In: F. Drewes, C. Martín-Vide, B. Truthe, Language and automata theory and applications, Springer, 2017,155–167. https://doi.org/10.1007/978-3-319-53733-7_11 |
| [15] | K. Mahalingam, P. Pandoh, On the maximum number of distinct palindromic sub-arrays, In: C. Martín-Vide, A. Okhotin, D. Shapira, Language and automata theory and applications, Springer, 2019,434–446. https://doi.org/10.1007/978-3-030-13435-8 |
| [16] |
K. Mahalingam, P. Pandoh, K. Krithivasan, On the least number of palindromes in two-dimensional words, Theor. Comput. Sci., 807 (2020), 246–256. https://doi.org/10.1016/j.tcs.2019.06.030 doi: 10.1016/j.tcs.2019.06.030
|
| [17] | K. Mahalingam, M. Sivasankar, K. Krithivasan, Palindromic properties of two-dimensional Fibonacci words, Romanian J. Inf. Sci. Technol., 21 (2018), 267–277. |
| [18] |
D. Giammarresi, A. Restivo, Recognizable picture languages, Int. J. Pattern Recog. Artif. Intell., 6 (1992), 241–256. https://doi.org/10.1142/S021800149200014X doi: 10.1142/S021800149200014X
|
| [19] | D. Giammarresi, A. Restivo, Two-dimensional languages, In: G. Rozenberg, A. Salomaa, Handbook of formal languages, Springer, 1997,215–267. https://doi.org/10.1007/978-3-642-59126-6 |
| [20] |
D. E. Knuth, J. Morris, V. Pratt, Fast pattern matching in strings, SIAM J. Comput., 6 (1977), 323–350. https://doi.org/10.1137/0206024 doi: 10.1137/0206024
|
| [21] | R. Cole, M. Crochemore, Z. Galil, L. Gasienec, R. Hariharan, S. Muthukrishnan, et al., Optically fast parallel algorithms for preprocessing and pattern matching in one and two dimensions, Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, 1993. https://doi.org/10.1109/SFCS.1993.366862 |
| [22] |
S. Geizhals, D. Sokol, Finding maximal 2-dimensional palindromes, Inf. Comput., 266 (2019), 161–172. https://doi.org/10.1016/j.ic.2019.03.001 doi: 10.1016/j.ic.2019.03.001
|
| [23] | P. Linz, S. H. Rodger, An introduction to formal languages and automata, 7 Eds., Jones & Barlett, 2023. |
| [24] |
G. Siromoney, R. Siromoney, K. Krithivasan, Array grammars and kolam, Comput. Graph. Image Process., 3 (1974), 63–82. https://doi.org/10.1016/0146-664X(74)90011-2 doi: 10.1016/0146-664X(74)90011-2
|
Figures(1)
Hannah Blasiyus, D. K. Sheena Christy. Two-dimensional array grammars in palindromic languages[J]. AIMS Mathematics, 2024, 9(7): 17305-17318. doi: 10.3934/math.2024841
DownLoad: