Uniform sets and complexity

DOI10.1016/j.disc.2008.10.001zbMath1204.68150MaRDI QIDQ1043538

Teturo Kamae

Publication date: 9 December 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.10.001

zbMATH Keywords

complexity; optimal position; super-stationary set; uniform set

Mathematics Subject Classification ID

68R15: Combinatorics on words

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Maximal pattern complexity, dual system and pattern recognition, Behavior of various complexity functions, Super-stationary set, subword problem and the complexity, Three complexity functions, Partitions by congruent sets and optimal positions, Uniform sets and super-stationary sets over general alphabets

Cites Work

• Sequences of linear arithmetical complexity
• Substitutions in dynamics, arithmetics and combinatorics
• Super-stationary set, subword problem and the complexity
• Complexity of sequences and dynamical systems
• Toeplitz words, generalized periodicity and periodically iterated morphisms
• Complexity of Toeplitz sequences
• Elemental methods in ergodic Ramsey theory
• Language structure of pattern Sturmian words
• Maximal pattern complexity of two-dimensional words
• On the density of families of sets
• Maximal pattern complexity of words over \(\ell\) letters
• Sequence entropy and the maximal pattern complexity of infinite words
• Maximal pattern complexity for discrete systems