SOFIC SHIFTS WITH SYNCHRONIZING PRESENTATIONS

A sofic shift S is a symbolic dynamical system that can be viewed as a set of all bi-infinite sequences obtained by reading the labels of al l bi-infinite paths in a finite directed labeled graph G. The presenta tion G is synchronizing if for every vertex upsilon there is a word x( upsilon) such that every path in G labeled with x(upsilon) has upsilon as a terminal vertex. We present an example of a subshift of finite t ype that has no unique minimal deterministic presentation and we show that if a sofic shift has a synchronizing, deterministic presentation (sdp), then it has a unique minimal one. Irreducible sofic shifts, sub shifts of finite type and nonwandering systems have synchronizing, det erministic presentations. We give an intrinsic characterization of a s ofic shift S that has an sdp in terms of the syntactic monoid M(S) of the factor language F(S) of S. Another characterization of sofic shift s with sdp's is given in terms of the predecessor sets. We show that a sofic shift can have at most one bi-synchronizing presentation.