Abstract
A q-Matrix Encoding Extending the Parikh Matrix Mapping
by: Omer Egecioglu
Abstract:
We introduce a generalization of the Parikh mapping called the Parikh q-matrix encoding, which takes its values in matrices with polynomial entries. The encoding represents a word w over a k-letter alphabet as a (k+1)-dimensional upper-triangular matrix with entries that are nonnegative integral polynomials in variable q$. Putting q=1, we obtain the morphism introduced by Mateescu, Salomaa, Salomaa, and Yu, which extends the Parikh mapping to (k+1)-dimensional (numerical) matrices.The Parikh q-matrix encoding however, produces matrices that carry more information about w than the numerical Parikh matrix. In fact it is injective.The entries of the q-matrix image of w under this encoding is constructed by q-counting the number of occurrences of certain words as scattered subwords of w. This construction is distinct from the Parikh $q$-matrix mapping into k-dimensional upper-triangular matrices with integral polynomial entries introduced by Egecioglu and Ibarra.
Keywords:
Parikh mapping, Parikh matrix mapping, scattered subword, q-analogue
Date:
May 2004
Document: 2004-14
