A sharpening of the Parikh mapping
Alexandru Mateescu; Arto Salomaa; Kai Salomaa; Sheng Yu
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 35, Issue: 6, page 551-564
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topMateescu, Alexandru, et al. "A sharpening of the Parikh mapping." RAIRO - Theoretical Informatics and Applications 35.6 (2010): 551-564. <http://eudml.org/doc/222049>.
@article{Mateescu2010,
abstract = {
In this paper we introduce
a sharpening of the Parikh mapping and investigate
its basic properties.
The new mapping is based on square
matrices of a certain form. The classical Parikh vector
appears in such a matrix as the second diagonal.
However, the matrix product gives more information about
a word than the Parikh vector. We characterize the matrix
products and establish also an interesting interconnection
between mirror images of words and inverses of .
},
author = {Mateescu, Alexandru, Salomaa, Arto, Salomaa, Kai, Yu, Sheng},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Formal languages; Parikh mapping; scattered subwords.; Parikh vector},
language = {eng},
month = {3},
number = {6},
pages = {551-564},
publisher = {EDP Sciences},
title = {A sharpening of the Parikh mapping},
url = {http://eudml.org/doc/222049},
volume = {35},
year = {2010},
}
TY - JOUR
AU - Mateescu, Alexandru
AU - Salomaa, Arto
AU - Salomaa, Kai
AU - Yu, Sheng
TI - A sharpening of the Parikh mapping
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 35
IS - 6
SP - 551
EP - 564
AB -
In this paper we introduce
a sharpening of the Parikh mapping and investigate
its basic properties.
The new mapping is based on square
matrices of a certain form. The classical Parikh vector
appears in such a matrix as the second diagonal.
However, the matrix product gives more information about
a word than the Parikh vector. We characterize the matrix
products and establish also an interesting interconnection
between mirror images of words and inverses of .
LA - eng
KW - Formal languages; Parikh mapping; scattered subwords.; Parikh vector
UR - http://eudml.org/doc/222049
ER -
References
top- A. Atanasiu, C. Martín-Vide and A. Mateescu, On the injectivity of the Parikh matrix mapping (submitted).
- T. Harju, O. Ibarra, J. Karhumäki and A. Salomaa, Some decision problems concerning semilinearity and commutation. J. Comput. System Sci. (to appear).
- J. Honkala, On slender languages. EATCS Bull.64 (1998) 145-152.
- J. Honkala, On Parikh slender languages and power series. J. Comput. System Sci.52 (1996) 185-190.
- L. Ilie, An attempt to define mildly context-sensitive languages. Publ. Math. Debrecen54 (1999) 865-876.
- L. Ilie, G. Rozenberg and A. Salomaa, A characterization of poly-slender context-free languages. RAIRO: Theoret. Informatics Appl.34 (2000) 77-86.
- J.J. Pansiot, A decidable property of iterated morphisms. Springer, Lecture Notes in Comput. Sci.104 (1981) 152-158.
- R.J. Parikh, On context-free languages. J. Assoc. Comput. Mach.13 (1966) 570-581.
- G. Rozenberg and A. Salomaa, Handbook of Formal Languages 1-3. Springer-Verlag, Berlin, Heidelberg, New York (1997).
- J. Sakarovitch and I. Simon, Subwords, edited by M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, Mass. (1983) 105-142.
- A. Salomaa, Formal Languages. Academic Press, New York (1973).
Citations in EuDML Documents
topNotesEmbed ?
topYou 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.