IMSc Webinar

Palindromes in 1D and 2D words

Palak Pandoh

IIT Madras

Identification of palindromes, i.e., words that are symmetric under reversal, have applications to string processing, bioinformatics, error correcting
codes, etc. A word is a Watson-Crick (WK) palindrome when the complement of its reverse is equal to itself. It was introduced to study palindromes from the perspective of DNA computing. WK mapping is an antimorphic involution. WK-conjugates of a word is a generalisation of conjugates of a word that incorporates the notion of WK-involution. We investigate scattered palindromic subwords in finite words. We study the distribution of palindromes and WK-palindromes among both the set of conjugates and WK-conjugates of a word. Two-dimensional palindromes were introduced in order to characterize 2D Sturmian words in terms of 2D palindromes. Due to their highly symmetric nature, 2D palindromes have applications in data compression, face recognition, pattern recognition, etc. We enumerate 2D palindromic factors in two-dimensional periodic and aperiodic words.