Characterizations of <i>M</i> -Equivalence and Weak <i>M</i> -Relation

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.