Parikh Matrices and Parikh Rewriting Systems

• Autorzy: Teh W. C.

Identyfikatory

DOI

10.3233/FI-2016-1388

• Języki publikacji: EN

Abstrakty

EN

Since the introduction of the Parikh matrix mapping, its injectivity problem is on top of the list of open problems in this topic. In 2010 Salomaa provided a solution for the ternary alphabet in terms of a Thue system with an additional feature called counter. This paper proposes the notion of a Parikh rewriting system as a generalization and systematization of Salomaa’s result. It will be shown that every Parikh rewriting system induces a Thue system without counters that serves as a feasible solution to the injectivity problem.

Słowa kluczowe

EN

Parikh matrix; subword; injectivity problem; Parikh rewriting system; M-equivalence

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 146, nr 3
• Strony: 305--320
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

Teh W. C.

• School of Mathematical Sciences, Universiti Sains Malaysia, 11800 USM, Malaysia

Bibliografia

• [1] Mateescu A, Salomaa A, Salomaa K, Yu S. A sharpening of the Parikh mapping. Theor Inform Appl. 2001;35(6):551-564 (2002). doi:10.1051/ita:2001131.
• [2] Parikh RJ. On context-free languages. J Assoc Comput Mach. 1966;13:570-581.
• [3] Atanasiu A. Binary amiable words. Internat J Found Comput Sci. 2007;18(2):387-400. doi:10.1142/S0129054107004735.
• [4] Atanasiu A. Parikh matrices, amiability and Istrail morphism. Internat J Found Comput Sci. 2010;21(6):1021-1033. doi:10.1142/S0129054110007702.
• [5] Atanasiu A. Parikh Matrix Mapping and Amiability Over a Ternary Alphabet. In: Discrete Mathematics and Computer Science. In Memoriam Alexandru Mateescu (1952-2005).; 2014. p. 1-12.
• [6] Atanasiu A, Atanasiu R, Petre I. Parikh matrices and amiable words. Theoret Comput Sci. 2008;390(1):102-109. doi:10.1016/j.tcs.2007.10.022.
• [7] Atanasiu A, Martín-Vide C, Mateescu A. On the injectivity of the Parikh matrix mapping. Fund Inform. 2002;49(4):289-299.
• [8] Fossé S, Richomme G. Some characterizations of Parikh matrix equivalent binary words. Inform Process Lett. 2004;92(2):77-82. doi:10.1016/j.ipl.2004.06.011.
• [9] Mahalingam K, Subramanian KG. Product of Parikh matrices and commutativity. Internat J Found Comput Sci. 2012;23(1):207-223. doi:10.1142/S0129054112500049.
• [10] Mateescu A, Salomaa A. Matrix indicators for subword occurrences and ambiguity. Internat J Found Comput Sci. 2004;15(2):277-292. doi:10.1142/S0129054104002418.
• [11] Salomaa A. On the injectivity of Parikh matrix mappings. Fund Inform. 2005;64:391-404.
• [12] Salomaa A. Criteria for the matrix equivalence of words. Theoret Comput Sci. 2010;411:1818-1827. doi:10.1016/j.tcs.2010.01.036.
• [13] Salomaa A, Yu S. Subword occurrences, Parikh matrices and Lyndon images. Internat J Found Comput Sci. 2010;21(1):91-111. doi:10.1142/S0129054110007155.
• [14] Şerbӑnutӑ VN. On Parikh matrices, ambiguity, and prints. Internat J Found Comput Sci. 2009;20(1):151-165. doi:10.1142/S0129054109006498.
• [15] Şerbӑnutӑ VN, Şerbӑnutӑ TF. Injectivity of the Parikh matrix mappings revisited. Fund Inform. 2006; 73:265-283.
• [16] Teh WC. On core words and the Parikh matrix mapping. Internat J Found Comput Sci. 2015;26(1):123-142. doi:10.1142/S0129054115500069.
• [17] Teh WC. Separability of M-equivalent words by morphisms. Internat J Found Comput Sci. 2016;27(1):39-52. doi:10.1142/S0129054116500039.
• [18] Teh WC, Atanasiu A. On a conjecture about Parikh matrices. Theoret Comput Sci. 2016;628:30-39. doi:10.1016/j.tcs.2016.03.008.
• [19] Teh WC, Kwa KH. Core words and Parikh matrices. Theoret Comput Sci. 2015;582:60-69. doi:10.1016/j.tcs.2015.03.037.
• [20] Rozenberg G, Salomaa A, editors. Handbook of formal languages. Vol. 1. Springer-Verlag, Berlin; 1997.
• [21] Manvel B, Meyerowitz A, Schwenk A, Smith K, Stockmeyer P. Reconstruction of sequences. Discrete Math. 1991;94(3):209-219. doi:10.1016/0012-365X(91)90026-X.