Stability for the zigzag submonoids (Q1208713): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Sur les codes zigzag et leur décidabilité. (Zigzag codes and their decidability) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3859267 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4430300 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Two-way automaton computations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On coding morphisms for zigzag codes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4138628 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3741089 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The intersection of free submonoids of a free monoid is free / rank | |||
Normal rank |
Revision as of 16:28, 17 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Stability for the zigzag submonoids |
scientific article |
Statements
Stability for the zigzag submonoids (English)
0 references
16 May 1993
0 references
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.
0 references
submonoids
0 references
codes
0 references
stability
0 references