On the palindromic decomposition of binary words

MaRDI QIDQ4820798zbMATH OpenFDO

Authors Oleksandr Ravs'kyj

Publication date 1 October 2004

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

zbMATH Keywords

measure of symmetrypalindrome

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: We prove a precise formula for the minimal number K(n) such that every binary word of length $n$ can be divided into K(n) palindromes. Also we estimate the average number $olK(n)$ of palindromes composing a random binary word of the length n.

Recommendations

• Counter-intuitive answers to some questions concerning minimal-palindromic extensions of binary words
• On highly palindromic words
• Properties of palindromes in finite words
• Total palindrome complexity of finite words
• The number of distinct subpalindromes in random words

Cited in

(18)

• On words with the zero palindromic defect
• A regularity lemma and twins in words
• On a theorem concerning partially overlapping subpalindromes of a binary word
• Local symmetry dynamics in one-dimensional aperiodic lattices: a numerical study
• The number of binary rotation words
• A baba galamaga.
• Diverse Palindromic Factorization Is NP-complete
• Extreme Palindromes
• On palindromic factorization of words
• Diverse Palindromic Factorization is NP-Complete
• A new measure of asymmetry of binary words
• scientific article; zbMATH DE number 2123420 (Why is no real title available?)
• Prefix Reversals on Binary and Ternary Strings
• Smallest and Largest Block Palindrome Factorizations
• On some 2-binomial coefficients of binary words: geometrical interpretation, partitions of integers, and fair words
• Double-ended palindromic trees in linear time
• On highly palindromic words: the ternary case
• On binary palindromes of the form \(10^n\pm 1\)

This page was built for publication: On the palindromic decomposition of binary words

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