Summary: We consider partitioned graphs, by which we mean finite directed graphs with a partitioned edge set \({\mathcal{E}}={\mathcal{E}}^{-}\cup {\mathcal{E}}^{+}\). Additionally given a relation \({\mathcal{R}}\) between the edges in \({\mathcal{E}}^{-}\) and the edges in \({\mathcal{E}}^{+}\), and under the appropriate assumptions on \({\mathcal{E}}^{-},{\mathcal{E}}^{+}\) and \({\mathcal{R}}\), denoting the vertex set of the graph by \(\mathfrak{P}\), we speak of an \({\mathcal{R}}\)-graph \({\mathcal{G}}_{{\mathcal{R}}}(\mathfrak{P},{\mathcal{E}}^{-},{\mathcal{E}}^{+})\). From \({\mathcal{R}}\)-graphs \({\mathcal{G}}_{{\mathcal{R}}}(\mathfrak{P},{\mathcal{E}}^{-},{\mathcal{E}}^{+})\) we construct semigroups (with zero) \({\mathcal{S}}_{{\mathcal{R}}}(\mathfrak{P},{\mathcal{E}}^{-},{\mathcal{E}}^{+})\) that we call \({\mathcal{R}}\)-graph semigroups. We write a list of conditions on a topologically transitive subshift with property \((A)\) that together are sufficient for the subshift to have an \({\mathcal{R}}\)-graph semigroup as its associated semigroup.
Generalizing previous constructions, we describe a method of presenting subshifts by means of suitably structured finite labeled directed graphs \(({\mathcal{V}}, \Sigma,\lambda)\) with vertex set \({\mathcal{V}}\), edge set \(\Sigma\), and a label map that assigns to the edges in \(\Sigma\) labels in an \({\mathcal{R}}\)-graph semigroup \({\mathcal{S}}_{{\mathcal{R}}}(\mathfrak{P},{\mathcal{E}}^{-},{\mathcal{E}}^{-})\). We denote the presented subshift by \(X({\mathcal{V}},\Sigma,\lambda)\) and call \(X({\mathcal{V}},\Sigma,\lambda)\) an \({\mathcal{S}}_{{\mathcal{R}}}(\mathfrak{P},{\mathcal{E}}^{-},{\mathcal{E}}^{-})\)-presentation.
We introduce a property \((B)\) of subshifts that describes a relationship between contexts of admissible words of a subshift, and we introduce a property \((c)\) of subshifts that in addition describes a relationship between the past and future contexts and the context of admissible words of a subshift. Property \((B)\) and the simultaneous occurrence of properties \((B)\) and \((c)\) are invariants of topological conjugacy.
We consider subshifts in which every admissible word has a future context that is compatible with its entire past context. Such subshifts we call right instantaneous. We introduce a property \(RI\) of subshifts, and we prove that this property is a necessary and sufficient condition for a subshift to have a right instantaneous presentation. We consider also subshifts in which every admissible word has a future context that is compatible with its entire past context, and also a past context that is compatible with its entire future context. Such subshifts we call bi-instantaneous. We introduce a property \(BI\) of subshifts, and we prove that this property is a necessary and sufficient condition for a subshift to have a bi-instantaneous presentation.
We define a subshift as strongly bi-instantaneous if it has for every sufficiently long admissible word \(a\) an admissible word \(c\), that is contained in both the future context of \(a\) and the past context of \(a\), and that is such that the word \(ca\) is a word in the future context of \(a\) that is compatible with the entire past context of \(a\), and the word \(ac\) is a word in the past context of \(a\), that is compatible with the entire future context of \(a\). We show that a topologically transitive subshift with property \((A)\), and associated semigroup a graph inverse semigroup \({\mathcal{S}}\), has an \({\mathcal{S}}\)-presentation, if and only if it has properties \((c)\) and \(BI\), and a strongly bi-instantaneous presentation, if and only if it has properties \((c)\) and \(BI\), and all of its bi-instantaneous presentations are strongly bi-instantaneous.
We construct a class of subshifts with property \((A)\), to which certain graph inverse semigroups \({\mathcal{S}}(\mathfrak{P},{\mathcal{E}}^{-},{\mathcal{E}}^{+})\) are associated, that do not have \({\mathcal{S}}(\mathfrak{P},{\mathcal{E}}^{-},{\mathcal{E}}^{+})\)-presentations.
We associate to the labeled directed graphs \(({\mathcal{V}},\Sigma,\lambda)\) topological Markov chains and Markov codes, and we derive an expression for the zeta function of \(X({\mathcal{V}},\Sigma,\lambda)\) in terms of the zeta functions of the topological Markov shifts and the generating functions of the Markov codes.