Back to Search
Start Over
SUBWORD OCCURRENCES, PARIKH MATRICES AND LYNDON IMAGES.
- Source :
-
International Journal of Foundations of Computer Science . Feb2010, Vol. 21 Issue 1, p91-111. 21p. - Publication Year :
- 2010
-
Abstract
- We investigate the number of occurrences of a word u as a (scattered) subword of a word w. The notion of a Parikh matrix, recently introduced, is a basic tool in this investigation. In general, several words are associated with a Parikh matrix. The ambiguity can be resolved by associating a unique word called the Lyndon image to each Parikh matrix. In this paper we will investigate properties of Lyndon images and the corresponding questions of ambiguity. We give an exhaustive characterization in the case of a binary alphabet. Our main results in the general case deal with the comparison of unambiguous words and Lyndon images, algorithms for constructing Lyndon images, as well as classes of words with the same Parikh matrix, obtained by circular variance. [ABSTRACT FROM AUTHOR]
- Subjects :
- *VOCABULARY
*MATRIX groups
*ALPHABETS
*LETTERING
*ANALYSIS of variance
Subjects
Details
- Language :
- English
- ISSN :
- 01290541
- Volume :
- 21
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- International Journal of Foundations of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 48014228
- Full Text :
- https://doi.org/10.1142/S0129054110007155