Fully bordered words

DOI10.1016/J.TCS.2016.10.020MaRDI QIDQ2358697zbMATH OpenOpenAlexFDO

Authors Štěpán Holub, Mike Müller

Publication date 15 June 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Lyndon wordspalindromesunbordered words

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: We characterize binary words that have exactly two unbordered conjugates and show that they can be expressed as a product of two palindromes.

Review text

The characterization of binary words that have exactly two unbordered conjugates in order to show that they can be expressed as a product of two palindromes, is very well treated in this paper. The introduction section is well presented and the paper is overall easy to understand. The background theory is fully connected to the given data and the method analysis. The structure of words that do not have any other unbordered conjugate apart from the two obligatory is examined, giving an inductive characterization of fully bordered words, which shows that they have some kind of fractal structure. So, every fully bordered word is a product of two palindromes. This result can also be interpreted in terms of saying that fully bordered words have palindromic length two. An extension of the above results is directly connected to the research on critical points of a word, which is a stronger concept than unbordered conjugate: the conjugate in the critical point is always unbordered, but not vice versa.

Recommendations

• Involutively bordered words
• Bordered conjugates of words over large alphabets
• A note of involutively bordered words
• Unbordered partial words
• Border correlations of partial words
• The perimeter of words
• Periods and borders of random words
• Border array on bounded alphabet
• Abelian borders in binary words
• Counting bordered partial words by critical positions

Cites work

• A proof of the extended Duval's conjecture
• Border correlation of binary words
• Density of Critical Factorizations
• On palindromic factorization of words
• Periodicity and unbordered words
• The Ehrenfeucht-Silberger problem

Cited in

(2)

• Prefix frequency of lost positions
• Border correlation of binary words

This page was built for publication: Fully bordered words

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