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},
zbl = {1005.68092},
mrnumber = {1922295},
language = {en},
url = {http://www.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
DA  - 2001///
SP  - 551
EP  - 564
VL  - 35
IS  - 6
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_2001__35_6_551_0/
UR  - https://zbmath.org/?q=an%3A1005.68092
UR  - https://www.ams.org/mathscinet-getitem?mr=1922295
LA  - en
ID  - ITA_2001__35_6_551_0
ER  - 
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://www.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 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