Computability of countable subshifts

DOI10.1007/978-3-642-13962-8_10MaRDI QIDQ3576194zbMATH OpenOpenAlexFDO

Authors Douglas Cenzer, Ali Dashti, Ferit Toska, Sebastian Wyman

Publication date 29 July 2010

Published in Programs, Proofs, Processes (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-13962-8_10

zbMATH Keywords

\(\Pi^0_1\) classescomputabilitysymbolic dynamics

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Computation over the reals, computable analysis (03D78) Symbolic dynamics (37B10)

Recommendations

• Computability of countable subshifts in one dimension
• Computable symbolic dynamics
• On the computability of the topological entropy of subshifts
• Constructions with countable subshifts of finite type
• Effective symbolic dynamics

Cited in

(15)

• The relationship between word complexity and computational complexity in subshifts
• Turing degree spectra of minimal subshifts
• \it \Pi^0_1 Sets and Tilings
• Undecidability of the Surjectivity of the Subshift Associated to a Turing Machine
• Conservatively approximable functions
• Computable symbolic dynamics
• Turing degrees of multidimensional SFTs
• Cototal enumeration degrees and their applications to effective mathematics
• Effective symbolic dynamics
• On derivatives and subpattern orders of countable subshifts
• A characterization of subshifts with computable language
• Two notes on subshifts
• Complexity of conjugacy, factoring and embedding for countable sofic shifts of rank 2
• Constructions with countable subshifts of finite type
• Computability of countable subshifts in one dimension

This page was built for publication: Computability of countable subshifts

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