Injectivity of the Parikh matrix mappings revisited. (English) Zbl 1104.68058

Summary: We deal with the notion of \(M\)-unambiguity in connection with the Parikh matrix mapping introduced by A. Mateescu, A. Salomaa, K. Salomaa and S. Yu [Theor. Inform. Appl. 35, 551–564 (2001; Zbl 1005.68092)]. \(M\)-unambiguity is studied both in terms of words and matrices and several sufficient criteria for \(M\)-unambiguity are provided in both cases, nontrivially generalizing the criteria based on the \(\gamma\)-property introduced by A. Salomaa [Fundam. Inform. 64, 391–404 (2005; Zbl 1102.68072)]. Also, the notion of \(M\)-unambiguity with respect to a word is defined in connection with the extended Parikh matrix morphism and some of the \(M\)-unambiguity criteria are lifted from the classical setting to the extended one.
This paper is a revised and extended version of [V. N. Şerbănuţă, Matrice Parikh injective (Romanian). Master Thesis, Faculty of Mathematics, University of Bucharest (2002)].


68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata