Properties of Subwords of Binary Words under Dejean morphism

Articles in Press

Document Type : Special Issue for ICGTA23

Authors

1 Vellore Institute of Technology Chennai, Department of Mathematics, School of Advanced Sciences, Chennai 600036 India

2 Department of Mathematics, Rajalakshmi Engineering College, Thandalam, Chennai 602 105 India

3 Department of Mathematics, Government Arts College, Dharmapuri, Tamil Nadu, 636 705 India

4 Department of Mathematics, Computer Science and Engineering, Liverpool Hope University, Liverpool L16 9JD U.K.

Abstract

A word w is a finite sequence of symbols belonging to a finite set, called an alphabet. A scattered subword of a word w is a subsequence of w. The Parikh matrix of a word w over an ordered alphabet with an ordering on its elements, is an upper triangular matrix with its entries giving the counts of different occurrences of certain scattered subwords in the word w. Based on the notions of scattered subword and Parikh matrix, several properties of images of words under morphisms have been established. Here we consider Dejean morphism on three letters and derive several properties for images of binary words under this morphism in the context of Parikh matrices.

Keywords

Main Subjects

References

[1] A. Atanasiu, Morphisms on amiable words, Annals of Bucharest University 59 (2010), 99–111.
[2] A. Atanasiu, Parikh matrices, amiability and istrail morphism, Int. J. Found. Comput. Sci. 21 (2010), no. 06, 1021–1033.
https://doi.org/10.1142/S0129054110007702
[3] A. Atanasiu, K. Mahalingam, and K.G. Subramanian, Morphisms and weak-ratio property, 11 2014, pp. 13–21.
[4] J. Berstel, Axel Thue’s Papers on Repetitions in Words: a Translation, vol. 20, Départements de mathématiques et d’informatique, Université du Québec à Montréal, 1995.
[5] J. Berstel and D. Perrin, The origins of combinatorics on words, European J. Combin. 28 (2007), no. 3, 996–1022.
https://doi.org/10.1016/j.ejc.2005.07.019
[6] F.J. Brandenburg, Uniformly growing $k$-th power-free homomorphisms, Theor. Comput. Sci. 23 (1988), no. 1, 69–82.
https://doi.org/10.1016/0304-3975(88)90009-6
[7] W. Chean Teh, Separability of M-equivalent words by morphisms, Int. J. Found. Comput. Sci. 27 (2016), no. 1, 39–52.
https://doi.org/10.1142/S0129054116500039
[8] F. Dejean, Sur un théoreme de thue, J. Comb. Theory Ser. A. 13 (1972), no. 1, 90–99. https://doi.org/10.1016/0097-3165(72)90011-8
[9] P. Isawasan, I. Venkat, K.G. Subramanian, and N.H. Sarmin, Morphic images of binary words and parikh matrices, AIP Conf. Proc. 1605 (2014), no. 1, 708–713. https://doi.org/10.1063/1.4887676
[10] L. Kari and K. Mahalingam, Involutively bordered words, Int. J. Found. Comput. Sci. 18 (2007), no. 05, 1089–1106.
https://doi.org/10.1142/S0129054107005145
[11] M. Lothaire, Combinatorics on Words, 2 ed., Cambridge University Press, Cambridge, 1997.
[12] K. Mahalingam and K.G. Subramanian, Product of parikh matrices and commutativity, Int. J. Found. Comput. Sci. 23 (2012), no. 1, 207–223. https://doi.org/10.1142/S0129054112500049
[13] A. Mateescu, Algebraic aspects of parikh matrices, Theory Is Forever: Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday (J. Karhumāki, H. Maurer, G. Päun, and G. Rozenberg, eds.), Springer Berlin Heidelberg, Berlin, Heidelberg, 2004, pp. 170–180. https://doi.org/10.1007/978-3-540-27812-2 16
[14] A. Mateescu, A. Salomaa, K. Salomaa, and S. Yu, A sharpening of the Parikh mapping, RAIRO - Theor. Inform. Appl. 35 (2001), no. 6, 551–564. https://doi.org/10.1051/ita:2001131
[15] G. Rozenberg and A. Salomaa, Handbook of Formal Languages: Volume 3 Beyond Words, Springer Science & Business Media, 2012.
[16] P. Séébold, Sequences generated by infinitely iterated morphisms, Discret. Appl. Math. 11 (1985), no. 3, 255–264.
https://doi.org/10.1016/0166-218X(85)90077-0
[17] P. Séébold, Lyndon factorization of the prouhet words, Theor. Comput. Sci. 307 (2003), no. 1, 179–197. https://doi.org/10.1016/S0304-3975(03)00100-2
[18] P. Séébold, On some generalizations of the Thue–Morse morphism, Theor. Comput. Sci. 292 (2003), no. 1, 283–298. https://doi.org/10.1016/S0304-3975(01)00228-6
[19] K.G. Subramanian, On prouhet morphisms and Parikh matrices, The 4th Int. Conf. Math. Sci., Universiti Kebangsaan Malaysia, 2016.
[20] K.G. Subramanian, A.M. Huey, and A.K. Nagar, On Parikh matrices, Int. J. Found. Comput. Sci. 20 (2009), no. 2, 211–219. https://doi.org/10.1142/S0129054109006528
[21] K.G. Subramanian, P. Isawasan, I. Venkat, and A.T. Khader, Parikh matrices of words under a generalized Thue morphism, AIP Conf. Proc. 1558 (2013), no. 1, 2516–2519. https://doi.org/10.1063/1.4826052
[22] K.G. Subramanian, P. Isawasan, I. Venkat, and A.T. Khader, Parikh matrices of words under a generalized Thue morphism, AIP Conf. Proc. 1558 (2013), no. 1, 2516–2519. https://doi.org/10.1063/1.4826052
[23] K.G. Subramanian, A. Nagar, and S. Sriram, Parikh matrices of binary and Ternary words under prouhet morphism, Int. J. Math. Comb. 1 (2018), 78–88.
[24] K.G. Subramanian, S. Sriram, and A.S. Prasanna Venkatesan, Parikh matrix of a word under Dejean morphism, 13th Annual ADMA Conference and Graph Theory Day-XIII, India, 2017.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 23 November 2025

Files

Share

How to cite

Statistics