Reducing the ambiguity of Parikh matrices: theoretical considerations and tools

The Parikh matrix mapping allows us to describe words using matrices. Whilst compact, this description comes with a level of ambiguity since a single matrix may describe multiple words. In this thesis, we investigate how considering the Parikh matrices of various transformations of a given word can decrease that ambiguity. More specifically, for any word, we study the Parikh matrix of its projection to a smaller alphabet as well as that of its Lyndon conjugate. Our results demonstrate that ambiguity can often be reduced using these concepts, and we give conditions on when they succeed.

We also provide and discuss a tool that handles many different Parikh matrix calculations. The user may utilise this software to find Parikh matrices, the words associated to a Parikh matrix, and words that share a Parikh matrix, as well as to perform calculations around the two concepts introduced in this thesis. We discuss various algorithms that may be used to find words that share a Parikh matrix and perform worst case time complexity analysis on each of these. Finally, we explain the functionality of the toolkit in greater detail, as well as explaining how each function is used.