Stability for the zigzag submonoids (Q1208713): Difference between revisions

Consider an alphabet \(A=\{a_ 1,\ldots,a_ k\}\) and the free group \(\mathbb{F}(A)\) generated by \(\{a_ 1,\ldots,a_ k,| a_ 1^{-1}\), \(\ldots,a_ k^{-1}\}\). A word \(w \in A^*\) is zigzag generated by \(X \subseteq A^*\) in \(\mathbb{F}(A)\) if \(w=x_ 1^{\varepsilon_ 1}\ldots x_ n^{\varepsilon_ n}\) where \(x_ i \in X\), \(\varepsilon_ i \in\{1,- 1\}\) and \(x_ 1^{\varepsilon_ 1} \ldots x_ i^{\varepsilon_ i}\) is a prefix of \(w\) for every \(i\leq n\). (In particular, \(x_ 1^{\varepsilon_ 1} \ldots x_ i^{\varepsilon_ i} \in A^*)\). This zigzag generation allows in a natural way to define zigzag submonoids of \(A^*\), and furthermore zigzag codes, zigzag free languages etc. The authors introduce the notion of stability for zigzag monoids. It is shown that the classes of zigzag stable submonoids and zigzag free submonoids coincide and that the property of being zigzag stable is decidable for zigzag submonoidds of \(A^*\) which are regular languages.