Behavior of various complexity functions

DOI10.1016/j.tcs.2011.11.012zbMath1260.68312MaRDI QIDQ764361

Teturo Kamae

Publication date: 13 March 2012

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.11.012

zbMATH Keywords

subword complexity; uniform complexity; maximal pattern complexity; minimal pattern complexity

Mathematics Subject Classification ID

68R15: Combinatorics on words

68Q45: Formal languages and automata

37B40: Topological entropy

37B10: Symbolic dynamics

Related Items

Complexity of Leading Digit Sequences, Central sets generated by uniformly recurrent words, Maximal pattern complexity, dual system and pattern recognition, Three complexity functions

Cites Work

• Substitutions in dynamics, arithmetics and combinatorics
• Maximal pattern complexity, dual system and pattern recognition
• Combinatorial lemmas and applications to dynamics
• Uniform sets and complexity
• Super-stationary set, subword problem and the complexity
• Language structure of pattern Sturmian words
• Maximal pattern complexity of two-dimensional words
• Maximal pattern complexity of words over \(\ell\) letters
• Three complexity functions
• Partitions by congruent sets and optimal positions
• Uniform sets and super-stationary sets over general alphabets
• On maximal pattern complexity of some automatic words
• Sequence entropy and the maximal pattern complexity of infinite words
• Maximal pattern complexity for discrete systems