Generalizations of Parikh mappings
Černý, Anton
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010), p. 209-228 / Harvested from Numdam

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.

Publié le : 2010-01-01
DOI : https://doi.org/10.1051/ita/2009021
Classification:  68R15
@article{ITA_2010__44_2_209_0,
     author = {\v Cern\'y, Anton},
     title = {Generalizations of Parikh mappings},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {44},
     year = {2010},
     pages = {209-228},
     doi = {10.1051/ita/2009021},
     mrnumber = {2674541},
     zbl = {pre05717747},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 209-228. doi : 10.1051/ita/2009021. http://gdmltest.u-ga.fr/item/ITA_2010__44_2_209_0/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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