Article ID Journal Published Year Pages File Type
438651 Theoretical Computer Science 2006 10 Pages PDF
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