ترغب بنشر مسار تعليمي؟ اضغط هنا

Symbolic dynamics: entropy = dimension = complexity

88   0   0.0 ( 0 )
 نشر من قبل Stephen G. Simpson
 تاريخ النشر 2017
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

Let $G$ be the group $mathbb{Z}^d$ or the monoid $mathbb{N}^d$ where $d$ is a positive integer. Let $X$ be a subshift over $G$, i.e., a closed and shift-invariant subset of $A^G$ where $A$ is a finite alphabet. We prove that the topological entropy of $X$ is equal to the Hausdorff dimension of $X$ and has a sharp characterization in terms of the Kolmogorov complexity of finite pieces of the orbits of $X$. In the version of this paper that has been published in Theory of Computing Systems, the proof of Lemma 4.3 contains a confusing typographical error. This version of the paper corrects that error.



قيم البحث

اقرأ أيضاً

Visibility algorithms are a family of geometric and ordering criteria by which a real-valued time series of N data is mapped into a graph of N nodes. This graph has been shown to often inherit in its topology non-trivial properties of the series stru cture, and can thus be seen as a combinatorial representation of a dynamical system. Here we explore in some detail the relation between visibility graphs and symbolic dynamics. To do that, we consider the degree sequence of horizontal visibility graphs generated by the one-parameter logistic map, for a range of values of the parameter for which the map shows chaotic behaviour. Numerically, we observe that in the chaotic region the block entropies of these sequences systematically converge to the Lyapunov exponent of the system. Via Pesin identity, this in turn suggests that these block entropies are converging to the Kolmogorov- Sinai entropy of the map, which ultimately suggests that the algorithm is implicitly and adaptively constructing phase space partitions which might have the generating property. To give analytical insight, we explore the relation k(x), x in[0,1] that, for a given datum with value x, assigns in graph space a node with degree k. In the case of the out-degree sequence, such relation is indeed a piece-wise constant function. By making use of explicit methods and tools from symbolic dynamics we are able to analytically show that the algorithm indeed performs an effective partition of the phase space and that such partition is naturally expressed as a countable union of subintervals, where the endpoints of each subinterval are related to the fixed point structure of the iterates of the map and the subinterval enumeration is associated with particular ordering structures that we called motifs.
For a group $G$ definable in a first order structure $M$ we develop basic topological dynamics in the category of definable $G$-flows. In particular, we give a description of the universal definable $G$-ambit and of the semigroup operation on it. We find a natural epimorphism from the Ellis group of this flow to the definable Bohr compactification of $G$, that is to the quotient $G^*/{G^*}^{00}_M$ (where $G^*$ is the interpretation of $G$ in a monster model). More generally, we obtain these results locally, i.e. in the category of $Delta$-definable $G$-flows for any fixed set $Delta$ of formulas of an appropriate form. In particular, we define local connected components ${G^*}^{00}_{Delta,M}$ and ${G^*}^{000}_{Delta,M}$, and show that $G^*/{G^*}^{00}_{Delta,M}$ is the $Delta$-definable Bohr compactification of $G$. We also note that some deeper arguments from the topological dynamics in the category of externally definable $G$-flows can be adapted to the definable context, showing for example that our epimorphism from the Ellis group to the $Delta$-definable Bohr compactification factors naturally yielding a continuous epimorphism from the $Delta$-definable generalized Bohr compactification to the $Delta$-definable Bohr compactification of $G$. Finally, we propose to view certain topological-dynamic and model-theoretic invariants as Polish structures which leads to some observations and questions.
We develop topological dynamics for the group of automorphisms of a monster model of any given theory. In particular, we find strong relationships between objects from topological dynamics (such as the generalized Bohr compactification introduced by Glasner) and various Galois groups of the theory in question, obtaining essentially new information about them, e.g. we present the closure of the identity in the Lascar Galois group of the theory as the quotient of a compact, Hausdorff group by a dense subgroup. We apply this to describe the complexity of bounded, invariant equivalence relations, obtaining comprehensive results, subsuming and extending the existing results and answering some open questions from earlier papers. We show that, in a countable theory, any such relation restricted to the set of realizations of a complete type over $emptyset$ is type-definable if and only if it is smooth. Then we show a counterpart of this result for theories in an arbitrary (not necessarily countable) language, obtaining also new information involving relative definability of the relation in question. As a final conclusion we get the following trichotomy. Let $mathfrak{C}$ be a monster model of a countable theory, $p in S(emptyset)$, and $E$ be a bounded, (invariant) Borel (or, more generally, analytic) equivalence relation on $p(mathfrak{C})$. Then, exactly one of the following holds: (1) $E$ is relatively definable (on $p(mathfrak{C})$), smooth, and has finitely many classes, (2) $E$ is not relatively definable, but it is type-definable, smooth, and has $2^{aleph_0}$ classes, (3) $E$ is not type definable and not smooth, and has $2^{aleph_0}$ classes. All the results which we obtain for bounded, invariant equivalence relations carry over to the case of bounded index, invariant subgroups of definable groups.
We examine topological dynamical systems on the Cantor set from the point of view of the continuous model theory of commutative C*-algebras. After some general remarks we focus our attention on the generic homeomorphism of the Cantor set, as construc ted by Akin, Glasner, and Weiss. We show that this homeomorphism is the prime model of its theory. We also show that the notion of generic used by Akin, Glasner, and Weiss is distinct from the notion of generic encountered in Fraisse theory.
We initiate the study of p-adic algebraic groups G from the stability-theoretic and definable topological-dynamical points of view, that is, we consider invariants of the action of G on its space of types over Q_p in the language of fields. We consid er the additive and multiplicative groups of Q_p and Z_p, the group of upper triangular invertible 2times 2 matrices, SL(2,Z_p), and, our main focus, SL(2,Q_p). In all cases we identify f-generic types (when they exist), minimal subflows, and idempotents. Among the main results is that the ``Ellis group of SL(2,Q_p)$ is the profinite completion of Z, yielding a counterexample to Newelskis conjecture with new features: G = G^{00} = G^{000} but the Ellis group is infinite. A final section deals with the action of SL(2,Q_p) on the type-space of the projective line over Q_p.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا