Injectivity of the Parikh Matrix Mappings Revisited

Issue title: SPECIAL ISSUE ON TRAJECTORIES OF LANGUAGE THEORY Dedicated to the memory of Alexandru Mateescu

Article type: Research Article

Authors: Şerbănuţă, Virgil Nicolae | Şerbănuţă, Traian Florin

Affiliations: Faculty of Mathematics and Informatics University of Bucharest Academiei 14, sector 1, 010014 Bucharest, Romania. E-mail: serbanutav@gmail.com | Department of Computer Science University of Illinois at Urbana-Champaign 201 N. Goodwin, Urbana, IL 61801, USA. E-mail: tserban2@cs.uiuc.edu

Abstract: We deal with the notion of M-unambiguity [5] in connection with the Parikh matrix mapping introduced by Mateescu and others in [7]. 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 γ-property introduced by Salomaa in [15]. Also, the notion of M-unambiguity with respect to a word is defined in connection with the extended Parikh matrix morphism [16] 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 [17].

Keywords: Subword, scattered subword, Parikh matrix, ambiguity

Journal: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 265-283, 2006