Factor maps, entropy and fiber cardinality for Markov shifts. Topological boundaries for countable state Markov shifts. Topological entropy of enumerable Markov chains. The author declares no conflict of interest. The universal system ( S U, σ ) contains every chain on an infinite alphabet as an open dense subsystem, since the infinite vertex set of the subgraph is open and dense in the cofinite topology. Then V Z ∩ S U is closed and nowhere dense, since V is finite, and a σ-invariant subset of S U, since G embeds as an induced subgraph. To see this, observe that the universal directed graph U contains a copy of G. The topological Markov chain ( S U, σ ) is such that, for any topological Markov chain S G on a finite alphabet, there exists a closed embedding ( S G, σ ) ↪ ( S U, σ ). (The case of undirected graphs is discussed in the case of directed graphs, in the guise of 3-colored graphs, is discussed in ). It is well-known that there exists a countable connected directed graph U such that, for any countable directed graph G, there exists an embedding G ↪ U, an injection that is adjacency preserving, whose image is an induced subgraph of U. However, there exists a more interesting universal chain. Hence, there is a countable topological Markov chain which contains all finite topological Markov chains as closed subsystems. Since there are countably many finite directed graphs, their disjoint union is a countable graph. Contrary to these authors, this paper is mostly interested in entropy theory, especially its connections to subword complexity and spectral theory. Their constructions have been further developed to yield topological dynamical systems which are analogous to classical Z-shifts, and in this setting, characterizations of morphisms of systems are known. , who considered an N-shift on words in the Alexandrov compactification which they endowed with a certain quotient topology to get rid of the introduced ∞-symbol. In Gurevich’s setting, the dynamical properties of the boundary of a (sofic) subshift have been studied ( Section 3) (see also ). Still, our approach is similar to Gurevich’s, since minimal open covers in the Alexandrov compactification of an infinite countable discrete space and in the cofinite topology are similar. The theory of Gurevich has the unpleasent feature that the closure of the set of graph walks must be taken. Gurevich has considered the Alexandrov compactification of the alphabet and his formula for the entropy of the respective topological Markov chains coincides with ours. In this note, we endow the alphabet with a compact topology which coincides with the discrete topology in the finite case, the cofinite topology. Most approaches attempt to compactify the respective alphabet. Beside its theoretical interest, this was motivated by the increasing importance of infinite state systems in computer science.Īny attempt at studying symbolic dynamics on infinite alphabets has to deal with the fact that the discrete topology, employed in the finite case, leads to shift spaces which are not compact. ![]() This note is an attempt to generalize this meeting ground of topology, graph theory, and spectral theory to infinite alphabets, especially countably infinite alphabets. On an exponential scale, this rate equals the growth of the number of finite words. Considering the graph as a linear map, the spectral radius measures the rate of dilation under iterated application. In the case of a topological Markov chain, the entropy equals the natural logarithm of the spectral radius of the generating graph. For symbolic systems, the entropy equals the exponential growth rate of the number of finite words of fixed length. The most important numerical invariant of dynamical systems is the topological entropy. In computer science, certain symbolic systems, namely, the topological Markov chains generated by finite graphs, model the evolution of finite transition systems, and the class of sofic symbolic systems (factors of topological Markov chains) models the evolution of certain automata. Symbolic dynamical systems on finite alphabets are classical mathematical objects that provide a wealth of examples and have greatly influenced theoretical developments in dynamical systems.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |