Generalizations of Parikh mappings

Anton Černý

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 44, Issue: 2, page 209-228
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Černý, Anton. "Generalizations of Parikh mappings." RAIRO - Theoretical Informatics and Applications 44.2 (2010): 209-228. <http://eudml.org/doc/250762>.

@article{Černý2010,
abstract = { 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. },
author = {Černý, Anton},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Parikh mapping; Parikh matrix; formal power series; Prouhet-Tarry-Escott problem; subword; amiable words; Prouhet-Tarry-Escott problem},
language = {eng},
month = {5},
number = {2},
pages = {209-228},
publisher = {EDP Sciences},
title = {Generalizations of Parikh mappings},
url = {http://eudml.org/doc/250762},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Černý, Anton
TI - Generalizations of Parikh mappings
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/5//
PB - EDP Sciences
VL - 44
IS - 2
SP - 209
EP - 228
AB - 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.
LA - eng
KW - Parikh mapping; Parikh matrix; formal power series; Prouhet-Tarry-Escott problem; subword; amiable words; Prouhet-Tarry-Escott problem
UR - http://eudml.org/doc/250762
ER -

References

top
  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.  Zbl1005.11005
  2. A. Atanasiu, Binary amiable words. Int. J. Found. Comput. Sci.18 (2007) 387–400.  Zbl1123.68097
  3. A. Atanasiu, R. Atanasiu and I. Petre, Parikh matrices and amiable words. Theoret. Comput. Sci.390 (2008) 102–109.  Zbl1134.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.  Zbl0997.68075
  5. J. Berstel and D. Perrin, The origins of combinatorics on words. Eur. J. Combin.28 (2007) 996–1022.  Zbl1111.68092
  6. G. Birkhoff and S. Mac Lane, A Survey of Modern Algebra. MacMillan, New York, 4th edn. (1977).  Zbl0863.00001
  7. P. Borwein and C. Ingalls, The Prouhet-Tarry-Escott problem revisited. Enseign. Math.40 (1994) 3–27.  Zbl0810.11016
  8. A. Černý, On fairness of D0L systems. Discrete Appl. Math.155 (2007) 1769–1773.  Zbl1127.68048
  9. A. Černý, On subword symmetry of words. Int. J. Found. Comput. Sci.19 (2008) 243–250.  Zbl1155.68033
  10. A. Černý, On fair words. J. Autom. Lang. Comb.14 (2009) (to appear).  Zbl1205.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.  Zbl1066.68067
  12. S. Fossé and G. Richomme, Some characterizations of Parikh matrix equivalent binary words. Inform. Process. Lett. 92 (2004) 77–82.  Zbl1173.68550
  13. M. Lothaire, Combinatorics on words. Cambridge University Press (1997).  Zbl0874.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.  Zbl1055.68074
  15. A. Mateescu and A. Salomaa, Matrix indicators for subword occurrences and ambiguity. Int. J. Found. Comput. Sci.15 (2004) 277–292.  Zbl1067.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.  Zbl1005.68092
  17. A. Mateescu, A. Salomaa and Sheng Yu, Subword histories and Parikh matrices. J. Comput. System Sci.68 (2004) 1–21.  Zbl1072.68085
  18. R.J. Parikh, On context-free languages. J. ACM13 (1966) 570–581.  Zbl0154.25801
  19. E. Prouhet, Mémoire sur quelques relations entre les puissances des nombres. C.R. Acad. Sci. Paris33 (1851) 255.  
  20. A. Salomaa, Independence of certain quantities indicating subword occurrences. Theoret. Comput. Sci.362 (2006) 222–231.  Zbl1100.68058
  21. A. Salomaa, Comparing subword occurrences in binary D0L sequences. Int. J. Found. Comput. Sci.18 (2007) 1395–1406.  Zbl1183.68353
  22. A Salomaa, Subword balance in binary words, languages and sequences. Fund. Inform.75 (2007) 469–482.  Zbl1108.68072
  23. T.-F. Şerbănuţă, Extending Parikh matrices. Theoret. Comput. Sci.310 (2004) 233–246.  Zbl1071.68036
  24. Wikipedia. Rings. http://en.wikipedia.org/wiki/Ring_(mathematics).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.