Narrow Results

The Parikh matrix, an extension of the Parikh vector for words, is a fundamental concept in combinatorics on words. We investigate $M$-unambiguity that identifies words with unique Parikh matrices. While the problem of identifying $M$-unambiguous words for a binary alphabet is solved using a palindromicly amicable relation, it is open for larger alphabets. We propose substitution rules that establish $M$-equivalence and solve the problem of $M$-unambiguity for a ternary alphabet. Our rules build on the principles of the palindromicly amicable relation and enable tracking of the differences of length-3 ordered subsequences. We characterize the set of $M$-unambiguous words and obtain a regular expression for the set. In addition, we examine the weak $M$-relation, a variant of $M$-equivalence, and present a solution for the generalization of weak $M$-relation regarding its degree.

Two words are M-equivalent iff they are indistinguishable by Parikh matrices. Even for the ternary alphabet, an incontestable characterization of the M-equivalence relation is long overdue, ever since the introduction of Parikh matrices by Mateescu et al. in 2001. Recent works by Atanasiu attempted to distinguish M-equivalent words by the Parikh matrices of their images under some morphism. This paper addresses various aspects of this approach. In particular, it is shown that no morphism is capable of completely separating M-equivalent words over a given alphabet. However, if the class of words is restricted in length, then such morphism exists, whose codomain is connected to the notion of t-spectrum.

Parikh matrices have been a powerful tool in arithmetizing words by numerical quantities. However, the dependence on the ordering of the alphabet is inherited by Parikh matrices. Strong M-equivalence is proposed as a canonical alternative to M-equivalence to get rid of this undesirable property. Some characterization of strong M-equivalence for a restricted class of ternary words is obtained. Finally, the existential counterpart of strong M-equivalence is introduced as well.

The characterization of M-equivalence for the Parikh matrices is a decade old open problem. This paper studies Parikh matrices and M-equivalence in relation to the s-shuffle operator for the binary alphabet. We also study the distance between images under the s-shuffle operator in a graph associated to the corresponding class of M-equivalent words.

The notion of strong $M$-equivalence was introduced as an order-independent alternative to $M$-equivalence for Parikh matrices. This paper further studies the notions of $M$-equivalence and strong $M$-equivalence. Certain structural properties of $M$-equivalent ternary words are presented and then employed to (partially) characterize pairs of ternary words that are ME-equivalent (i.e. obtainable from one another by certain elementary transformations). Finally, a sound rewriting system in determining strong $M$-equivalence is obtained for the ternary alphabet.

Parikh matrices as an extension of Parikh vectors are useful tools in arithmetizing words by numbers. This paper presents a further study of Parikh matrices by restricting the corresponding words to terms formed over a signature. Some $M$-equivalence preserving rewriting rules for such terms are introduced. A characterization of terms that are only $M$-equivalent to themselves is studied for binary signatures. Graphs associated to the equivalence classes of $M$-equivalent terms are studied with respect to graph distance. Finally, the preservation of $M$-equivalence under the term self-shuffle operator is studied.