| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 438072 | Theoretical Computer Science | 2008 | 8 Pages |
Abstract
The basic numerical quantity investigated in this paper is |w|u, the number of occurrences of a word u as a scattered subword of a word w. Arithmetical combinations of such quantities yield a so-called subword history. We investigate the information content of subword histories. Reducing subword histories to linear ones, as well as the recently introduced Parikh matrices, will be important tools. Simple polynomial formulas for computing the value of a subword history for arbitrary powers of a word are obtained.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
