Two notes on subshifts

DOI10.1090/S0002-9939-2011-11000-1zbMath1246.37025MaRDI QIDQ5390213

Joseph S. Miller

Publication date: 27 April 2012

Published in: Proceedings of the American Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

Kolmogorov complexitysubshiftseffectively closed subshiftavoidable sequencelength of forbidden words

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Symbolic dynamics (37B10) Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32)

Related Items

Doubled patterns are 3-avoidable ⋮ Shift-complex sequences ⋮ Computability in Symbolic Dynamics ⋮ Turing degree spectra of minimal subshifts ⋮ Finitely presented expansions of computably enumerable semigroups ⋮ Classifying word problems of finitely generated algebras via computable reducibility ⋮ Entropy bounds for multi-word perturbations of subshifts ⋮ Finitely presented expansions of groups, semigroups, and algebras ⋮ The relationship between word complexity and computational complexity in subshifts ⋮ Medvedev degrees of two-dimensional subshifts of finite type ⋮ Computability of countable subshifts in one dimension ⋮ On computably enumerable structures ⋮ Compressibility and probabilistic proofs ⋮ Automatic Sequences and Generalised Polynomials ⋮ On subshifts with slow forbidden word growth

Cites Work

• Unnamed Item
• Unnamed Item
• Complex tilings
• An Introduction to Symbolic Dynamics and Coding
• Effective Symbolic Dynamics
• Complex tilings
• Medvedev degrees of two-dimensional subshifts of finite type
• Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: Two notes on subshifts