Two notes on subshifts

DOI10.1090/S0002-9939-2011-11000-1MaRDI QIDQ5390213zbMATH OpenFDO

Authors Joseph S. Miller

Publication date 27 April 2012

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

Full work available at URL https://doi.org/10.1090/S0002-9939-2011-11000-1

zbMATH Keywords

avoidable sequenceeffectively closed subshiftKolmogorov complexitylength of forbidden wordssubshifts

Mathematics Subject Classification ID

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

Recommendations

• Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences
• Computability of countable subshifts
• Computability of countable subshifts in one dimension
• The relationship between word complexity and computational complexity in subshifts
• Shifts with decidable language and non-computable entropy

Cites work

• An introduction to Kolmogorov complexity and its applications
• An Introduction to Symbolic Dynamics and Coding
• Complex tilings
• Complex tilings
• Computability and randomness
• Effective symbolic dynamics
• Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• Medvedev degrees of two-dimensional subshifts of finite type

Cited in

(21)

• Finitely presented expansions of computably enumerable semigroups
• The relationship between word complexity and computational complexity in subshifts
• Compressibility and probabilistic proofs
• On computably enumerable structures
• Turing degree spectra of minimal subshifts
• Doubled patterns are 3-avoidable
• On subshift presentations
• Computability in Symbolic Dynamics
• A characterization of subshifts with computable language
• Automatic sequences and generalised polynomials
• Shift-complex sequences
• Finitely presented expansions of groups, semigroups, and algebras
• Medvedev degrees of two-dimensional subshifts of finite type
• On subshifts with slow forbidden word growth
• Classifying word problems of finitely generated algebras via computable reducibility
• Entropy bounds for multi-word perturbations of subshifts
• Self-simulable groups
• Translation-like actions by \(\mathbb{Z} \), the subgroup membership problem, and Medvedev degrees of effective subshifts
• Finding lower bounds on the growth and entropy of subshifts over countable groups
• Computability of countable subshifts in one dimension
• Dimensionality and randomness

This page was built for publication: Two notes on subshifts

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