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 all bi-infinite paths in a finite directed labeled graph G. The presentation G is synchronizing if for every vertex v there is a word x v such that every path in G labeled with x v has v as a terminal vertex. We present an example of a subshift of finite type 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, subshifts of finite type and nonwandering systems have synchronizing, deterministic presentations. We give an intrinsic characterization of a sofic 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 shifts 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.

Authors

• Nataša Jonoska

Keywords

No keywords are indexed for this paper.