Search

In this paper, we obtain a combinatorial expression for the Perron root and eigenvectors of a non-negative integer matrix using techniques from symbolic dynamics. We associate such a matrix with a multigraph and consider the edge shift corresponding to it. This gives rise to a collection of forbidden words F which correspond to the non-existence of an edge between two vertices, and a collection of repeated words R with multiplicities which correspond to multiple edges between two vertices. In general, for given collections F of forbidden words and R of repeated words with pre-assigned multiplicities, we construct a generalized language as a multiset. A combinatorial expression that enumerates the number of words of fixed length in this generalized language gives the Perron root and eigenvectors of the adjacency matrix. We also obtain conditions under which such a generalized language is a language of an edge shift. [ABSTRACT FROM AUTHOR]

We look at constructions of aperiodic subshifts of finite type (SFTs) on fundamental groups of graph of groups. In particular, we prove that all generalized Baumslag-Solitar groups (GBS) admit a strongly aperiodic SFT. Our proof is based on a structural theorem by Whyte and on two constructions of strongly aperiodic SFTs on $\mathbb {F}_n\times \mathbb {Z}$ and $BS(m,n)$ of our own. Our two constructions rely on a path-folding technique that lifts an SFT on $\mathbb {Z}^2$ inside an SFT on $\mathbb {F}_n\times \mathbb {Z}$ or an SFT on the hyperbolic plane inside an SFT on $BS(m,n)$. In the case of $\mathbb {F}_n\times \mathbb {Z}$ , the path folding technique also preserves minimality, so that we get minimal strongly aperiodic SFTs on unimodular GBS groups. [ABSTRACT FROM AUTHOR]

The purpose of this article is to study the algorithmic complexity of the Besicovitch stability of noisy subshifts of finite type, a notion studied in a previous article [1]. First, we exhibit an unstable aperiodic tiling,and then see how it can serve as a building block to implement several reductions from classical undecidable problems on Turing machines. It will follow that the question of stability of subshifts of finite type is undecidable, and the strongest lower bound we obtain in the arithmetical hierarchy is Π 2 -hardness. Lastly, we prove that this decision problem,which requires to quantify over an uncountable set of probability measures,has a Π 4 upper bound. [ABSTRACT FROM AUTHOR]

We provide an example of a non-finitely generated group which admits a nonempty strongly aperiodic subshift of finite type. Furthermore, we completely characterize the groups with this property in terms of their finitely generated subgroups and the roots of their conjugacy classes. [ABSTRACT FROM AUTHOR]

The non-emptiness, called the Domino Problem, and the characterization of the possible entropies of $ \mathbb{Z}^2 $-subshifts of finite type are standard problems of symbolic dynamics. In this article we study these questions with horizontal constraints fixed beforehand as a parameter. We determine for which horizontal constraints the Domino Problem is undecidable and when all right-recursively enumerable numbers can be obtained as entropy, with two approaches: either the additional local rules added to the horizontal constraints can be of any shape, or they can only be vertical rules. [ABSTRACT FROM AUTHOR]

A new geometric criterion is derived for the existence of chaos in continuous-time autonomous systems in three-dimensional Euclidean spaces, where a type of Smale horseshoe in a subshift of finite type exists, but the intersection of stable and unstable manifolds of two points on a hyperbolic periodic orbit does not imply the existence of a Smale horseshoe of the same type on any cross section of these two points. This criterion is based on the existence of a hyperbolic periodic orbit, differing from the classical equilibrium-based Shilnikov criterion and the condition of transversal homoclinic or heteroclinic orbit of a Poincaré map. [ABSTRACT FROM AUTHOR]

We define a class of subshifts defined by a family of allowed patterns of the same shape where, for any contents of the shape minus a corner, the number of ways to fill in the corner is the same. For such a subshift, a locally legal pattern of convex shape is globally legal, and there is a measure that samples uniformly on convex sets. We show by example that these subshifts need not admit a group structure by shift-commuting continuous operations. Our approach to convexity is axiomatic, and only requires an abstract convex geometry that is "midpointed with respect to the shape". We construct such convex geometries on several groups, in particular strongly polycyclic groups and free groups. We also show some other methods for sampling finite patterns, and show a link to conjectures of Gottshalk and Kaplansky. [ABSTRACT FROM AUTHOR]

