Words with unbounded periodicity complexity

DOI10.1142/S0218196714500362MaRDI QIDQ2934268zbMATH OpenOpenAlexFDO

Authors Štěpán Holub

Publication date 12 December 2014

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

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

zbMATH Keywords

combinatorics on wordsperiodicity complexity

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: If an infinite non-periodic word is uniformly recurrent or is of bounded repetition, then the limit of its periodicity complexity is infinity. Moreover, there are uniformly recurrent words with the periodicity complexity arbitrarily high at infinitely many positions.

Recommendations

• A new complexity function for words based on periodicity
• Sequence entropy and the maximal pattern complexity of infinite words
• scientific article; zbMATH DE number 1223721
• Topological invariants for words of linear factor complexity
• Locally periodic versus globally periodic infinite words

Cites work

• A characterization of substitutive sequences using return words
• A new complexity function for words based on periodicity
• Complexity of Toeplitz sequences
• Toeplitz words, generalized periodicity and periodically iterated morphisms
• Two-way string-matching

Cited in

(14)

• Words whose complexity satisfies lim \(\frac{p(n)}{n} = 1\).
• Locally periodic versus globally periodic infinite words
• On non-repetitive complexity of Arnoux-Rauzy words
• A characterization of eventual periodicity
• Topological invariants for words of linear factor complexity
• A new complexity function for words based on periodicity
• Cyclic Complexity of Words
• Unavoidable regularities in long words with bounded number of symbol occurrences
• scientific article; zbMATH DE number 1223721 (Why is no real title available?)
• scientific article; zbMATH DE number 1948496 (Why is no real title available?)
• On the complexity function for sequences which are not uniformly recurrent
• Recurrence and periodicity in infinite words from local periods
• Word of low complexity without uniform frequencies
• New string attractor-based complexities for infinite words

This page was built for publication: Words with unbounded periodicity complexity

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