Stability for the zigzag submonoids. (English) Zbl 0782.68069

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.


68Q45 Formal languages and automata
Full Text: DOI


[2] Anselmo, M., Sur les codes zigzag et leur décidabilité, Theoret. Comput. Sci., 74, 341-354 (1990) · Zbl 0701.68057
[3] Anselmo, M., Automates bilatères et codes zigzag, Thèse LITP n° 90-27 (1990) · Zbl 0701.68057
[4] Berstel, J., Transductions and Context-Free Languages (1979), Teubner: Teubner Stuttgart · Zbl 0424.68040
[5] Berstel, J.; Perrin, D., Theory of Codes (1985), Academic Press: Academic Press New York · Zbl 1022.94506
[6] Birget, J. C., Two-way automaton computations, RAIRO Inform. Théor. Appl., 24, 1, 47-66 (1990) · Zbl 0701.68058
[7] Van, Do Long; Le Saëc, B.; Litovsky, I., On coding morphisms for zigzag codes, Rapport interne LaBRI n° 91-11 (1991), to appear in RAIRO Inform. Théor. Appl. · Zbl 0766.68074
[8] Lindner, R.; Staiger, L., Algebraische Codierungstheorie-Theorie der sequentiellen Codierungen (1977), Akademie-Verlag: Akademie-Verlag Berlin · Zbl 0363.94016
[9] Pécuchet, J. P., Automates boustrophédon, semi-groupe de Birget et monoide inversif libre, RAIRO Inform. Théor. Appl., 19, 1, 71-100 (1985) · Zbl 0604.68094
[10] Schützenberger, M. P., Une théorie algébrique du codage, Séminaire Dubreil-Pisot (1955-1956), Exposé n° 15
[11] Tilson, B., The intersection of free submonoids is free, Semigroup Forum, 4, 345-350 (1972) · Zbl 0261.20060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.