On the Injectivity of Parikh Matrix Mappings

Issue title: Contagious Creativity – In Honor of the 80th Birthday of Professor Solomon Marcus

Article type: Research Article

Authors: Salomaa, Arto

Affiliations: Turku Centre for Computer Science, Lemminkäisenkatu 14, 20520 Turku, Finland. asalomaa@it.utu.fi

Note: [] Address for correspondence: Turku Centre for Computer Science, Lemminkäisenkatu 14, 20520 Turku, Finland

Abstract: We investigate the number of (scattered) subword occurrences and Parikh matrices, especially the case where the matrix determines the word uniquely. A condition introduced in this paper, called γ-property, turns out to be a powerful tool for such unambiguous matrices. Interconnections with the general theory of subword histories are also pointed out.

Keywords: Subword, scattered subword, number of subwords, Parikh matrix, ambiguity

Journal: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 391-404, 2005