Decidability of irreducible tree shifts of finite type

DOI10.1007/S10955-019-02407-ZMaRDI QIDQ2283159zbMATH OpenOpenAlexWikidataFDO

Authors Jung-Chao Ban, Chih-Hung Chang, Nai-Zhu Huang, 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

graph representationirreduciblecomplex 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)

Abstract: We reveal an algorithm for determining the complete prefix code irreducibility (CPC-irreducibility) of dyadic trees labeled by a finite alphabet. By introducing an extended directed graph representation of tree shift of finite type (TSFT), we show that the CPC-irreducibility of TSFTs is related to the connectivity of its graph representation, which is a similar result to one-dimensional shifts of finite type.

Recommendations

• Decidability of CPC-irreducibility of subshifts of finite type over free groups
• Decidability of Conjugacy of Tree-Shifts of Finite Type
• Sofic and almost of finite type tree-shifts
• Tree-shifts of finite type
• Sofic tree-shifts

Cites work

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

Cited in

(6)

• On mixing properties of Markov tree-shifts
• Classes of Tree Homomorphisms with Decidable Preservation of Regularity
• Decidability of Conjugacy of Tree-Shifts of Finite Type
• -adic characterization of minimal ternary dendric shifts
• Stem and topological entropy on Cayley trees
• Decidability of CPC-irreducibility of subshifts of finite type over free groups

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

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