Complexity of infinite words

DOI10.1007/978-3-031-81202-6_1MaRDI QIDQ6996906zbMATH OpenFDO

Authors Svetlana Puzynina

Publication date 15 April 2025

Full work available at URL https://doi.org/10.1007/978-3-031-81202-6_1

zbMATH Keywords

complexity of infinite wordsMorse and Hedlund theoremSturmian words

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Cites work

• A lower bound for the arithmetical complexity of Sturmian words
• Abelian combinatorics on words: a survey
• Abelian complexity of minimal subshifts
• Abelian maximal pattern complexity of words
• An algebraic geometric approach to Nivat's conjecture
• Aperiodic two-dimensional words of small abelian complexity
• Asymptotic abelian complexities of certain morphic binary words
• AVOIDING ABELIAN POWERS IN BINARY WORDS WITH BOUNDED ABELIAN COMPLEXITY
• Balance and abelian complexity of the Tribonacci word
• Balances for fixed points of primitive substitutions.
• Complexité des facteurs des mots infinis engendrés par morphismes itérés
• Complexity of short rectangles and periodicity
• Cyclic complexity of words
• Decidability and periodicity of low complexity tilings
• Factor complexity
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• Maximal pattern complexity for discrete systems
• Maximal pattern complexity of words over \(\ell\) letters
• Multidimensional extension of the Morse-Hedlund theorem
• Nonexpansive \(\mathbb{Z}^{2}\)-subdynamics and Nivat's conjecture
• On a generalization of abelian equivalence and complexity of infinite words
• On Context-Free Languages
• On the arithmetical complexity of Sturmian words
• On the asymptotic abelian complexity of morphic words
• Recurrent words with constant abelian complexity
• Sequence entropy and the maximal pattern complexity of infinite words
• Sequences of linear arithmetical complexity
• Sequences of low arithmetical complexity
• Sequences with minimal block growth
• Sturmian words: structure, combinatorics, and their arithmetics
• Symbolic dynamics II. Sturmian trajectories.
• Symbolic dynamics.
• The rectangle complexity of functions on two-dimensional lattices
• Transcendence of numbers with a low complexity expansion
• Ultimately constant abelian complexity of infinite words
• Variations of the Morse-Hedlund theorem for \(k\)-abelian equivalence

This page was built for publication: Complexity of infinite words

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