A Matrix q-Analogue of the Parikh Map

Report ID: 
Omer Egecioglu and Oscar Ibarra
2004-02-01 04:00:00


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.


File 2004-06.ps