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.  
  2. A. Atanasiu, Binary amiable words. Int. J. Found. Comput. Sci.18 (2007) 387–400.  
  3. A. Atanasiu, R. Atanasiu and I. Petre, Parikh matrices and amiable words. Theoret. Comput. Sci.390 (2008) 102–109.  
  4. A. Atanasiu, C. Martín-Vide and A. Mateescu, On the injectivity of the Parikh matrix mapping. Fund. Inform.49 (2002) 289–299.  
  5. J. Berstel and D. Perrin, The origins of combinatorics on words. Eur. J. Combin.28 (2007) 996–1022.  
  6. G. Birkhoff and S. Mac Lane, A Survey of Modern Algebra. MacMillan, New York, 4th edn. (1977).  
  7. P. Borwein and C. Ingalls, The Prouhet-Tarry-Escott problem revisited. Enseign. Math.40 (1994) 3–27.  
  8. A. Černý, On fairness of D0L systems. Discrete Appl. Math.155 (2007) 1769–1773.  
  9. A. Černý, On subword symmetry of words. Int. J. Found. Comput. Sci.19 (2008) 243–250.  
  10. A. Černý, On fair words. J. Autom. Lang. Comb.14 (2009) (to appear).  
  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.  
  13. M. Lothaire, Combinatorics on words. Cambridge University Press (1997).  
  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.  
  15. A. Mateescu and A. Salomaa, Matrix indicators for subword occurrences and ambiguity. Int. J. Found. Comput. Sci.15 (2004) 277–292.  
  16. A. Mateescu, A. Salomaa, K. Salomaa and S. Yu, A sharpening of the Parikh mapping. RAIRO-Theor. Inf. Appl.35 (2001) 551–564.  
  17. A. Mateescu, A. Salomaa and Sheng Yu, Subword histories and Parikh matrices. J. Comput. System Sci.68 (2004) 1–21.  
  18. R.J. Parikh, On context-free languages. J. ACM13 (1966) 570–581.  
  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.  
  21. A. Salomaa, Comparing subword occurrences in binary D0L sequences. Int. J. Found. Comput. Sci.18 (2007) 1395–1406.  
  22. A Salomaa, Subword balance in binary words, languages and sequences. Fund. Inform.75 (2007) 469–482.  
  23. T.-F. Şerbănuţă, Extending Parikh matrices. Theoret. Comput. Sci.310 (2004) 233–246.  
  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.