On strongly \(M\)-unambiguous prints and Şerbǎnuţǎ's conjecture for Parikh matrices (Q1704577)

Parikh vectors record the number of occurrences of letters in words. Parikh matrices, which extend Parikh vectors, also preserve information on the number of occurrences of certain subwords. The injectivity problem, which relates to Parikh matrices, has been open for almost a decade. The problem is to characterize \(M\)-equivalent words, i.e., words that share the same Parikh matrix (a word is \(M\)-unambiguous if it is not \(M\)-equivalent to any distinct word). The authors relate this problem to the notion of print of a word and strong \(M\)-equivalence, an order-independent alternative to \(M\)-equivalence. They first generalize some work of Serbanuta on prints and \(M\)-unambiguity to strong \(M\)-equivalence. Then they show that for any alphabet, there exist only finitely many strongly \(M\)-unambiguous prints. They finally disprove a conjecture of Şerbănuţă [\textit{V. N. Şerbănuţă} and \textit{T. F. Şerbănuţă}, Fundam. Inform. 73, No. 1--2, 265--283 (2006; Zbl 1104.68058)] saying that the \(M\)-unambiguity of a word implies the \(M\)-unambiguity of the word's print. The authors also discuss a number of open problems.