×

Parikh \(q\)-matrices and \(q\)-ambiguous words. (English) Zbl 1430.68252

Summary: The Parikh matrix mapping plays an important role in the study of words through numerical properties. The Parikh \(q\)-matrix mapping, introduced by [Ö. Eğecioğlu and O. H. Ibarra, “A \(q\)-analogue of the Parikh matrix mapping”, in: K. G. Subramanian (ed.) et al., Formal models, languages and applications. Hackensack, NJ: World Scientific. 97–111 (2006; doi:10.1142/9789812773036_0007)] as an extension of the Parikh matrix mapping, maps words to matrices with polynomial entries in \(q \). A word \(w\) over an ordered alphabet \(\Sigma\) is said to be \(q\)-ambiguous if there exists another word \(v\) over \(\Sigma\) such that both the words have same Parikh \(q\)-matrix. Here, we derive several properties of \(q\)-ambiguous words, in particular, for a binary alphabet.

MSC:

68R15 Combinatorics on words

Citations:

Zbl 1138.68434
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Atanasiu, A., Binary amiable words, International Journal of Foundations of Computer Science18(2) (2007) 387-400. · Zbl 1123.68097
[2] Atanasiu, A., Atanasiu, R. and Petre, I., Parikh matrices and amiable words, Theoretical Computer Science390(1) (2008) 102-109. · Zbl 1134.68027
[3] Atanasiu, A., Martin-Vide, C. and Mateescu, A., On the injectivity of the Parikh matrix mapping, Fundamenta Informaticae49(4) (2002) 289-299. · Zbl 0997.68075
[4] Bera, S. and Mahalingam, K., Some algebraic aspects of Parikh \(q\)-matrices, International Journal of Foundation of Computer Science27(4) (2016) 479-499. · Zbl 1371.68140
[5] Egecioglu, O. and Ibarra, O. H., A \(q\)-analogue of the Parikh Matrix Mapping, Formal Models, Languages and Applications, Series in Machine Perception and Artificial Intelligence, World Scientific66 (2006) 97-111. · Zbl 1138.68434
[6] Fosse, S. and Richomme, G., Some characterizations of Parikh matrix equivalent binary words, Information Processing Letters92(2) (2004) 77-82. · Zbl 1173.68550
[7] Lothaire, M., Combinatorics on Words (Addison-Wesley, USA, 1983). · Zbl 0514.20045
[8] Mateescu, A. and Salomaa, A., Matrix indicators for subword occurrences and ambiguity, International Journal of Foundations of Computer Science15(2) (2004) 277-292. · Zbl 1067.68117
[9] Mateescu, A.et al., A sharpening of the Parikh Mapping, Theoretical Informatics and Applications35(6) (2001) 551-564. · Zbl 1005.68092
[10] Parikh, R. J., On context-free languages, Journal of the Association for Computing Machinery4 (1966) 570-581. · Zbl 0154.25801
[11] Salomaa, A., On the injectivity of Parikh matrix mappings, Fundamenta Informatica64(1-4) (2005) 391-404. · Zbl 1102.68072
[12] Salomaa, A., Subword balance, position indices and power sums, Journal of Computer and System Sciences76(8) (2010) 861-871. · Zbl 1215.68123
[13] Serbanuta, V. N. and Serbanuta, T. F., Injectivity of the Parikh matrix mappings revisited, Fundamenta Informatica73(1-2) (2006) 265-283. · Zbl 1104.68058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.