A characterization of subshifts with computable language

DOI10.4230/LIPICS.STACS.2019.40MaRDI QIDQ5090490FDOQ5090490

Authors: Emmanuel Jeandel, Pascal Vanier 

Publication date: 18 July 2022

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

zbMATH Keywords

computabilitysubshiftsTuring degreeenumeration degreeminimal subshifts

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

Cited In (3)

• Graph subshifts
• Recoding Lie algebraic subshifts
• Self-avoiding walks on Cayley graphs through the lens of symbolic dynamics

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)