Characterization and topological behavior of homomorphism tree-shifts (Q2230907): Difference between revisions

Let \(\mathcal{A}\) be a finite alphabet. A pattern on \(\mathbb{Z}^{d}\) over \(\mathcal{A}\) is a function from a finite subset of \(\mathbb{Z}^{d}\) to \(\mathcal{A}\). Let \(M_n(\{0, 1\})\) be the set of \(n \times n\) binary matrices, and \(A \in M_n(\{0,1\})\) be given. The set \(\mathcal{T}_A := \{t\in \mathcal{A}^{T}: A(t_w, t_{ws}) = 1\ \text{for}\ w \in T\ \text{and}\ s\in\Sigma\}\) is called a hom tree-SFT, where \(T\) is the free monoid generated by \(\Sigma=\{0, 1, \cdots, k - 1\}\). The authors are interested in the problem of equivalence of shifts of finite type (SFT), in particular between a one-sided shift \(X\) and its associated hom tree-shift \(\mathcal{T}_X\). Here \(X\subset \mathcal{A}^{\mathbb{Z}_+}\) is a one-dimensional shift and the hom tree-shift \(\mathcal{T}_X\) is defined by \[ \mathcal{T}_X := \{t\in \mathcal{A}^{T} : (t_{w_1w_2...w_i })_{i\in \mathbb{Z}_+}\in X\ \text{for any sequence}\ (w_i)_{i\in\mathbb{Z}_+}\ \text{in}\ \Sigma\}.\] The authors investigate the topological relations between \(X\) and \(\mathcal{T}_X\). Suppose that \(X\) is a shift space. In this case, it is proved that: (1) \(X\) is a SFT if and only if \(\mathcal{T}_X\) is a tree-SFT; (2) \(X\) is a sofic shift if and only if \(\mathcal{T}_X\) is a sofic tree-shift. Then, the authors study the interplay among the comparable mixing properties on tree-shifts as those on multidimensional shift spaces. The comparable mixing properties are irreducibility, topological mixing, block gluing, strong irreducibility, complete prefix code (CPC), and uniform CPC. They study mixing properties for abstract tree-shift \(\mathcal{T}\), hom tree-shift \(\mathcal{T}_X\), and hom tree-SFT \(\mathcal{T}_A\). For a shift space \(X\), it is proved that: (1) \(X\) is mixing if \(\mathcal{T}_X\) is topologically mixing; (2) \(X\) is transitive if \(\mathcal{T}_X\) is irreducible. For an adjacency matrix \(A\), the authors study the mixing properties of \(X_A\) and \(\mathcal{T}_A\).