Invariants for subshifts via nested sequences of shifts of finite type (Q2773056)

This paper is motivated by Krieger's characterization of coded systems as those subshifts which contain an increasing sequence of irreducible shifts of finite type with dense union [\textit{W. Krieger}, On subshifts and topological Markov chains, in: Althöfer, Ingo (ed.), et al., Numbers, information and complexity. Dedicated to Rudolf Ahlswede on the occasion of his 60th birthday, Dordrecht: Kluwer Academic Publishers, 453--472 (2000; Zbl 0957.60073)]. NEWLINENEWLINENEWLINEThe authors call subshifts with this property presynchronized shifts, and the collection of points in the increasing sequence the presynchronizing points. Here the authors investigate the uniqueness (up to eventual equality) of such sequences. They consider both one-sided and two-sided shifts. They define an equivalence relation on the periodic presynchronizing points which captures all the possible choices of these sequences. In the one-sided case they show that there is only one dense equivalence class and show that the presynchronized class is the same as the half-synchronized systems.NEWLINENEWLINENEWLINEIn the two-sided case while transitive sofic systems or synchronized systems have one dense class the authors show that there exist subshifts with more than one dense class. They define an ordering on equivalence classes and give realizations of all possible order structures.