Decidability of irreducible tree shifts of finite type

DOI10.1007/s10955-019-02407-zzbMath1494.68188arXiv1910.13846OpenAlexW3102054923WikidataQ126981610 ScholiaQ126981610MaRDI QIDQ2283159

Chih-Hung Chang, Nai-Zhu Huang, Jung-Chao Ban, Yu-Liang Wu

Publication date: 30 December 2019

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1910.13846

zbMATH Keywords

irreduciblegraph representationcomplex prefix codestrongly periodic pointtree shift of finite type

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Prefix, length-variable, comma-free codes (94A45) Multidimensional shifts of finite type (37B51)

Related Items (3)

Decidability of CPC-irreducibility of subshifts of finite type over free groups ⋮ On mixing properties of Markov tree-shifts ⋮ Stem and topological entropy on Cayley trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sofic tree-shifts
• Cellular automata between sofic tree shifts
• Hardness of conjugacy, embedding and factorization of multidimensional subshifts
• Symbolic dynamics on free groups
• An aperiodic set of 13 Wang tiles
• A small aperiodic set of Wang tiles
• Symbolic dynamics. One-sided, two-sided and countable state Markov shifts
• Mixing properties for hom-shifts and the distance between walks on associated graphs
• Tree-shifts of finite type
• Automorphisms of \(\mathbb Z^ d\)-subshifts of finite type
• Classification of subshifts of finite type
• Undecidability and nonperiodicity for tilings of the plane
• Remarks on Berger's paper on the domino problem
• Projectional entropy and the electrical wire shift
• The topological strong spatial mixing property and new conditions for pressure approximation
• Matrix Subshifts for Z ^v Symbolic Dynamics
• The decomposition theorem for two-dimensional shifts of finite type
• The symbolic dynamics of multidimensional tiling systems
• Morphisms from non-periodic \mathbb{Z}^{2} subshifts I: constructing embeddings from homomorphisms
• Mixing properties of tree-shifts
• MINIMAL FORBIDDEN PATTERNS OF MULTI-DIMENSIONAL SHIFTS
• An Introduction to Symbolic Dynamics and Coding
• Multidimensional sofic shifts without separation and their factors
• Matrix Characterization of Multidimensional Subshifts of Finite Type
• Classification of sofic projective subdynamics of multidimensional shifts of finite type
• Tree-shifts: Irreducibility, mixing, and the chaos of tree-shifts
• Factoring higher-dimensional shifts of finite type onto the full shift
• The undecidability of the domino problem

This page was built for publication: Decidability of irreducible tree shifts of finite type