Parikh Matrices and Parikh Rewriting Systems

Article type: Research Article

Authors: Teh, Wen Chean^*

Affiliations: School of Mathematical Sciences, Universiti Sains Malaysia, 11800 USM, Malaysia. [email protected]

Correspondence: [*] Address for correspondence: School of Mathematical Sciences, Universiti Sains Malaysia, 11800 USM, Malaysia. Supported by the short term grant No. 304/PMATHS/6313077 of Universiti Sains Malaysia.

Abstract: Since the introduction of the Parikh matrix mapping, its injectivity problem is on top of the list of open problems in this topic. In 2010 Salomaa provided a solution for the ternary alphabet in terms of a Thue system with an additional feature called counter. This paper proposes the notion of a Parikh rewriting system as a generalization and systematization of Salomaa’s result. It will be shown that every Parikh rewriting system induces a Thue system without counters that serves as a feasible solution to the injectivity problem.

Keywords: Parikh matrix, subword, injectivity problem, Parikh rewriting system, M-equivalence

DOI: 10.3233/FI-2016-1388

Journal: Fundamenta Informaticae, vol. 146, no. 3, pp. 305-320, 2016