We study the periodicity of subshifts of finite type (SFT) on Baumslag-Solitar groups. We show that for residually finite Baumslag-Solitar groups there exist both strongly and weakly-but-not-strongly aperiodic SFTs. In particular, this shows that unlike Z 2 , but like Z 3 , strong and weak aperiodic SFTs are different classes of SFTs in residually finite BS groups. More precisely, we prove that a weakly aperiodic SFT on B S (m , n) due to Aubrun and Kari is, in fact, strongly aperiodic on B S (1 , n) ; and weakly but not strongly aperiodic on any other B S (m , n). In addition, we exhibit an SFT which is weakly but not strongly aperiodic on B S (1 , n) ; and we show that there exists a strongly aperiodic SFT on B S (n , n). [ABSTRACT FROM AUTHOR]

In this paper, we describe the relationship between the Perron root and eigenvectors of an irreducible subshift of finite type with the correlation between the forbidden words in the subshift. In particular, we derive an expression for the Perron eigenvectors of the associated adjacency matrix. As an application, we obtain the Perron eigenvectors for irreducible (0 , 1) matrices which are adjacency matrices for directed graphs. Moreover, we derive an alternate definition of the Parry measure in ergodic theory on an irreducible subshift of finite type. [ABSTRACT FROM AUTHOR]

Let G G be a countable monoid and let A A be an Artinian group (resp. an Artinian module). Let Σ ⊂ A G Σ ⊂ A G be a closed subshift which is also a subgroup (resp. a submodule) of A G A G. Suppose that Γ Γ is a finitely generated monoid consisting of pairwise commuting cellular automata Σ → Σ Σ → Σ that are also homomorphisms of groups (resp. homomorphisms of modules) with monoid binary operation given by composition of maps. We show that the natural action of Γ Γ on Σ Σ satisfies a natural intrinsic shadowing property. Generalizations are also established for families of endomorphisms of admissible group subshifts. [ABSTRACT FROM AUTHOR]

We study mean dimension of shifts of finite type defined on compact metric spaces and give its lower bound when the shift possesses a certain "periodic block" of arbitrarily large length. The result is applied to shift maps on generalized inverse limits with upper semi-continuous closed set-valued functions. In particular we obtain a refinement of some results due to Banič [1] and Erceg and Kennedy [5] on the dimension of the inverse limit spaces and topological entropy of their shifts. [ABSTRACT FROM AUTHOR]

We prove strong laws of large numbers under intermediate trimming for Birkhoff sums over subshifts of finite type. This gives another application of a previous trimming result only proven for interval maps. To prove these statements we introduce the space of quasi-Hölder continuous functions for subshifts of finite type. Additionally, we prove a trimmed strong law for St. Petersburg type distribution functions which can be applied to interval maps, subshifts of finite type and possibly other dynamical systems. [ABSTRACT FROM AUTHOR]

This paper establishes topological (equi-)semiconjugacy and (equi-) conjugacy between induced non-autonomous set-valued systems and subshifts of finite type. First, some necessary and sufficient conditions are given for a non-autonomous discrete system to be topologically semiconjugate or conjugate to a subshift of finite type. Further, several sufficient conditions for it to be topologically equi-semiconjugate or equi-conjugate to a subshift of finite type are obtained. Consequently, estimations of topological entropy and several criteria of Li–Yorke chaos and distributional chaos in a sequence are derived. Second, the relationships of several related dynamical behaviors between the non-autonomous discrete system and its induced set-valued system are investigated. Based on these results, the paper furthermore establishes the topological (equi-)semiconjugacy and (equi-)conjugacy between induced set-valued systems and subshifts of finite type. Consequently, estimations of the topological entropy for the induced set-valued system are obtained, and several criteria of Li–Yorke chaos and distributional chaos in a sequence are established. Some of these results not only extend the existing related results for autonomous discrete systems to non-autonomous discrete systems, but also relax the assumptions of the counterparts in the literature. Two examples are finally provided for illustration. [ABSTRACT FROM AUTHOR]

In this paper, we establish statistical results for a convex co-compact action of a free group on a CAT( - 1 ) space where we restrict to a non-trivial conjugacy class in the group. In particular, we obtain a central limit theorem where the variance is twice the variance that appears when we do not make this restriction. [ABSTRACT FROM AUTHOR]

