A sharpening of the Parikh mapping
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 6, pp. 551-564.

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.

Classification : 68Q45, 68Q70
Mots-clés : formal languages, Parikh mapping, scattered subwords 
@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},
     pages = {551--564},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {6},
     year = {2001},
     mrnumber = {1922295},
     zbl = {1005.68092},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_2001__35_6_551_0/}
}
TY  - JOUR
AU  - Mateescu, Alexandru
AU  - Salomaa, Arto
AU  - Salomaa, Kai
AU  - Yu, Sheng
TI  - A sharpening of the Parikh mapping
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2001
SP  - 551
EP  - 564
VL  - 35
IS  - 6
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_2001__35_6_551_0/
LA  - en
ID  - ITA_2001__35_6_551_0
ER  - 
%0 Journal Article
%A Mateescu, Alexandru
%A Salomaa, Arto
%A Salomaa, Kai
%A Yu, Sheng
%T A sharpening of the Parikh mapping
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 551-564
%V 35
%N 6
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_2001__35_6_551_0/
%G en
%F 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) no. 6, pp. 551-564. http://archive.numdam.org/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

[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 | Zbl

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

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

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

[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 | Zbl

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

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

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

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

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