A q-Matrix Encoding Extending the Parikh Matrix Mapping

Report ID: 
2004-14
Authors: 
Omer Egecioglu
Date: 
2004-05-01 05:00:00

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.

Document

2004-14.pdf