Borders, palindrome prefixes, and square prefixes

DOI10.1016/J.IPL.2020.106027zbMATH Open1506.68087arXiv1906.03689OpenAlexW3087550749MaRDI QIDQ2224845FDOQ2224845

Authors: Daniel Gabric, Jeffrey Shallit 

Publication date: 4 February 2021

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: We show that the number of length-n words over a k-letter alphabet having no even palindromic prefix is the same as the number of length-n unbordered words, by constructing an explicit bijection between the two sets. A slightly different but analogous result holds for those words having no odd palindromic prefix. Using known results on borders, we get an asymptotic enumeration for the number of words having no even (resp., odd) palindromic prefix . We obtain an analogous result for words having no nontrivial palindromic prefix. Finally, we obtain similar results for words having no square prefix, thus proving a 2013 conjecture of Chaffin, Linderman, Sloane, and Wilks.

Full work available at URL: https://arxiv.org/abs/1906.03689

Recommendations

• scientific article; zbMATH DE number 3842140
• The number of distinct subpalindromes in random words
• Palindromic prefixes and episturmian words
• Prefix palindromic length of the Thue-Morse word
• On prefix palindromic length of automatic words

zbMATH Keywords

enumerationformal languagescombinatorial problemsbordered wordpalindrome prefix

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• Title not available (Why is that?)
• The equation \(a_ M=b^ Nc^ P\) in a free group
• A note on bifix-free sequences (Corresp.)
• Equations on palindromes and circular words
• Periodicity and unbordered segments of words
• Inverse star, borders, and palstars
• Counting the palstars
• Title not available (Why is that?)
• Title not available (Why is that?)
• Periods and borders of random words
• On Curling Numbers of Integer Sequences

Cited In (1)

• Enumeration of bordered words, le langage de la vache-qui-rit

Uses Software

• OEIS

This page was built for publication: Borders, palindrome prefixes, and square prefixes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2224845)