In this paper, we construct a special class of subshifts of finite type. By studying the spectral radius of the transfer matrix associated with the subshift of finite type, we obtain an estimation of its topological entropy. Interestingly, we find that the topological entropy of this class of subshifts of finite type converges monotonically to log(n + 1) (a constant only depends on the structure of the transfer matrices) as the increasing of the order of the transfer matrices. [ABSTRACT FROM AUTHOR]

The dynamical structure of the rational map ax+1/x on the projective line P1(Q2) over the field ℚ2 of 2-adic numbers, is fully described. [ABSTRACT FROM AUTHOR]

We generalize the definition of topological entropy due to Adler, Konheim, and McAndrew [1] to set-valued functions from a closed subset A of the interval to closed subsets of the interval. We view these set-valued functions, via their graphs, as closed subsets of [ 0 , 1 ] 2 . We show that many of the topological entropy properties of continuous functions of a compact topological space to itself hold in our new setting, but not all. We also compute the topological entropy of some examples, relate the entropy to other dynamical and topological properties of the examples, and we give an example of a closed subset G of [ 0 , 1 ] 2 that has 0 entropy but G ∪ { ( p , q ) } , where ( p , q ) ∈ [ 0 , 1 ] 2 ∖ G , has infinite entropy. [ABSTRACT FROM AUTHOR]

In this paper we extend the concept of topological stability from homeomorphisms to group actions on compact metric spaces and prove that if an action of a finitely generated group is expansive and has the pseudoorbit tracing property, then it is topologicaly stable. This represents a group action version of P. Walter's stability theorem [Lecture Notes in Math., vol. 668, Springer, 1978, pp. 231-244]. Moreover we give a class of group actions with topological stability or pseudo-orbit tracing property. In particular, we establish a characterization of subshifts of finite type over finitely generated groups in terms of the pseudo-orbit tracing property. [ABSTRACT FROM AUTHOR]

Let f be an Anosov diffeomorphism of the n -dimensional torus T n and τ a continuous self-mapping of T n commuting with f . We prove that τ is surjective if and only if the restriction of τ to each homoclinicity class of f is injective. [ABSTRACT FROM AUTHOR]

This paper is concerned with estimations of topological entropy for non-autonomous discrete systems. An estimation of lower bound of topological entropy for coupled-expanding systems associated with transition matrices in compact Hausdorff spaces is given. Estimations of upper and lower bounds of topological entropy for systems in compact metric spaces are obtained by their topological equi-semiconjugacy to subshifts of finite type under certain conditions. One example is provided for illustration. [ABSTRACT FROM PUBLISHER]

On the one hand, Socolar showed in 1990 that the n-fold planar tilings admit weak local rules when n is not divisible by 4 (the $$n=10$$ case corresponds to the Penrose tilings and is known since 1974). On the other hand, Burkov showed in 1988 that the eightfold tilings do not admit weak local rules, and Le showed the same for the 12-fold tilings (unpublished). We here show that this is actually the case for all the 4 p-fold tilings. [ABSTRACT FROM AUTHOR]

Subshifts of finite type are sets of colorings of the plane defined by local constraints. They can be seen as a discretization of continuous dynamical systems. We investigate here the hardness of deciding factorization, conjugacy and embedding of subshifts in dimensions d > 1 for subshifts of finite type and sofic shifts and in dimensions d ≥ 1 for effective shifts. In particular, we prove that the conjugacy, factorization and embedding problems are Σ 3 0 -complete for sofic and effective subshifts and that they are Σ 1 0 -complete for SFTs, except for factorization which is also Σ 3 0 -complete. [ABSTRACT FROM AUTHOR]

We are interested in situations where the Hausdorff measure and Hausdorff content of a set are equal in the critical dimension. Our main result shows that this equality holds for any subset of a self-similar set corresponding to a nontrivial cylinder of an irreducible subshift of finite type, and thus also for any self-similar or graph-directed self-similar set, regardless of separation conditions. The main tool in the proof is an exhaustion lemma for Hausdorff measure based on the Vitali Covering Theorem. We also give several examples showing that one cannot hope for the equality to hold in general if one moves in a number of the natural directions away from 'self-similar'. For example, it fails in general for self-conformal sets, self-affine sets and Julia sets. We also give applications of our results concerning Ahlfors regularity. Finally we consider an analogous version of the problem for packing measure. In this case we need the strong separation condition and can only prove that the packing measure and δ-approximate packing pre-measure coincide for sufficiently small δ > 0. [ABSTRACT FROM AUTHOR]

