Stability for the zigzag submonoids

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.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Stability for the zigzag submonoids

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