×

Extension of Parikh matrices to terms and its injectivity problem. (English) Zbl 1434.68381

Summary: Parikh matrices introduced by A. Mateescu et al. [Theor. Inform. Appl. 35, No. 6, 551–564 (2001; Zbl 1005.68092)] are very useful in understanding structural properties of words by analyzing their numerical properties. This is due to the information of a word provided by its Parikh matrix is more than its Parikh vector. The study of Parikh matrices is extended in this paper to terms formed over a signature with a binary underlying alphabet. We obtain some numerical properties that characterize when a word is a term. Finally, new \(M\)-equivalence preserving rewriting rules are introduced and shown to characterize \(M\)-equivalence for our terms, thus contributing towards the injectivity problem.

MSC:

68R15 Combinatorics on words
05A05 Permutations, words, matrices

Citations:

Zbl 1005.68092
PDFBibTeX XMLCite
Full Text: Link