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.
@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] and , 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] , Binary amiable words. Int. J. Found. Comput. Sci. 18 (2007) 387-400. | Zbl 1123.68097
[3] , and , Parikh matrices and amiable words. Theoret. Comput. Sci. 390 (2008) 102-109. | Zbl 1134.68027
[4] , and , On the injectivity of the Parikh matrix mapping. Fund. Inform. 49 (2002) 289-299. | Zbl 0997.68075
[5] and , The origins of combinatorics on words. Eur. J. Combin. 28 (2007) 996-1022. | Zbl 1111.68092
[6] and , A Survey of Modern Algebra. MacMillan, New York, 4th edn. (1977). | Zbl 0061.04802
[7] and , The Prouhet-Tarry-Escott problem revisited. Enseign. Math. 40 (1994) 3-27. | Zbl 0810.11016
[8] , On fairness of D0L systems. Discrete Appl. Math. 155 (2007) 1769-1773. | Zbl 1127.68048
[9] , On subword symmetry of words. Int. J. Found. Comput. Sci. 19 (2008) 243-250. | Zbl 1155.68033
[10] , On fair words. J. Autom. Lang. Comb. 14 (2009) (to appear). | Zbl 1205.68271
[11] and , 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] and , Some characterizations of Parikh matrix equivalent binary words. Inform. Process. Lett. 92 (2004) 77-82. | Zbl 1173.68550
[13] , Combinatorics on words. Cambridge University Press (1997). | Zbl 0874.20040
[14] , 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] and , Matrix indicators for subword occurrences and ambiguity. Int. J. Found. Comput. Sci. 15 (2004) 277-292. | Zbl 1067.68117
[16] , , and , A sharpening of the Parikh mapping. RAIRO-Theor. Inf. Appl. 35 (2001) 551-564. | Numdam | Zbl 1005.68092
[17] , and , Subword histories and Parikh matrices. J. Comput. System Sci. 68 (2004) 1-21. | Zbl 1072.68085
[18] , On context-free languages. J. ACM 13 (1966) 570-581. | Zbl 0154.25801
[19] , Mémoire sur quelques relations entre les puissances des nombres. C.R. Acad. Sci. Paris 33 (1851) 255.
[20] , Independence of certain quantities indicating subword occurrences. Theoret. Comput. Sci. 362 (2006) 222-231. | Zbl 1100.68058
[21] , 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] , Extending Parikh matrices. Theoret. Comput. Sci. 310 (2004) 233-246. | Zbl 1071.68036
[24] Wikipedia. Rings. http://en.wikipedia.org/wiki/Ring_(mathematics).