Palindromes In Sturmian Strings

2010/02/24 by A. Karaman, Karaman, Ayse
Computer Science · #68R15 #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Natural Language Processing Techniques #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1002.4606

openalex publication_date 2010/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let p be a maximal palindrome in a Sturmian word s=ul₁pl₂v so that p is a palindrome and l₁pl₂ is not for letters l₁ and l₂. Let α(p,p') be a morphism mapping letters a and b respectively to a^pb and a^p'b, |p-p'|=1. In this paper, we characterize the palindromes in a Sturmian word and show that the number of maximal palindromes in a Sturmian word X= α(p,p')(Y) for finite Y and thus X is 2|X|-2|Y|. We show that the set of maximal palindromes in a finite Sturmian word X has the cardinality Σ i=1..n max(pi,p'i) where X is characterized by subsequent mappings of i=1..n.

Related

• A note on palindromic length of Sturmian sequences
• Words with many palindrome pair factors
• The palindromization map
• On Generating Binary Words Palindromically
• Palindromic length of words and morphisms in class P