It was shown in Kifer (Israel J Math, ) that for any subshift of finite type considered with a Gibbs invariant measure the numbers of multiple recurrencies to shrinking cylindrical neighborhoods of almost all points are asymptotically Poisson distributed. Here we not only extend this result to all $$\psi $$ -mixing shifts with countable alphabet but actually show that for all points the distributions of these numbers are asymptotically close either to Poisson or to compound Poisson distributions. It turns out that for all nonperiodic points a limiting distribution is always Poisson while at the same time for periodic points there may be no limiting distribution at all unless the shift invariant measure is Bernoulli in which case the limiting distribution always exists. Thus we describe, essentially completely, limiting distributions of multiple recurrence numbers in this setup. As a corollary we obtain also that the first occurence time of the multiple recurrence event is asymptotically exponentially distributed. Most of the results are new also for the widely studied single recurrencies case (see, for instance, Haydn and Vaienti Discret Contin Dyn Syst A 10:589-616, ; Probab Theory Relat Fields 144:517-542, ; Abadi and Saussol Stoch Process Appl 121:314-323, ; Abadi and Vergne Nonlinearity 21:2871-2885, ), as well. [ABSTRACT FROM AUTHOR]

We develop a Galois theory for difference ring extensions, inspired by Magid's separable Galois theory for ring extensions and by Janelidze's categorical Galois theory. Our difference Galois theorem states that the category of difference ring extensions split by a chosen Galois difference ring extension is classified by actions of the associated difference profinite Galois groupoid. In particular, difference locally étale extensions of a difference ring are classified by its difference profinite fundamental groupoid. The emergence of difference profinite spaces, viewed as discrete dynamical systems in the realm of topological dynamics, leads us to investigate the interaction of difference algebra and symbolic dynamics. As an application of this interaction, we prove the near-rationality of a certain difference zeta function counting solutions of systems of difference algebraic equations over algebraic closures of finite fields with Frobenius. [ABSTRACT FROM AUTHOR]

Abstract: We construct spectral metric spaces for Gibbs measures on a one-sided topologically exact subshift of finite type. That is, for a given Gibbs measure we construct a spectral triple and show that Connesʼ corresponding pseudo-metric is a metric and that its metric topology agrees with the weak-⁎-topology on the state space over the set of continuous functions defined on the subshift. Moreover, we show that each Gibbs measure can be fully recovered from the noncommutative integration theory and that the noncommutative volume constant of the associated spectral triple is equal to the reciprocal of the measure theoretical entropy of the shift invariant Gibbs measure. [Copyright &y& Elsevier]

Abstract: In this paper, we are interested in computability aspects of subshifts and in particular Turing degrees of two-dimensional subshifts of finite type (SFTs) (i.e., tilings). To be more precise, we prove that, given any class of , there is an SFT such that is recursively homeomorphic to , where is a computable set of points. As a consequence, if contains a computable member, and have the exact same set of Turing degrees. On the other hand, we prove that, if contains only non-computable members, some of its members always have different but comparable degrees. This gives a fairly complete study of Turing degrees of SFTs. [Copyright &y& Elsevier]

Abstract: Using topological conjugacies, a continuous mapping from the Cantor set onto itself approximates its factors that are continuous surjective mappings on the Cantor set. Using topological conjugacies, a continuous mapping from the Cantor set onto itself and its natural extension approximate to each other. As a corollary, we shall show that a sofic subshift that is homeomorphic to the Cantor set is approximated by some subshifts of finite type. Furthermore, extending the former result in Shimomura (in press) , we get the following result: Let f and g be continuous mappings from the Cantor set onto itself. Suppose that f is chain mixing and g is aperiodic. Then, a sequence of continuous mappings which are topologically conjugate to g approximates f if trivial necessary conditions on periodic points are satisfied. As a corollary, in the set of all chain mixing topological dynamical systems on the Cantor set, the topological conjugacy class of any topological dynamical system without periodic point is dense. [Copyright &y& Elsevier]

