Injectivity of the Parikh Matrix Mappings Revisited

• Autorzy: Serbanuta V.N. , Serbanuta T.F.
• Języki publikacji: EN

Abstrakty

EN

We deal with the notion of M-unambiguity [5] in connection with the Parikh matrix mapping introduced by Mateescu and others in [7]. M-unambiguity is studied both in terms of words and matrices and several sufficient criteria for M-unambiguity are provided in both cases, nontrivially generalizing the criteria based on the g-property introduced by Salomaa in [15]. Also, the notion of M-unambiguity with respect to a word is defined in connection with the extended Parikh matrix morphism [16] and some of the M-unambiguity criteria are lifted from the classical setting to the extended one.

Słowa kluczowe

EN

subword; scattered subwords; parikh matrix; ambiguity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 1-2
• Strony: 265--283
• Opis fizyczny: biliogr. 17 poz.

Twórcy

autor

Serbanuta V.N.

autor

Serbanuta T.F.

• Faculty of Mathematics and Informatics, Bucharest University, Str. Academiei 14, sector 1, 010014 Bucharest, Romania,

Bibliografia

• [1] A. Atanasiu, C. Martin-Vide, A, Mateescu: Codifiable languages and the Parikh matrix mapping. J. UCS, 7 (2001), 783-793.
• [2] A. Atanasiu, C.Martin-Vide, A.Mateescu: On the injectivity of the Parikhmatrixmapping. Fundam. Inform., 49 (2002), 289-299.
• [3] C. Ding, A. Salomaa: On some problems of Mateescu concerning subword occurrences. Technical Report 701, TUCS, August 2005.
• [4] S. Fossé, G. Richomme: Some characterizations of Parikh matrix equivalent binary words. Inf. Process. Lett., 92 (2004), 77-82.
• [5] A. Mateescu, A. Salomaa: Matrix indicators for subword occurrences and ambiguity. Int. J. Found. Comput. Sci., 15 (2004), 277-292.
• [6] A. Mateescu, A. Salomaa, K. Salomaa, S. Yu: On an extension of the Parikh mapping. Technical Report 364, TUCS, 2000.
• [7] A. Mateescu, A. Salomaa, K. Salomaa, S. Yu: A sharpening of the Parikh mapping. ITA, 35, 6 (2001), 551-564.
• [8] A. Mateescu, A. Salomaa, S. Yu: Subword histories and Parikh matrices. J. Comput. Syst. Sci., 68 (2004), 1-21.
• [9] R. Parikh: On context-free languages. J. ACM, 13 (1966), 570-581.
• [10] G. Rozenberg, A Salomaa, eds.: Handbook of Formal Languages. Springer-Verlag, Berlin, 1997.
• [11] J. Sakarovitch, I. Simon: Subwords. In Combinatorics on Words (M. Lothaire, Ed.), Addison-Wesley, Reading, 1983, 105-144.
• [12] A. Salomaa: Formal Languages. Academic Press, New York, 1973.
• [13] A. Salomaa: Connections between subwords and certain matrix mappings. Theor. Comput. Sci., 340 (2005), 188-203.
• [14] A. Salomaa: On languages defined by numerical parameters. Technical Report 663, TUCS, 2005.
• [15] A. Salomaa: On the injectivity of Parikh matrix mappings. Fundamenta Informaticae, 64 (2005), 188-203.
• [16] T.F. Şerbǎnutǎ: Extending Parikh matrices. Theor. Comput. Sci., 310 (2004), 233-246.
• [17] V.N. Şerbǎ nutǎ: Matrice Parikh Injective. Master Thesis, Faculty of Mathematics, University of Bucharest, December 2002 (in Romanian).