On subshift presentations

Abstract

We consider partitioned graphs, by which we mean finite strongly connected directed graphs with a partitioned edge set $\mathcal{E}={\mathcal{E}}^{-}\cup {\mathcal{E}}^{+}$. With additionally given a relation $\mathcal{R}$ between the edges in ${\mathcal{E}}^{-}$ and the edges in ${\mathcal{E}}^{+}$, and denoting the vertex set of the graph by $\mathfrak{P}$, we speak of an 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 describe a method of presenting subshifts by means of suitably structured labelled directed graphs $(\mathcal{V},\Sigma ,\lambda )$ with vertex set $\mathcal{V}$, edge set $\Sigma$, and a label map that asigns to the edges in $\Sigma$ labels in an $\mathcal{R}$-graph semigroup ${\mathcal{S}}_{\mathcal{R}}(\mathfrak{P},{\mathcal{E}}^{-},{\mathcal{E}}^{-})$. We call the presented subshift an ${\mathcal{S}}_{\mathcal{R}}(\mathfrak{P},{\mathcal{E}}^{-},{\mathcal{E}}^{-})$-presentation. We introduce a Property $(B)$ and a Property (c), tof subshifts, and we introduce a notion of strong instantaneity. Under an assumption on the structure of the $\mathcal{R}$-graphs ${\mathcal{G}}_{\mathcal{R}}(\mathfrak{P},{\mathcal{E}}^{-},{\mathcal{E}}^{-})$ we show for strongly instantaneous subshifts with Property $(A)$ and associated semigroup ${\mathcal{S}}_{\mathcal{R}}(\mathfrak{P},{\mathcal{E}}^{-},{\mathcal{E}}^{-})$, that Properties $(B)$ and (c) are necessary and sufficient for the existence of an ${\mathcal{S}}_{\mathcal{R}}(\mathfrak{P},{\mathcal{E}}^{-},{\mathcal{E}}^{-})$-presentation, to which the subshift is topologically conjugate,

33 pages

References in corpus (6)

• A categorical invariant of flow equivalence of shifts
• A Construction of Subshifts and a Class of Semigroups
• On Certain Subshifts and their Associated Monoids
• Finite-type-Dyck shift spaces
• Presentations of symbolic dynamical systems by labelled directed graphs (Notes for a "mini-cours", SDA2, Paris 4-5 October 2007)
• Excluding words from Dyck shifts

Cited by in corpus (8)

• A categorical invariant of flow equivalence of shifts
• On $g$-functions for subshifts
• A Construction of Subshifts and a Class of Semigroups
• Finite-type-Dyck shift spaces
• Some notes on the classification of shift spaces: Shifts of Finite Type; Sofic Shifts; and Finitely Defined Shifts
• Excluding words from Dyck shifts
• On a class of highly symmetric Markov-Dyck shifts
• Encodings of trajectories and invariant measures