Quasiperiods of biinfinite words

DOI10.1016/J.EJC.2019.103046MaRDI QIDQ2297910zbMATH OpenOpenAlexWikidataFDO

Authors Florian Barbero, Guilhem Gamard, Anaël Grandjean

Publication date 20 February 2020

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: We study the notion of quasiperiodicity, in the sense of "coverability", for biinfinite words. All previous work about quasiperiodicity focused on right infinite words, but the passage to the biinfinite case could help to prove stronger results about quasiperiods of Sturmian words. We demonstrate this by showing that all biinfinite Sturmian words have infinitely many quasiperiods, which is not quite (but almost) true in the right infinite case, and giving a characterization of those quasiperiods. The main difference between right infinite and the biinfinite words is that, in the latter case, we might have several quasiperiods of the same length. This is not possible with right infinite words because a quasiperiod has to be a prefix of the word. We study in depth the relations between quasiperiods of the same length in a given biinfinite quasiperiodic word. This study gives enough information to allow to determine the set of quasiperiods of an arbitrary word.

Recommendations

• Determining sets of quasiperiods of infinite words
• Quasiperiods of infinite words
• Quasiperiodic Sturmian words and morphisms
• Coverability in two dimensions
• Quasiperiodic and Lyndon episturmian words

Cites work

• Algebraic combinatorics on words. With preface by Jean Berstel and Dominique Perrin.
• Coverability in two dimensions
• Determining sets of quasiperiods of infinite words
• Efficient detection of quasiperiodicities in strings
• scientific article; zbMATH DE number 5604107 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 1400047 (Why is no real title available?)
• Quasiperiodic and Lyndon episturmian words
• Quasiperiodic Sturmian words and morphisms
• Substitutions in dynamics, arithmetics and combinatorics
• Symbolic Dynamics II. Sturmian Trajectories

Cited in

(11)

• Quasi-periodic \(\beta\)-expansions and cut languages
• Infinite periodic words and almost nilpotent varieties
• Coverability and multi-scale coverability on infinite pictures
• scientific article; zbMATH DE number 1615295 (Why is no real title available?)
• Coverability in two dimensions
• Minimal critical exponent of quasiperiodic words
• Determining sets of quasiperiods of infinite words
• The Maximal Subword Complexity of Quasiperiodic Infinite Words
• Quasiperiods of infinite words
• Endomorphisms of words in a quiver
• Quasiperiodic Sturmian words and morphisms

This page was built for publication: Quasiperiods of biinfinite words

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