Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences

DOI10.1007/11672142_32zbMath1136.68473arXiv1009.4455OpenAlexW1582077892MaRDI QIDQ5449816

A. Yu. Rumyantsev, M. A. Ushakov

Publication date: 19 March 2008

Published in: STACS 2006 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts ⋮ Shift-complex sequences ⋮ Computability in Symbolic Dynamics ⋮ Seas of squares with sizes from a \(\Pi_{1}^{0}\) set ⋮ Fixed-point tile sets and their applications ⋮ Two notes on subshifts ⋮ \(\mu\)-limit sets of cellular automata from a computational complexity perspective ⋮ Kolmogorov Complexity as a Language ⋮ Effective Closed Subshifts in 1D Can Be Implemented in 2D ⋮ Compressibility and probabilistic proofs ⋮ The expressiveness of quasiperiodic and minimal shifts of finite type ⋮ Asymptotic Cellular Complexity ⋮ On the Expressive Power of Quasiperiodic SFT.