Stability for the zigzag submonoids. (English) Zbl 0782.68069

Do Long Van; Le Saëc, Bertrand; Litovsky, Igor

Theor. Comput. Sci. 108, No. 2, 237-249 (1993).

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.

Reviewer: L.Staiger (Pulheim)

MSC:

68Q45

Formal languages and automata

Keywords:

submonoids; codes; stability

References:

[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