Abstract: We consider continuous self-maps of compact metric spaces, and for each point of the space we define the notion of eulerian entropy by considering the exponential growth rate of complexity in the initial chunks of the orbit of the point. We show that eulerian entropy is constant on a residual subset for transitive dynamical systems. For elements in the shift dynamical system we define an equivalent notion named non-repetitive subword complexity, and show that for a large class of mixing subshifts of finite type, the set of points for which the non-repetitive subword complexity is equal to the topological entropy is residual. If is either a transitive interval map or an infinite transitive subshift of finite type, we establish that there is such that the eulerian entropy of is a positive constant that is attained on a residual set of points. [Copyright &y& Elsevier]

We present some simple examples of exponentially mixing hyperbolic suspension flows. We include some speculations indicating possible applications to suspension flows of algebraic Anosov systems. We conclude with some remarks about generalizations of our methods. [ABSTRACT FROM AUTHOR]

By applying a result from the theory of subshifts of finite type,1 we generalize the result of Frame and Lanski2 to IFS with multistep memory. Specifically, we show that for an IFS ${\cal I}$ with m-step memory, there is an IFS with 1-step memory (though in general with many more transformations than ${\cal I}$) having the same attractor as ${\cal I}$. [ABSTRACT FROM AUTHOR]

Under some mild condition, a random walk in the plane is recurrent. In particular each trajectory is dense, and a natural question is how much time one needs to approach a given small neighbourhood of the origin. We address this question in the case of some extended dynamical systems similar to planar random walks, including ℤ2-extension of mixing subshifts of finite type. We define a pointwise recurrence rate and relate it to the dimension of the process, and establish a result of convergence in distribution of the rescaled return time near the origin. [ABSTRACT FROM AUTHOR]

Abstract: It was discovered some years ago that there exist non-integer real numbers for which only one sequence of integers satisfies the equality . The set of such “univoque numbers” has a rich topological structure, and its study revealed a number of unexpected connections with measure theory, fractals, ergodic theory and Diophantine approximation. In this paper we consider for each fixed the set of real numbers x having a unique representation of the form with integers belonging to . We carry out a detailed topological study of these sets. For instance, we characterize their closures, and we determine those bases q for which is closed or even a Cantor set. We also study the set consisting of all sequences of integers such that . We determine the numbers for which the map (defined on ) is constant in a neighborhood of r and the numbers for which is a subshift or a subshift of finite type. [Copyright &y& Elsevier]

The aim of this paper is to derive a sharper lower bound for the spatial entropy of two-dimensional golden mean. [ABSTRACT FROM AUTHOR]

Let Γ be a group of type rotating automorphisms of a building B of type A˜2, and suppose that Γ acts freely and transitively on the vertex set of B. The apartments of B are tiled by triangles, labelled according to Γ-orbits. Associated with these tilings there is a natural subshift of finite type, which is shown to be irreducible. The key element in the proof is a combinatorial result about finite projective planes. [Copyright &y& Elsevier]

We give a computable condition for topological transitivity and topological mixing of subshifts of finite type. An algorithmizable method for computing a spectral decomposition of a subshift of finite type is also presented. [ABSTRACT FROM AUTHOR]

The code space plays a significant role in the study of self-similar fractals. It is used to give coordinates to the points of a self-similar set. The code space also plays an important role in dynamical systems as well. The shift map on the code space is a valuable an example of a dynamical system. The shift map restricted to certain invariant subspaces is also important. The subshifts of finite type are used to analyze many common dynamical systems. This is the basis for the theory of symbolic dynamics.There is a particularly useful metric on the code space. With this metric the dimension of the code space and the subshifts of finite type can be computed using results of K. Falconer on sub-self-similar sets. We show that the code space can be embedded in Euclidean space, Rn, by a map which is bi-Lipschitz. The shift or subshift of finite type on this embedded image can be extended to a C∞-map F :Rn→Rn having the embedded set as a maximal compact invariant set which contains the nonwandering set of F in this case. The map F restricted to this set will be equivalent to a power of the shift or the subshift of finite type. The Hausdorff dimension of the invariant set, the Lyapunov exponents of F at various points in the invariant set, and the topological entropy of F can all be computed. This provides a general method of constructing examples in which the relationship between these quantities can be studied. [Copyright &y& Elsevier]