Algebraic characterization of dendricity

If \(\mathcal{A}\) is a finite set representing an \textit{alphabet}, then \(\mathcal{A}^\ast\) and \(F_{\mathcal{A}}\) denote the free monoid, and the free group generated by \(\mathcal{A}\), respectively.\par Also, \(\mathcal{A}^\mathbb{Z}\) denote the set of two-sided infinite words equipped with the product topology of the discrete topology over \(\mathcal{A}\). A \textit{shift space} is a closed subset \(X\subseteq\mathcal{A}^\mathbb{Z}\) that is invariant under the shift map \((x_n)_{n\in\mathbb{Z}}\mapsto (x_{n+1})_{n\in\mathbb{Z}}\), and the \textit{language} of a shift space \(X\) is the set \(\mathcal{L}(X) = \{ x_i\cdots x_{j} \vert x\in X, \ i\leq j\}\cup\{\epsilon\}\), where \(\epsilon\) is the empty word. A shift space is \textit{minimal} (with respect to the inclusion of shift spaces) if, for every \(u\in \mathcal{L}(X)\), there exists \(n\) such that \(u\) is a factor of every \(w\in \mathcal{L}(X) \cap \mathcal{A}^n\).\N\NFor a word \(w \in \mathcal{L}(X)\), the set of \textit{(left) return words} to \(w\) is \(\mathcal{R}_X(w) = \{r \in \mathcal{A}^+ \vert rw\in \mathcal{L}(X)\cap w\mathcal{A}^\ast\setminus \mathcal{A}^+w\mathcal{A}^+\}\), where \(\mathcal{A}^+\) is the set of nonempty words.\N\NFor a shift space \(X\), and a word \(w\in\mathcal{L}(X)\), the left and right extensions of \(w\) can be described in terms of a bipartite graph, called \textit{extension graph} of \(w\). The word \(w\) is said to be \textit{dendric} if its extension graph is a tree. The space \(X\) is dendric in case each \(w\in\mathcal{L}(X)\) is dendric.\N\NThe Return Theorem states that in a minimal dendric shift space, every return set forms a basis of the free group [\textit{V. Berthé} et al., Monatsh. Math. 176, No. 4, 521--550 (2015; Zbl 1309.68160)].\N\NThe authors prove that the converse also holds, which leads to a complete algebraic characterization of dendric spaces.

Cites work

Cited in

(1)

Stability properties for subgroups generated by return words

This page was built for publication: Algebraic characterization of dendricity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6987868)