The number of distinct subpalindromes in random words

DOI10.3233/FI-2016-1366MaRDI QIDQ4976404zbMATH OpenDBLPWikidataFDO

Authors Mikhail Rubinchik, Arseny M. Shur

Publication date 28 July 2017

Published in Fundamenta Informaticae (Search for Journal in Brave)

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

zbMATH Keywords

combinatorics on wordsexpectationpalindromesquare factors

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: We prove that a random word of length $n$ over a $k$-ary fixed alphabet contains, on expectation, $Theta(sqrtn)$ distinct palindromic factors. We study this number of factors, $E(n,k)$, in detail, showing that the limit $li{m}_{noinfty}E(n,k)/sqrtn$ does not exist for any $kge2$, $limin{f}_{noinfty}E(n,k)/sqrtn=Theta(1)$, and $limsu{p}_{noinfty}E(n,k)/sqrtn=Theta(sqrtk)$. Such a complicated behaviour stems from the asymmetry between the palindromes of even and odd length. We show that a similar, but much simpler, result on the expected number of squares in random words holds. We also provide some experimental data on the number of palindromic factors in random words.

Recommendations

• On the expected number of distinct gapped palindromic factors
• On the average number of regularities in a word
• Properties of palindromes in finite words
• Periods and borders of random words
• scientific article; zbMATH DE number 939777

Cited in

(12)

• Periods and borders of random words
• scientific article; zbMATH DE number 939777 (Why is no real title available?)
• On the average number of regularities in a word
• Density dichotomy in random words
• Arnoux-Rauzy substitutions and Palindrome words
• Borders, palindrome prefixes, and square prefixes
• On the palindromic decomposition of binary words
• Random palindromes: Multivariate generating function and Bernoulli density
• Upper bound for palindromic and factor complexity of rich words
• scientific article; zbMATH DE number 6439121 (Why is no real title available?)
• Tight tradeoffs for real-time approximation of longest palindromes in streams
• On the expected number of distinct gapped palindromic factors

This page was built for publication: The number of distinct subpalindromes in random words

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