Symbolic Dynamics


Doris Fiebig & Ulf Fiebig

This site presents informations on our papers, as publishing status, and a short abstract, together with a possibility for download of some of the papers. On further requests please contact via email given below.
Most of them are related to symbolic dynamics, and a few other ones.

Please visit the graphics homepage Riolama of Doris Fiebig, where you can browse a gallery, buy prints, read tutorials, and hire for webdesign or commisional graphic works.




    1. U.Fiebig. A return time invariant for finitary isomorphisms, Ergod. Th. & Dynam. Sys. (1984), 4, 225-231
      abstract: Poincare•s recurrence theorem says that, given a measurable subset of a space on which a finite measure-preserving transformation acts, almost every point of the subset returns to the subset after a finite number of applications of the transformation. Moreover, Kac•s recurrence theorem refines this result by showing that the average of the first return times to the subset over the subset is at most one, with equality in the ergodic case. In particular, the first return time function to any measurable set is integrable. By considering the supremum over all p — 1 for which the first return time function is p-integrable for all open sets, we obtain a number for each almost-topological dynamical system, which we call the return time invariant. It is easy to show that this invariant is non-decreasing under finitary homomorphism. We use the invariant to construct a continuum number of countable state Markov shifts with a given entropy (and hence measure-theoretically isomorphic) which are pairwise non-finitarily isomorphic.
    2. U.Fiebig, J.van den Berg. On a combinatorial conjecture concerning disjoint occurrences of events, Ann. Prob. 15 (1987),354-374
      abstract: Recently van den Berg and Kesten have obtained a correlation-like inequality for Bernoulli sequences. This inequality, which goes in the opposite direction of the FKG inequality, states that the probability that two monotone (i.e., increasing or decreasing) events "occur disjointly" is smaller than the product of the individual probabilities. They conjecture that the monotonicity condition is immaterial, i.e., that the inequality holds for all events. In the present paper we try to make clear the intuitive meaning of the conjecture and prove some nontrivial special cases, one of which, a pure correlation inequality, is an extension of Harris' FKG inequality.
    3. U.Fiebig, M.Boyle. The action of inert finite-order automorphisms on finite subsystems of the shift, Ergod. Th. & Dynam. Sys. (1991), 11, 413-425
      abstract: Let (X,S) be a shift of finite type. Let G be the group of automorphisms of (X,S) which are compositions of elements of finite order in the kernel of the dimensionrepresentation. We characterize the action of G on finite subsystems of (X.S).
    4. U.Fiebig. Gyration numbers for involutions of subshifts of finite type I, Forum Math. 4 (1992), 77- 108
      abstract: We investigate the sign and gyration number sequences for products of involutions of shifts of finite type (SFT) and a generalized version of the sign-gyration compatibility condition (SGCC) introduced by Boyle and Krieger [BK]. The concept of the parity set of a dynamical system and the study of orbit spaces leads to a computable transform for the SGCC satisfied by a given product of involutions. In particular, only finitely many such compatibility conditions occur for a single SFT. Analogously, linking parity sets to gyration numbers gives a computable transfor for the sign and gyration sequences of (products of) involutions, which allow us to characterize these sequences. Finally, we determine for the full N-shifts the (simple) gyration range for products of involutions, the general SFT-case will be treated in [Fi2].
    5. U.Fiebig. Gyration numbers for involutions of subshifts of finite type II, Forum Math. 4 (1992), 187-215
      abstract: We continue our study of the sign (SN), gyration (GY), and the sign-gyration-compatibility (SGCC) for homeomorphisms for products of involutions of shifts of finite type. We focus on the automorphism subgroup generated by the (simple) involutions of a single SFT. We describe its image under the gyration homomorphism in terms of the zetafunction and a new invariant for shift equivalence over Z/2Z. Then we show that in a global sense GY and SGCC are independent homomorphisms, but GY and SN as well as SN and SGCC are not. Finally, we discuss some of the basic number theoretical properties of sign and gyration number sequences.
    6. D.Fiebig. Common closing extensions and finitary regular isomorphism for synchronized systems, Contemporary Mathematics, Vol 135, 1992,125-138.
      abstract: Two synchronized systems are shown to be finitary regular isomorphic iff they admit a common synchronized extension with factor maps which are right closing a.e. and 1-1 a.e. A complete invariant in terms of the Fischer coever is presented. Some computable invariants are discussed.
    7. D.Fiebig, U.Fiebig. Covers for coded systems, Contemporary Mathematics, Vol 135, 1992, 139-179.
      abstract: A coded system is a shubshift (with finite alphabet) which is the closure of an uniformly continuous image of a countable irreducible Markov chain. Such a Markov chain together with the uniformly continuous map is called a "cover". The coded systems are a natural generalization of transitive sofic systems. Our aim is to generalize parts of the sofic theory to certain subclasses of coded systems, the so-called synchronized and half-synchronized systems. We give alternative definitions for (half-)synchronized systems which show that any subshifts with at most countably many follower sets (of left infinite rays) is synchronized.
      We define a canonical Fischer cover for (half-)synchronized systems and discuss its minimality properties in the space of all covers. We characterize the Fischer cover in various ways and develop an analogue of the sofic almost Markov theory. A synchronized system will be "almost Markov" if its Fischer cover is uniformly left closing. Then its Fischer cover intercepts any other cover by a uniformly continuous factor map.
      We characterize those Fischer covers which continuously intercept any other cover.
      We show that a Fischer cover has no proper uniformly continuous factors and characterize those Fischer covers which have no proper continuous factors.
    8. U.Fiebig. Periodic points and finite group actions on shifts of finite type,Ergod.Th.&Dynam.Sys. (1993), 13, 485-514
      abstract: Let G be an abstract finite group. For an action alpha of G on a shift of finite type (SFT) S we introduce the periodic data of alpha, a computable finite-orderd set of complex polynomials. We show that two actions of G on possibly different SFTs are conjugate on periodic points iff their periodic data coincide. For each subgroup H of G the points fixed by alpha/H (the restriction of alpah to H) form a subsystem of S, which is of finite type. Our result shows that the zetafunctions of these subsystems determine the conjugacy class (on periodic points) of alpha up to finitely many possibilities.
      The orbit space of a finite skew action on a SFT S, endowed with the homeomorphim induced by S, is shown to have a zeta function equal to the zeta function of an SFT which is a left-closing quotient of S. We show that this zeta function equals the zeta function of S iff the skew action is inert with respect to a certain power of S.
      Finally we consider functions of the periodic data as for example gyration numbers.
    9. D.Fiebig. Mixing properties of a class of Bernoulli-processes, Trans of the AMS 338 (1993),479-493.
      abstract: We prove that stationary very weak Bernoulli process with rate O(1/n) (VWB O(1/n)) are strictly very weak Bernoulli with rate O(1/n). Furthermore we discuss the relationbetween VWB O(1/n) and the classical mixing properties for countable state processes. In particular, we show that VWB O(1/n) implies phi-mixing.
    10. R.Burton, M.Denker, D.Fiebig. Finite-state, stationary, phi-mixing processes which are not very weak Bernoulli with rate O(1/n), Stochastic Processes and their Applications 50 (1994) 117-133.
      abstract: In this paper a stationary finite-state process is constructed that satisfies the phi-mixing condition but is not very weak Bernoulli with rate O(1/n). phi-mixing is implied by very weak Bernoulli with rate O(1/n), so this examle shows very weak Bernoulli with rate O(1/n) is a strictly stronger condition.
    11. D.Fiebig, U.Fiebig. Topological boundaries for countable state Markov shifts, Proc. Lond. Math. Soc., III, Ser.70, No.3, (1995), 625-643.
      abstract: Let (S,s) be a transitive locally compact countable state Markov shift. If (S^,s^) is some compact metric dynamical system ("cmds") that contains (S,s) as a dense subsystem then the space S* = S^- S together with the homeomorphism s* = s^|S* will be called a boundary for (S,s). Any cmds (X,T) is shown to be a boundary for some transitive locally compact countable state Markov shift (Theorem A). We define a new canonical compactification whose boundary is a conjugacy invariant that distinguishes Markov shifts according to their behaviour "at infinity" (Theorem B). This boundary, together with a periodic point condition, will be used to characterize the set of all chain recurrent boundaries of a given transitive locally compact countable state Markov shift (Theorem C,D).
    12. D.Fiebig. Common extensions and hyperbolic factor maps for coded systems, Ergod.Th. & Dynam.Sys. (1995) 15, 517-534.
      abstract: The classification of dynamical systems by the existence of certain common extensions has been carried out very successfully in the class of shifts of finite type ("finite equivalence", "almost topological conjugacy" [P], [AM]). We consider generalizations of these notions in the class of coded systems. Topological entropy is shown to be a complete invariant for the existence of a common coded entropy preserving extension. In contrast to the shift of finite type setting, this extension cannot be made bounded-to-1 in general. Common extensions with hyperbolic factor maps lead to a version of almost topological conjugacy for coded systems.
    13. D.Fiebig. Constant-to-one extensions of shifts of finite type, Proceedings of the AMS 124 (1996), 2917-2922.
      abstract: Any transitive shift of finite type has a transitive constant-to-one extension which is not of finite type.
    14. D.Fiebig, U.Fiebig. The automorphism group of a coded system, TransAMS 348, (1996), 3173-3191.
      abstract: We give a general construction of coded systems with an automorphism group isomorphic to Z dirct sum G where G is any preassigned group which has a "continuous block presentation" (the isomorphism will map the shift to (1,e_G)). Several applications are given. In particular, we obtain automorphism groups of coded systems which are abelian, which are finitely generated and one which contains Z[1/2]. We show that any group which occurs as a subgroup of the automorphism group of some subshift with periodic points dense already occurs for some synchronized system.
    15. D.Fiebig, U.Fiebig. Entropy and generators for locally compact subshifts, Ergod.Th. & Dynam.Sys.(1997), 17, 349-368.
      abstract: We introduce transition entropy and periodic entropy for locally compact subshifts. Finiteness of both characterizes the existence of a finite generator. Finiteness of the transition entropy characterizes the existence of a generator with bounded degree. We extend Krieger•s embedding theorem and characterize the locally compact non-dense subsystems of a (compact) mixing shift of finite type.
    16. M.Boyle, D.Fiebig, U.Fiebig. A dimension group for local homeomorphisms and endo- morphisms of onesided shifts of finite type, J. reine angew. Math. (Crelles) 487, (1997), 27-59.
      abstract: We attach to a local homeomorphism S of a compact zero dimensional metrizable space X two abstract ordered groups, the images group G(S) and the preimages group G^(S). The images group is a dimension group with a distinguished order unit. We use these groups to study commuting local homeomorphisms. When S is a onesided mixing shift of finite type (SFT), G(S) is isomorphic to the direct limit group of a defining matrix, and a onesided SFT commuting with S is determined up to eventual conjugacy (but not conjugacy) by its action on G(S). We obtain complete and computable invariants for the eventual conjugacy classes of onesided SFTs, and show commuting onesided SFTs have a common measure of maximal entropy. This places severe constraints on the existence of commuting presentations of onesided SFTs. There are applications to cellular automata and links to Ruelle's thermodynamic formalism.
    17. D.Fiebig, U.Fiebig, N.Jonoska. Multiplicities of covers for sofic shifts, Theoret. Comp. Sci. 262 (2001) 349-375.
      abstract: We consider a transitive sofic shift T and a SFT cover f : S arrow T. We define the multiplicity of the cover (S,f) to be the largest number of preimages of a point. The intrinsic multiplicity of T is the minimum of the multiplicities over all covers of T, denoted by m(T). Is m(T) computable ? We do not answer this question. However the attempt to solve this problem led us to find sharp estimates for the intrinsic multiplicity, sharpen a result of S.Williams, and solve a problem posed by P.Trow.
    18. D.Fiebig. Factor maps, entropy and fibre cardinality for Markov shifts, Rocky Mountain J. Math. (2001), 31, 955-986.
      abstract: It is well known that a factor map between transitive shifts of finite type either preserves entropy and is bounded-to-1 or it does not preserve entropy and is uncountable-to-1. In this paper we elucidate the relation between entropy and fibre cardinality for factor maps between transitive locally compact Markov shifts. We show that every countable-to-1 factor map increases the Gurevic entropy while every finite-to-1 factor map preserves Gurevic entropy. We study finite-to-1 proper factor maps and show that they additionally preserve positive and strongly positive recurrence. Then we investigate finite-to-1 proper factor maps between Markov shifts which have an expansive 1-point compactification. We conclude the paper with some examples showing that properly finite-to-1 and properly countable-to-1 factor maps exist between synchronized systems.
      download .dvi-file
    19. D.Fiebig, U.Fiebig. Compact factors of countable state Markov shifts, Theoret. Comp. Sci. 270 (2002) 935-946.
      abstract: We study continuous shift commuting maps from transitive countable state Markov shifts into compact subshifts. The closure of the image is a coded system. On the other hand, any coded system is the surjective image of some transitive Markov shift, which may be chosen locally compact by construction. These two results yield a formal analogy to \lq\lq the transitive sofic systems are the subshift factors of transitive shifts of finite type\rq\rq . Then we consider factor maps which have bounded coding length in some graph presentation (label maps). Now the image has to be synchronized, but not every synchronized system can be obtained in this way. We show various restrictions for a surjective label map to exist.
      download .dvi-file
    20. D.Fiebig, U.Fiebig. Invariants for Subshifts via Nested Sequences of Shifts of Finite Type, Ergod.Th. &Dynam.Sys. (2001), 21, 1731-1758.
      abstract: To obtain connections between grammars of languages and subshifts, W.Krieger introduced the idea of associating to a subshift \ $ X $\ \ a certain increasing sequence of shifts of finite type \ $ X_{n} $\ \ sitting inside \ $ X$. Their union is the set of {\sl presynchronizing points}. A system is called {\sl presynchronized} if there is a sequence of irreducible components \ $ C_{n} \subset X_{n}$, $ n \in \Bbb N$, increasing with \ $ n $\ \ and with dense union (a characterization of coded systems shows that presynchronized systems are coded.) We investigate the uniqueness (up to eventual equality) of such sequences. For that an equivalence relation on the periodic presynchronizing points captures all the possible choices of increasing sequences of irreducible components. Dense equivalence classes correspond to dense unions. There is a one-sided and a two-sided theory. In the one-sided setting we show the uniqueness of a dense equivalence class and identify the right presynchronized systems as the well known halfsynchronized systems. The two sided theory turns out to be more complicated (and interesting). There can be more than one dense class. Many examples are discussed in detail. There is a natural ordering on the set of (dense) equivalence classes. For each finite order structure we find a representative in the countable class of systems which are intersections of Dyck shifts with shifts of finite type. Finally we discuss the relation to other known classes of subshifts, which is more subtle than in the one-sided setting. Almost all systems considered in this work will be coded.
      download .dvi-file
    21. D.Fiebig, U.Fiebig. Subshift compactifications of locally compact Markov shifts, to appear in Theoret. Comp. Sci.
      abstract: A compact subshift T is a subshift compactification of a locally compact (l.c.) subshift S if there is a dense embedding of S into T. We consider the class of compact subshifts which occur as compactifications of l.c. Markov shifts. This class is contained in the class of coded systems, contains all synchronized systems, and both containments are strict. We investigate embedding maps which have bounded coding length in some graph presentation (label maps) and how the embedded l.c. Markov shifts are located within the ambient (now necessarily synchronized) subshift. Finally we consider l.c. Markov shifts S with expansive 1-point compactification S_0. Now all compactifications with finite boundary (in particular S_0 ) have to be synchronized. We obtain additional information (individual dynamical properties and the lattice structure of these compactifications), in the cases where S_0 is sofic, almost finite type, or finite type.
      download .dvi-file
    22. D.Fiebig. Factor theorems for locally compact Markov shift, Forum Math. 14 (2002), 623-640.
      abstract: We study the problem of the existence of a factor map between two given locally compact transitive countable state Markov shifts. The case of a compact range shift is already satisfactory solved. We consider non-compact Markov shifts. Various necessary conditions arise, as divers weakenings of compactness, the "geometry" of the shifts at "infinity" and return time constraints. We characterize when a factor map exists when the domain shift has an uncountable set going to infinity and the range shift is mixing and periodic at infinity. As an application we obtain two mixing locally compact Markov shifts which are weakly conjugate, but not conjugate.
      download .dvi-file
    23. D.Fiebig. Common extensions for locally compact Markov shifts, Monath. Math. 132, 289-301 (2001).
      abstract: We extend W.Parry's result in showing that two locally compact transitive Markov shifts have the same Gurevic entropy iff they have a common entropy preserving extension by a locally compact transitive Markov shift. Additionally the factor maps can be made countable-to-1 biclosing.
      download .dvi-file
    24. M.Boyle, D.Fiebig, U.Fiebig. Residual entropy, conditional entropy and subshift cover, Forum Math. 14 (2002), 713-757
      abstract: We study the existence of subshift covers for topological dynamical systems, the infimum of the entrpy jumps to such covers, and various aspects of conditional entropy and covering maps including a variational principle for covering maps. In particular we show every asymptotically h-expansive system (and therefore by Buzzi every C^infinity homeomorphism of a compact Riemannian mainfold) has a subshift cover of equal entropy. Our arguments in dimension zero are extended to higher dimensions with theorems of Kulesza and Thomsen.
      get file here (external link)
    25. D.Fiebig. Book Review: Symbolic Dynamics. One-sided, Two-sided and Countable State Markov Shifts by Bruce P.Kitchens. Ergod.Th. & Dynam.Sys.(2001), 21, 315-318
    26. D.Fiebig, U.Fiebig, M.Yuri. Pressure and equilibrium states for countable state Markov shifts. Israel J.Math. 131(2002),221-257
      abstract: We give a general definition of the topological pressure \ $ P_{top}(f$,$S) $\ \ for continuous real valued functions \ $ f : X \to \Bbb R $\ \ on transitive countable state Markov shifts \ $ (X$,$S)$. A variational principle holds for functions satisfying a mild distortion property. We introduce a new notion of Z-recurrent functions. Given any such function \ $ f$, we show a general method how to obtain tight sequences of invariant probability measures supported on periodic points such that a weak accumulation point \ $ \mu $\ \ is an equilibrium state for \ $ f $\ \ if and only if \ $ \int f^{-} d\mu < \infty $. we discuss some conditions that ensure this integrability. as an application we obtain the gauss measure as a weak limit of measures supported on periodic points.
      download .dvi-file
    27. D.Fiebig. Graphs with preassigned Salama entropies and optimal degrees for locally compact Markov shifts. Ergodic Theory and Dynamical Systems (2003), 23:1093-1124
      abstract: Suppose that \ $ S $\ \ is a transitive locally compact Markov shift with Gurevic entropy less than \ $ logp$, where \ $ p $\ \ is an integer. If the inequality is strict, then \ $ S $\ \ admits a graph presentation with degree \ $ p$. Additionally, we realize any preassigned values for the Salama entropies. This result is best possible, since there are examples of Gurevic entropy \ $ logp $\ \ which do not admit a graph presentation with degree \ $ p$. We also show that every non-compact locally compact Markov shift has presentations without synchronizing blocks.
    28. D.Fiebig, U.Fiebig. Embedding theorems for locally compact mixing Markov shifts. Ergodic Theory & Dynam. Systems (2005), 25, 107-131
      abstract: We characterize when a lower entropy locally compact subshift \ $ S $\ \ embeds into a locally compact mixing Markov shift \ $ T$. As in the compact case (when \ $ T $\ \ is a shift of finite type) the existence of an embedding is solely determined by the periodic orbit counts of \ $ S$. However, in contrast to the compact case, the topology of the target system \ $ T $\ \ becomes important. This is demonstrated with the help of the Zeta Function Lemma, which in particular characterizes the periodic orbit counts and entropies of locally compact mixing Markov shifts.
    29. D.Fiebig, U.Fiebig, Z.Nitecki. Entropy and Preimage Sets. Ergod. Th & Dynam. Sys.(2003), 23, 1785-1806
      abstract: We study the relation between topological entropy and the dispersion of preimages. Symbolic dynamics plays a crucial role in our investigation. For forward expansive maps, we show that the two pointwise preimage entropy invariants defined by Hurley agree with each other and with topological entropy, and are reflected in the growth rate of the number of preimages of a single point, called a preimage growth point for the map. We extend this notion to that of an entropy point for a system, in which the dipersion of preimages of an \ $ \varepsilon $\ \ - stable set measures topological entropy. We show that for maps satisfying a weak form of the specification property, every point is an entropy point, and that every asymptotically h-expansive homeomorphism (in particular, every smooth diffeomorphism of a compact manifold) has entropy points. Examples are given of maps in which Hurley's invariants differ, and of homeomorphisms with no entropy points.
    30. D.Fiebig, M.Roy. Factor theorems for locally compact Markov shifts II. to appear in Forum Math.
      abstract: We study the problem of the existence of a factor map between two given locally compact transitive countable state Markov shifts.