A sharpening of the Parikh mapping
Mateescu, Alexandru ; Salomaa, Arto ; Salomaa, Kai ; Yu, Sheng
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001), p. 551-564 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

In this paper we introduce a sharpening of the Parikh mapping and investigate its basic properties. The new mapping is based on square matrices of a certain form. The classical Parikh vector appears in such a matrix as the second diagonal. However, the matrix product gives more information about a word than the Parikh vector. We characterize the matrix products and establish also an interesting interconnection between mirror images of words and inverses of matrices.

Publié le : 2001-01-01
Classification:  68Q45,  68Q70 
@article{ITA_2001__35_6_551_0,
     author = {Mateescu, Alexandru and Salomaa, Arto and Salomaa, Kai and Yu, Sheng},
     title = {A sharpening of the Parikh mapping},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {35},
     year = {2001},
     pages = {551-564},
     mrnumber = {1922295},
     zbl = {1005.68092},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2001__35_6_551_0}
}

Mateescu, Alexandru; Salomaa, Arto; Salomaa, Kai; Yu, Sheng. A sharpening of the Parikh mapping. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) pp. 551-564. http://gdmltest.u-ga.fr/item/ITA_2001__35_6_551_0/

[1] A. Atanasiu, C. Martín-Vide and A. Mateescu, On the injectivity of the Parikh matrix mapping (submitted). | Zbl 0997.68075

[2] T. Harju, O. Ibarra, J. Karhumäki and A. Salomaa, Some decision problems concerning semilinearity and commutation. J. Comput. System Sci. (to appear). | MR 1939772 | Zbl 1059.68061

[3] J. Honkala, On slender languages. EATCS Bull. 64 (1998) 145-152. | MR 1618305 | Zbl 0898.68042

[4] J. Honkala, On Parikh slender languages and power series. J. Comput. System Sci. 52 (1996) 185-190. | MR 1375813 | Zbl 0846.68056

[5] L. Ilie, An attempt to define mildly context-sensitive languages. Publ. Math. Debrecen 54 (1999) 865-876. | MR 1709927 | Zbl 0981.68086

[6] L. Ilie, G. Rozenberg and A. Salomaa, A characterization of poly-slender context-free languages. RAIRO: Theoret. Informatics Appl. 34 (2000) 77-86. | Numdam | MR 1771131 | Zbl 0966.68097

[7] J.J. Pansiot, A decidable property of iterated morphisms. Springer, Lecture Notes in Comput. Sci. 104 (1981) 152-158. | Zbl 0457.68095

[8] R.J. Parikh, On context-free languages. J. Assoc. Comput. Mach. 13 (1966) 570-581. | MR 209093 | Zbl 0154.25801

[9] G. Rozenberg and A. Salomaa, Handbook of Formal Languages 1-3. Springer-Verlag, Berlin, Heidelberg, New York (1997). | Zbl 0866.68057

[10] J. Sakarovitch and I. Simon, Subwords, edited by M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, Mass. (1983) 105-142. | MR 675953

[11] A. Salomaa, Formal Languages. Academic Press, New York (1973). | MR 438755 | Zbl 0262.68025