Decidability of irreducible tree shifts of finite type

DOI10.1007/S10955-019-02407-ZzbMATH Open1494.68188arXiv1910.13846OpenAlexW3102054923WikidataQ126981610 ScholiaQ126981610MaRDI QIDQ2283159FDOQ2283159

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)

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.

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

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

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)

Cites Work

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

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)