On Commuting Parikh q-Matrices

• Autorzy: Bera Somnath , Mahalingam Kalpana

Identyfikatory

DOI

10.3233/FI-2020-1907

• Języki publikacji: EN

Abstrakty

EN

This paper investigates properties of words such that their Parikh q-matrices commute. For any two words u , v ∈ ∑ _k *, the concept of q-weak ratio property between u and v is introduced. Based on this property a necessary and sufficient condition for the Parikh q-matrices of any two words over binary alphabet to commute is given. This paper also provides a special class of words over an arbitrary alphabet ∑_k such that their Parikh q-matrices commute.

Słowa kluczowe

EN

commutativity; Parikh q-matrix mapping; q-ambiguity; q-weak ratio property

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 172, nr 4
• Strony: 327--341
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Bera Somnath

• Department of Mathematics, Indian Institute of Technology Madras, Chennai-600036 India

autor

Mahalingam Kalpana

• Department of Mathematics, Indian Institute of Technology Madras, Chennai-600036 India

Bibliografia

• [1] Mateescu A, Salomaa A, Salomaa K, Yu S. A sharpening of the Parikh mapping. ITA, 2001. 35(6):551-564. doi:10.1051/ita:2001131.
• [2] Atanasiu A, Martín-Vide C, Mateescu A. On the Injectivity of the Parikh Matrix Mapping. Fundam. Inform., 2002. 49(4):289-299. URL http://content.iospress.com/articles/fundamenta-informaticae/fi49-4-01.
• [3] Ding C, Salomaa A. On Some Problems of Mateescu Concerning Subword Occurrences. Fundam. Inform., 2006. 73(1-2):65-79. URL http://content.iospress.com/articles/fundamenta-informaticae/fi73-1-2-07.
• [4] Fossé S, Richomme G. Some characterizations of Parikh matrix equivalent binary words. Inf. Process. Lett., 2004. 92(2):77-82. doi:10.1016/j.ipl.2004.06.011.
• [5] Mateescu A, Salomaa A. Matrix Indicators For Subword Occurrences And Ambiguity. Int. J. Found. Comput. Sci., 2004. 15(2):277-292. doi:10.1142/S0129054104002418.
• [6] Salomaa A. On the Injectivity of Parikh Matrix Mappings. Fundam. Inform., 2005. 64(1-4):391-404. URL http://content.iospress.com/articles/fundamenta-informaticae/fi64-1-4-33.
• [7] Salomaa A. Parikh Matrices: Subword Indicators and Degrees of Ambiguity. In: Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday. 2018 pp. 100-112. doi:10.1007/978-3-319-98355-4\_7.
• [8] Poovanandran G, Teh WC. Elementary matrix equivalence and core transformation graphs for Parikh matrices. Discrete Applied Mathematics, 2018. 251:276-289. doi:10.1016/j.dam.2018.06.002.
• [9] Atanasiu A, Poovanandran G, Teh WC. Parikh matrices for powers of words. Acta Inf., 2019. 56(6):521-535. doi:10.1007/s00236-018-0327-8.
• [10] Poovanandran G, Teh WC. On M-Equivalence and Strong M-Equivalence for Parikh Matrices. Int. J. Found. Comput. Sci., 2018. 29(1):123-138. doi:10.1142/S0129054118500065.
• [11] Teh WC, Subramanian KG, Bera S. Order of weak M-relation and Parikh matrices. Theor. Comput. Sci., 2018. 743:83-92. doi:10.1016/j.tcs.2018.04.042.
• [12] Egecioglu Ö, Ibarra OH. A Matrix q-Analogue of the Parikh Map. In: Exploring New Frontiers of Theoretical Informatics, IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004), 22-27 August 2004, Toulouse, France. 2004 pp. 125-138. doi:10.1007/1-4020-8141-3\_12.
• [13] Bera S, Mahalingam K. Some Algebraic Aspects of Parikh q-Matrices. Int. J. Found. Comput. Sci., 2016. 27(4):479-500. doi:10.1142/S0129054116500118.
• [14] Mahalingam K, Subramanian KG. Product of Parikh Matrices and Commutativity. Int. J. Found. Comput. Sci., 2012. 23(1):207-223. doi:10.1142/S0129054112500049.
• [15] Atanasiu A, Atanasiu RF. Message Authentication Code based on Parikh Matrices. In: Proceedings of International Conference on Security for Information technology and communication SECIT& C 2008, 27-28 Nov. 2008 pp. 7-14.
• [16] Bera S, Mahalingam K. Structural Properties of Word Representable Graphs. Mathematics in Computer Science, 2016. 10(2):209-222. doi:10.1007/s11786-016-0257-1.
• [17] Mathew L, Thomas N, Bera S, Subramanian KG. Some results on Parikh word representable graphs and partitions. Adv. Appl. Math., 2019. 107:102-115. doi:10.1016/j.aam.2019.02.009.
• [18] Aisah I, Jayanti PRE, Supriatna AK. 2-cut splicing and 4-cut splicing on DNA molecule. IOP Conference Series: Materials Science and Engineering, 2019. 567:012018. doi:10.1088/1757-899x/567/1/012018.
• [19] Parikh R. On Context-Free Languages. J. ACM, 1966. 13(4):570-581. doi:10.1145/321356.321364.
• [20] Serbanuta VN, Serbanuta T. Injectivity of the Parikh Matrix Mappings Revisited. Fundam. Inform., 2006. 73(1-2):265-283. URL http://content.iospress.com/articles/fundamenta-informaticae/fi73-1-2-23.
• [21] Bera S, Ceterchi R, Subramanian KG, Mahalingam K. Parikh q-matrices and q-ambiguous words. Int. J. Found. Comput. Sci., March, 2018. Accepted.
• [22] Subramanian KG, Huey AM, Nagar AK. On Parikh Matrices. Int. J. Found. Comput. Sci., 2009. 20(2):211-219. doi:10.1142/S0129054109006528.
• [23] Salomaa A, Yu S. Subword Occurrences, Parikh Matrices and Lyndon Images. Int. J. Found. Comput. Sci., 2010. 21(1):91-111. doi:10.1142/S0129054110007155

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).