Borders, palindrome prefixes, and square prefixes

DOI10.1016/J.IPL.2020.106027MaRDI QIDQ2224845zbMATH OpenOpenAlexFDO

Authors Daniel Gabric, Jeffrey Shallit

Publication date 4 February 2021

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

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

zbMATH Keywords

enumerationformal languagescombinatorial problemsbordered wordpalindrome prefix

Mathematics Subject Classification ID

Combinatorics on words (68R15)

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.

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

Cites work

• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3409617 (Why is no real title available?)
• scientific article; zbMATH DE number 3052800 (Why is no real title available?)
• A note on bifix-free sequences (Corresp.)
• Counting the palstars
• Equations on palindromes and circular words
• Inverse star, borders, and palstars
• On Curling Numbers of Integer Sequences
• Periodicity and unbordered segments of words
• Periods and borders of random words
• The equation \(a_ M=b^ Nc^ P\) in a free group

Cited in

(1)

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

Describes a project that uses

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)