Abstract
Based on the idea of \(\texttt {q}-\)count of certain subwords of a word, the notion of Parikh \(\texttt {q}-\)matrix of a word over an ordered alphabet was introduced. On the other hand, with a two-dimensional picture array of symbols arranged in rows and columns, two kinds of upper triangular matrices, known as row and column Parikh \(\texttt {q}-\)matrices have also been introduced and investigated. Certain algebraic properties such as Parikh \(\texttt {q}-\)matrices commutators, alternate Parikh \(\texttt {q}-\)matrices and extending Parikh \(\texttt {q}-\)matrices have been investigated for one dimensional case, yet they do not suffice for two-dimensional words. In this paper, we introduce Parikh \(\texttt {q}-\)matrices commutators, alternate Parikh \(\texttt {q}-\)matrices and extending Parikh \(\texttt {q}-\)matrices for two-dimensional words and discuss their properties. We also derive the result used for transferring information with respect to subword occurrences derived from Parikh \(\texttt {q}-\)matrices to corresponding information derived from extending Parikh \(\texttt {q}-\)matrices.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Atanasiu, A.: Binary amiable words. Int. J. Found. Comput. Sci. 18(2), 387–400 (2007). https://doi.org/10.1142/S0129054107004735
Atanasiu, A., Atanasiu, R., Petre, I.: Parikh matrices and amiable words. Theor. Comput. Sci. 390(1), 102–109 (2008). https://doi.org/10.1016/j.tcs.2007.10.022
Atanasiu, A., Martín-Vide, C., Mateescu, A.: On the injectivity of the parikh matrix mapping. Fundam. Informaticae 49(4), 289–299 (2002). http://content.iospress.com/articles/fundamenta-informaticae/fi49-4-01
Bera, S., Ceterchi, R., Mahalingam, K., Subramanian, K.G.: Parikh q-matrices and q-ambiguous words. Int. J. Found. Comput. Sci. 31(1), 23–36 (2020). https://doi.org/10.1142/S012905412040002X
Bera, S., Mahalingam, K.: Extending parikh q-matrices. Int. J. Comput. Appl. 975, 8887 (2016)
Bera, S., Mahalingam, K.: Some algebraic aspects of parikh q-matrices. Int. J. Found. Comput. Sci. 27(4), 479–500 (2016). https://doi.org/10.1142/S0129054116500118
Bera, S., Mahalingam, K.: On commuting parikh q-matrices. Fundam. Informaticae 172(4), 327–341 (2020). https://doi.org/10.3233/FI-2020-1907
Bera, S., Mahalingam, K., Pan, L., Subramanian, K.: Two-dimensional picture arrays and parikh q-matrices. In: Journal of Physics: Conference Series, vol. 1132, p. 012006. IOP Publishing (2018)
Berthé, V., Tijdeman, R.: Balance properties of multi-dimensional words. Theor. Comput. Sci. 273(1–2), 197–224 (2002). https://doi.org/10.1016/S0304-3975(00)00441-2
Carpi, A., de Luca, A.: Repetitions and boxes in words and pictures. In: Karhumäki, J., Maurer, H.A., Paun, G., Rozenberg, G. (eds.) Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, pp. 295–306. Springer, Cham (1999). https://doi.org/10.1007/978-3-642-60207-8_26
Carpi, A., de Luca, A.: Repetitions, fullness, and uniformity in two-dimensional words. Int. J. Found. Comput. Sci. 15(2), 355–383 (2004). https://doi.org/10.1142/S0129054104002479
Egecioglu, O., Ibarra, O.H.: A matrix Q-analogue of the Parikh map. In: Levy, J.-J., Mayr, E.W., Mitchell, J.C. (eds.) TCS 2004. IIFIP, vol. 155, pp. 125–138. Springer, Boston, MA (2004). https://doi.org/10.1007/1-4020-8141-3_12
Egecioglu, Ö., Ibarra, O.H.: A q-analogue of the Parikh matrix mapping. In: Mukund, M., Rangarajan, K., Subramanian, K.G. (eds.) Formal Models, Languages and Applications [this volume commemorates the 75th birthday of Prof. Rani Siromoney]. Series in Machine Perception and Artificial Intelligence, vol. 66, pp. 97–111. World Scientific (2007). https://doi.org/10.1142/9789812773036_0007
Janaki, K., Arulprakasam, R., Dare, V.: Generalized Parikh matrices of picture array. J. Math. Comput. Sci. 11(2), 1955–1969 (2021)
Mateescu, A.: Algebraic aspects of Parikh matrices. In: Karhumäki, J., Maurer, H., Păun, G., Rozenberg, G. (eds.) Theory Is Forever. LNCS, vol. 3113, pp. 170–180. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27812-2_16
Mateescu, A., Salomaa, A., Salomaa, K., Yu, S.: A sharpening of the Parikh mapping. RAIRO Theor. Inf. Appl. 35(6), 551–564 (2001). https://doi.org/10.1051/ita:2001131
Parikh, R.: On context-free languages. J. ACM 13(4), 570–581 (1966). https://doi.org/10.1145/321356.321364
Poovanandran, G., Teh, W.C.: On m-equivalence and strong m-equivalence for Parikh matrices. Int. J. Found. Comput. Sci. 29(1), 123–138 (2018). https://doi.org/10.1142/S0129054118500065
Poovanandran, G., Teh, W.C.: Strong (2 \(\cdot \) t) and strong (3 \(\cdot \) t) transformations for strong m-equivalence. Int. J. Found. Comput. Sci. 30(5), 719–733 (2019). https://doi.org/10.1142/S0129054119500187
Salomaa, A.: On the injectivity of parikh matrix mappings. Fundam. Informaticae 64(1–4), 391–404 (2005). http://content.iospress.com/articles/fundamenta-informaticae/fi64-1-4-33
Salomaa, A.: Parikh matrices: subword indicators and degrees of ambiguity. In: Böckenhauer, H.-J., Komm, D., Unger, W. (eds.) Adventures Between Lower Bounds and Higher Altitudes. LNCS, vol. 11011, pp. 100–112. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98355-4_7
Serbanuta, T.: Extending Parikh matrices. Theor. Comput. Sci. 310(1–3), 233–246 (2004). https://doi.org/10.1016/S0304-3975(03)00396-7
Subramanian, K.G., Huey, A.M., Nagar, A.K.: On Parikh matrices. Int. J. Found. Comput. Sci. 20(2), 211–219 (2009). https://doi.org/10.1142/S0129054109006528
Subramanian, K.G., Mahalingam, K., Abdullah, R., Nagar, A.K.: Two-dimensional digitized picture arrays and Parikh matrices. Int. J. Found. Comput. Sci. 24(3), 393–408 (2013). https://doi.org/10.1142/S012905411350010X
Teh, W.C.: On core words and the Parikh matrix mapping. Int. J. Found. Comput. Sci. 26(1), 123–142 (2015). https://doi.org/10.1142/S0129054115500069
Teh, W.C.: Parikh matrices and strong M-equivalence. Int. J. Found. Comput. Sci. 27(5), 545–556 (2016). https://doi.org/10.1142/S0129054116500155
Teh, W.C.: Parikh-friendly permutations and uniformly Parikh-friendly words. Australas. J. Comb. 76, 208–219 (2020). http://ajc.maths.uq.edu.au/pdf/76/ajc_v76_p208.pdf
Teh, W.C., Kwa, K.H.: Core words and Parikh matrices. Theor. Comput. Sci. 582, 60–69 (2015). https://doi.org/10.1016/j.tcs.2015.03.037
Masilamani, V., Krithivasan, K., Subramanian, K.G., Huey, A.M.: Efficient algorithms for reconstruction of 2D-arrays from extended Parikh images. In: Bebis, G., et al. (eds.) ISVC 2008. LNCS, vol. 5359, pp. 1137–1146. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-89646-3_113
Acknowledgements
We would like to thank the unknown referees for their comments and suggestions on the manuscript in improving from an earlier version. The authors K. Janaki and R. Arulprakasam are very much thankful to the management, SRM Institute of Science and Technology for their continuous support and encouragement.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Janaki, K., Arulprakasam, R., Paramasivan, M., Dare, V.R. (2023). Algebraic Properties of Parikh \(\texttt {q}\)-Matrices on Two-Dimensional Words. In: Barneva, R.P., Brimkov, V.E., Nordo, G. (eds) Combinatorial Image Analysis. IWCIA 2022. Lecture Notes in Computer Science, vol 13348. Springer, Cham. https://doi.org/10.1007/978-3-031-23612-9_11
Download citation
DOI: https://doi.org/10.1007/978-3-031-23612-9_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-23611-2
Online ISBN: 978-3-031-23612-9
eBook Packages: Computer ScienceComputer Science (R0)