Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDecidability of irreducible tree shifts of finite type
152
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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.
rate research
Read More
We study the topological entropy of hom tree-shifts and show that, although the topological entropy is not conjugacy invariant for tree-shifts in general, it remains invariant for hom tree higher block shifts. In doi:10.1016/j.tcs.2018.05.034 and doi:10.3934/dcds.2020186, Petersen and Salama demonstrated the existence of topological entropy for tree-shifts and $h(mathcal{T}_X) geq h(X)$, where $mathcal{T}_X$ is the hom tree-shift derived from $X$. We characterize a necessary and sufficient condition when the equality holds for the case where $X$ is a shift of finite type. In addition, two novel phenomena have been revealed for tree-shifts. There is a gap in the set of topological entropy of hom tree-shifts of finite type, which makes such a set not dense. Last but not least, the topological entropy of a reducible hom tree-shift of finite type is equal to or larger than that of its maximal irreducible component.
This paper deals with the topological entropy for hom Markov shifts $mathcal{T}_M$ on $d$-tree. If $M$ is a reducible adjacency matrix with $q$ irreducible components $M_1, cdots, M_q$, we show that $h(mathcal{T}_{M})=max_{1leq ileq q}h(mathcal{T}_{M_{i}})$ fails generally, and present a case study with full characterization in terms of the equality. Though that it is likely the sets ${h(mathcal{T}_{M}):Mtext{ is binary and irreducible}}$ and ${h(mathcal{T}_{X}):Xtext{ is a one-sided shift}}$ are not coincident, we show the two sets share the common closure. Despite the fact that such closure is proved to contain the interval $[d log 2, infty)$, numerical experiments suggest its complement contain open intervals.
The purpose of this article is twofold. On one hand, we reveal the equivalence of shift of finite type between a one-sided shift $X$ and its associated hom tree-shift $mathcal{T}_{X}$, as well as the equivalence in the sofic shift. On the other hand, we investigate the interrelationship among the comparable mixing properties on tree-shifts as those on multidimensional shift spaces. They include irreducibility, topologically mixing, block gluing, and strong irreducibility, all of which are defined in the spirit of classical multidimensional shift, complete prefix code (CPC), and uniform CPC. In summary, the mixing properties defined in all three manners coincide for $mathcal{T}_{X}$. Furthermore, an equivalence between irreducibility on $mathcal{T}_{A}$ and irreducibility on $X_A$ are seen, and so is one between topologically mixing on $mathcal{T}_{A}$ and mixing property on $X_A$, where $X_A$ is the one-sided shift space induced by the matrix $A$ and $T_A$ is the associated tree-shift. These equivalences are consistent with the mixing properties on $X$ or $X_A$ when viewed as a degenerate tree-shift.
In this paper we consider the notion of normality of sequences in shifts of finite type. A sequence is normal if the frequency of each block exists and is equal to the Parry measure of the block. We give a characterization of normality in terms of incompressibility by lossless transducers. The result was already known in the case of the full shift.
We prove decidability results on the existence of constant subsequences of uniformly recurrent morphic sequences along arithmetic progressions. We use spectral properties of the subshifts they generate to give a first algorithm deciding whether, given p $in$ N, there exists such a constant subsequence along an arithmetic progression of common difference p. In the special case of uniformly recurrent automatic sequences we explicitely describe the sets of such p by means of automata.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
