Generalizations of Parikh mappings
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 2, pp. 209-228.

Parikh matrices have become a useful tool for investigation of subword structure of words. Several generalizations of this concept have been considered. Based on the concept of formal power series, we describe a general framework covering most of these generalizations. In addition, we provide a new characterization of binary amiable words - words having a common Parikh matrix.

DOI : 10.1051/ita/2009021
Classification : 68R15
Mots-clés : Parikh mapping, Parikh matrix, formal power series, Prouhet-Tarry-Escott problem, subword, amiable words 
@article{ITA_2010__44_2_209_0,
     author = {\v{C}ern\'y, Anton},
     title = {Generalizations of {Parikh} mappings},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {209--228},
     publisher = {EDP-Sciences},
     volume = {44},
     number = {2},
     year = {2010},
     doi = {10.1051/ita/2009021},
     mrnumber = {2674541},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2009021/}
}
TY  - JOUR
AU  - Černý, Anton
TI  - Generalizations of Parikh mappings
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2010
SP  - 209
EP  - 228
VL  - 44
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2009021/
DO  - 10.1051/ita/2009021
LA  - en
ID  - ITA_2010__44_2_209_0
ER  - 
%0 Journal Article
%A Černý, Anton
%T Generalizations of Parikh mappings
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2010
%P 209-228
%V 44
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2009021/
%R 10.1051/ita/2009021
%G en
%F ITA_2010__44_2_209_0
Černý, Anton. Generalizations of Parikh mappings. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 2, pp. 209-228. doi : 10.1051/ita/2009021. http://www.numdam.org/articles/10.1051/ita/2009021/

[1] J.-P. Allouche and J.O. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, in Sequences and Their Applications, Proceedings of SETA '98, edited by C. Ding, T. Helleseth and H. Niederreiter. Springer-Verlag (1999) 1-16. | Zbl

[2] A. Atanasiu, Binary amiable words. Int. J. Found. Comput. Sci. 18 (2007) 387-400. | Zbl

[3] A. Atanasiu, R. Atanasiu and I. Petre, Parikh matrices and amiable words. Theoret. Comput. Sci. 390 (2008) 102-109. | Zbl

[4] A. Atanasiu, C. Martín-Vide and A. Mateescu, On the injectivity of the Parikh matrix mapping. Fund. Inform. 49 (2002) 289-299. | Zbl

[5] J. Berstel and D. Perrin, The origins of combinatorics on words. Eur. J. Combin. 28 (2007) 996-1022. | Zbl

[6] G. Birkhoff and S. Mac Lane, A Survey of Modern Algebra. MacMillan, New York, 4th edn. (1977). | Zbl

[7] P. Borwein and C. Ingalls, The Prouhet-Tarry-Escott problem revisited. Enseign. Math. 40 (1994) 3-27. | Zbl

[8] A. Černý, On fairness of D0L systems. Discrete Appl. Math. 155 (2007) 1769-1773. | Zbl

[9] A. Černý, On subword symmetry of words. Int. J. Found. Comput. Sci. 19 (2008) 243-250. | Zbl

[10] A. Černý, On fair words. J. Autom. Lang. Comb. 14 (2009) (to appear). | Zbl

[11] Ö. Eğecioğlu and O.H. Ibarra, A matrix q-analogue of the Parikh mapping, in IFIP TCS, edited by J.-J. Lévy, E.W. Mayr and J.C. Mitchell. Kluwer (2004) 125-138.

[12] S. Fossé and G. Richomme, Some characterizations of Parikh matrix equivalent binary words. Inform. Process. Lett. 92 (2004) 77-82. | Zbl

[13] M. Lothaire, Combinatorics on words. Cambridge University Press (1997). | Zbl

[14] A. Mateescu, Algebraic aspects of Parikh matrices, in Theory Is Forever, edited by J. Karhumäki, H.A. Maurer, G. Păun and G. Rozenberg. Lect. Notes Comput. Sci. 3113 (2004) 170-180. | Zbl

[15] A. Mateescu and A. Salomaa, Matrix indicators for subword occurrences and ambiguity. Int. J. Found. Comput. Sci. 15 (2004) 277-292. | Zbl

[16] A. Mateescu, A. Salomaa, K. Salomaa and S. Yu, A sharpening of the Parikh mapping. RAIRO-Theor. Inf. Appl. 35 (2001) 551-564. | Numdam | Zbl

[17] A. Mateescu, A. Salomaa and Sheng Yu, Subword histories and Parikh matrices. J. Comput. System Sci. 68 (2004) 1-21. | Zbl

[18] R.J. Parikh, On context-free languages. J. ACM 13 (1966) 570-581. | Zbl

[19] E. Prouhet, Mémoire sur quelques relations entre les puissances des nombres. C.R. Acad. Sci. Paris 33 (1851) 255.

[20] A. Salomaa, Independence of certain quantities indicating subword occurrences. Theoret. Comput. Sci. 362 (2006) 222-231. | Zbl

[21] A. Salomaa, Comparing subword occurrences in binary D0L sequences. Int. J. Found. Comput. Sci. 18 (2007) 1395-1406. | Zbl

[22] A Salomaa, Subword balance in binary words, languages and sequences. Fund. Inform. 75 (2007) 469-482. | Zbl

[23] T.-F. Şerbănuţă, Extending Parikh matrices. Theoret. Comput. Sci. 310 (2004) 233-246. | Zbl

[24] Wikipedia. Rings. http://en.wikipedia.org/wiki/Ring_(mathematics).

Cité par Sources :