BLOCK INVERSION ON ${\wp}$WORDS WITH
ZERO PALINDROMIC DEFECT

R. Krishna Kumari1, K. Janaki2, R. Arulprakasam3
1 Career Development Centre
College of Engineering and Technology
SRM Institute of Science and Technology
Kattankulathur-603203, Tamilnadu, INDIA
2 Department of Mathematics
Saveetha Engineering College
Saveetha Nagar, Thandalam
Chennai-602105, Tamilnadu, INDIA
3 Department of Mathematics
College of Engineering and Technology
SRM Institute of Science and Technology
Kattankulathur-603203, Tamilnadu, INDIA

Abstract

The role of ${\wp}$words and inversions in molecular biology led to a unified study of inversions on ${\wp}$words. In this paper, we use a generalization of the concept of inversion termed as block inversion on finite rich ${\wp}$words. A comparison of block inversion on finite total words and on finite ${\wp}$words is made. We conclude that the total number of ${\wp}$words in the block inversion set of a finite rich ${\wp}$word of length $n$ is strictly less than $2^{n-1}$.

Citation details of the article



Journal: International Journal of Applied Mathematics
Journal ISSN (Print): ISSN 1311-1728
Journal ISSN (Electronic): ISSN 1314-8060
Volume: 36
Issue: 5
Year: 2023

DOI: 10.12732/ijam.v36i5.4

Download Section



Download the full text of article from here.

You will need Adobe Acrobat reader. For more information and free download of the reader, please follow this link.

References

  1. [1] J. Berstel and L. Boasson, Partial words and a theorem of Fine and Wilf, Theor. Comput. Sci., 218, No 1 (1999), 135–141.
  2. [2] F. Blanchet-Sadri, Primitive partial words, Discrete Applied Mathematics, 148 (2005), 195–213.
  3. [3] F. Blanchet-Sadri, Algorithmic Combinatorics on Partial Words, Discrete Mathematics and its Applications, CRC Press (2008).
  4. [4] D.J. Cho, Y.S. Han, S.D. Kang, H. Kim, S.K. Ko and K. Salomaa, Pseudoinversion on formal languages, Proceedings of the Unconventional Computation and Natural Computation (2014), 93–104.
  5. [5] M. Daley, O.H. Ibarra and L. Kari, Closure and decidability properties of some language classes with respect to ciliate bio-operations, Theor. Comput. Sci., 306, No 1 (2003), 19–38.
  6. [6] M. Daley, L. Kari and I. McQuillan, Families of languages defined by ciliate bio-operations, Theor. Comput. Sci., 320, No 1 (2004), 51–69.
  7. [7] J. Dassow, V. Mitrana and A. Salomaa, Operations and language generating devices suggested by the genome evolution, Theor. Comput. Sci., 270, No 1 (2002), 701–738.
  8. [8] M.J. Fischer and M.S. Paterson, String matching and other products, In: Karp, R.M. (ed.) Complexity of Computation. SIAM-AMS Proceedings (1974), 113-125.
  9. [9] K. Goto, I. Tomohiro, H. Bannai and S. Inenaga, Block palindromes: a new generalization of palindromes, String Processing and Information Retrieval, Springer International Publishing, Cham, (2018), 183–190.
  10. [10] S. Heubach and T. Mansour, Combinatorics of Compositions and Words, Discrete Mathematics and its Applications, CRC Press (2009).
  11. [11] O.H. Ibarra, On decidability and closure properties of language classes with respect to bio-operations, Proceedings of the 20th International Conference on DNA Computing and Molecular Programming (2014), 148–160.
  12. [12] H. Kim and Y.S. Han, Non-overlapping inversion on strings and languages, Theor. Comput. Sci., 592 (2015), 9–22.
  13. [13] R. Krishna Kumari, R. Arulprakasam, P. Meenakshi and V.R. Dare, Circular partial words and arrays, Proceedings of the International Symposium on Artificial Intelligence and Mathematics 2022 (ISAIM 2022), Fort Lauderdale, Florida, USA, 2022.
  14. [14] R. Krishna Kumari, R. Arulprakasam and V.R. Dare, Combinatorial properties of Fibonacci partial words and arrays, Journal of Discrete Mathematical Sciences and Cryptography, 24, No 4 (2021), 1007-1020.
  15. [15] L. Heged s and B. Nagy, Representations of circular words. Proceedings 14th International Conference on Automata and Formal Languages, AFL 2014, Szeged, Hungary, 151 (2014), 261–270.
  16. [16] M. Lothaire, Combinatorics on Words, Cambridge University Press, 1983.
  17. [17] K. Mahalingam, A. Maity, P. Pandoh and R. Raghavan, Block reversal on finite words, Theoret. Comput.Sci., Preprint (2021).
  18. [18] B. Rittaud, L. Vivier, Circular words and Applications, Proceedings of Words 2011, Electronic Proceedings in Theoret. Comput.Sci., 63 (2011), 31–36.
  19. [19] M. Schoniger, M. Waterman, A local algorithm for DNA sequence alignment with inversions, Bull. Math. Biol., 54 (1992), 521–536.