Abstract
A Matrix q-Analogue of the Parikh Map
by: Omer Egecioglu and Oscar Ibarra
Abstract:
We introduce an extension of the Parikh mapping called the Parikh q-matrix mapping, which takes its values in matrices with polynomial entries. The morphism constructed represents a word w over a k-letter alphabet S as a k-dimensional upper-triangular matrix with entries that are nonnegative integral polynomials in variable q. We show that by appropriately embedding the k-letter alphabet into the (k+1)-letteralphabet and putting q=1, we obtain the extension of the Parikh mapping to (k+1)-dimensional (numerical) matrices introduced by Mateescu, Salomaa, Salomaa, and Yu. The Parikh q-matrix mapping however, produces matrices that carry more information about w than the numerical Parikh matrix.The entries of the q-matrix image of w under this morphism isconstructed by q-counting the number of occurrences of certain words as scattered subwords of w.
Keywords:
Parikh mapping, Parikh matrix mapping, scattered subword, q-analogue
Date:
February 2004
Document: 2004-06
