A characterization of subshifts with computable language

DOI10.4230/LIPICS.STACS.2019.40MaRDI QIDQ5090490zbMATH OpenFDO

Authors Emmanuel Jeandel, Pascal Vanier

Publication date 18 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2019.40

zbMATH Keywords

computabilityenumeration degreeminimal subshiftssubshiftsTuring degree

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Two notes on subshifts
• Shifts with decidable language and non-computable entropy
• scientific article; zbMATH DE number 3911734
• Computability of countable subshifts
• Hardness of conjugacy, embedding and factorization of multidimensional subshifts

Cites work

• A characterization of the entropies of multidimensional shifts of finite type
• An algebraic characterization of groups with soluble word problem
• An order on sets of tilings corresponding to an order on languages
• Bounded enumeration reducibility and its degree structure
• Characterizations of periods of multi-dimensional shifts
• Combinatorial algebra: syntax and semantics. With contributions by Victor S. Guba and Mikhail V. Volkov
• Combinatorial group theory.
• Effective closed subshifts in 1D can be implemented in 2D
• Enumeration reducibility in closure spaces with applications to logic and algebra
• Factoring higher-dimensional shifts of finite type onto the full shift
• Finite Axiomatizability using additional predicates
• Fixed-point tile sets and their applications
• scientific article; zbMATH DE number 3670685 (Why is no real title available?)
• scientific article; zbMATH DE number 193180 (Why is no real title available?)
• scientific article; zbMATH DE number 3074067 (Why is no real title available?)
• Mass problems associated with effectively closed sets
• Multidimensional sofic shifts without separation and their factors
• On the dynamics and recursive properties of multidimensional symbolic systems
• On the expressive power of quasiperiodic SFT
• On the topological full group of a minimal Cantor Z^2-system
• Reducibility and Completeness for Sets of Integers
• Simulation of effective subshifts by two-dimensional subshifts of finite type
• Subgroups of finitely presented groups
• The undecidability of the domino problem

Cited in

(5)

• Recoding Lie algebraic subshifts
• Cutting corners
• Graph subshifts
• Self-avoiding walks on Cayley graphs through the lens of symbolic dynamics
• On a Rice theorem for dynamical properties of SFTs on groups

This page was built for publication: A characterization of subshifts with computable language

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