Sur les codes zigzag et leur décidabilité. (Zigzag codes and their decidability). (French) Zbl 0701.68057

Anselmo, M.

Theor. Comput. Sci. 74, No. 3, 341-354 (1990).

Summary: This paper deals with zigzag factorizations and zigzag codes. The language of “zigzag” over a regular language is represented by constructing a special family of two-way automata. Decidability of zigzag codes, previously shown for the finite languages, is proved here for all regular languages by the analysis of the set of “crossing sequences” produced by a two-way automaton in the family. We also obtain that it is decidable whether or not a two-way automaton of a certain type is non- ambiguous.

MSC:

68Q45	Formal languages and automata
03B25	Decidability of theories and sets of sentences

Keywords:

zigzag codes; regular language; two-way automata

References:

[1]	Anselmo, M., Automates et codes zigzag, Rapport LITP No. 88-74 (Novembre 1988), et à paraitre dans RAIRO Inform. Thér.
[2]	Berstel, J.; Perrin, D., Theory of Codes (1985), Academic Press: Academic Press New York · Zbl 1022.94506
[3]	Birget, J. C., Concatenations of inputs in a two-way automaton, Theoret. Comput. Sci., 63, 141-156 (1989) · Zbl 0664.68081
[4]	Birget, J. C., Two-way auromaton computations, (Technical Report No. 60 (July 1987), Dept. of Computer Science, Univ. of Nebraska: Dept. of Computer Science, Univ. of Nebraska Lincoln), et à paraître dans RAIRO Inform. Théor. · Zbl 1328.68072
[5]	Eilenberg, S., Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045
[6]	Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[7]	Howie, J. M., An Introduction to Semigroup Theory (1976), Academic Press: Academic Press New York · Zbl 0355.20056
[8]	Pécuchet, J. P., Automates buostrophédons, langages reconnaissables de mots infinis et variétés de semigroupes, Thése d’Etat. Thése d’Etat, Automates buostrophédons, semi-groupe de Birget et monoide inversif libre. Thése d’Etat. Thése d’Etat, Automates buostrophédons, semi-groupe de Birget et monoide inversif libre, RAIRO Inform. Théor., 19, 17-100 (1985), LITP · Zbl 0604.68094
[9]	Moore, E. F., Sequential Machines: Selected Papers (1964), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0147.24107
[10]	Moore, E. F., Sequential Machines: Selected Papers (1964), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0147.24107