Independence of certain quantities indicating subword occurrences
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. (C) 2006 Elsevier B.V. All rights reserved.
subword parikh matrix scattered subword number of subwords independence of subwords ambiguity