This reduces the computation of the entropy of certain symbolic systems on countable alphabets to a well-understood numerical problem. Under some conditions, the entropy of a countable topological Markov chain may be computed or bounded via the spectral radius of a linear operator, analogous to the finite case. The entropy is obtained by suprematizing over such identifications. In the case of an infinite alphabet, the number of finite words may be uncountable hence, we identify all but finitely many letters prior to counting. The entropy theory of this note admits a clear operational interpretation. 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 kommentar(er)
