Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
438651 | Theoretical Computer Science | 2006 | 10 Pages |
Abstract
When words are characterized in terms of numerical quantities, awkward considerations due to the noncommutativity of words are avoided. The 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. Parikh matrices recently introduced have these quantities as their entries. According to the main result in this paper, no entry in a Parikh matrix, no matter how high the dimension, can be computed in terms of the other entries. Consequences concerning various inference problems between numbers |w|u themselves, as well as of the word w from these numbers, are obtained.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics