Automata and zigzag codes. (Automates et codes zigzag.) (French) Zbl 0735.68050

Anselmo, Marcella

RAIRO, Inform. Théor. Appl. 25, No. 1, 49-66 (1991).

Let \(X\) be an alphabet. \(X^*\) is the free monoid generated by \(X\) with 1 as identity element. Let \(L\) be a language over \(X\). On \(X^*\times X^*\) one defines re-writing steps \((u,v)\to(u',v')\) as follows. This step is possible if \(u=u'x\) and \(v'=xv\) or if \(v=xv'\) and \(u'=ux\). For a word \(w\), a sequence of re-writing steps without a loop that leads from \((1,w)\) to \((w,1)\) is called a zigzag factorization of \(w\) with respect to \(L\). A language \(L\) is called a zigzag code if every word in \(X^*\) has at most one zigzag factorization. Every zigzag code is indeed a code.
These definitions are motivated by Isbell’s theory of dominions in semigroups and the “zigzag theorem” [J. R. Isbell, Epimorphisms and dominions, Proc. Conf. Categorical Algebra, La Jolla 1965, 232–246 (1966; Zbl 0194.01601); see also J. M. Howie, An introduction to semigroup theory. London etc.: Academic Press (1976; Zbl 0355.20056)].
The zigzag re-writing steps correspond to elementary moves of 2-way automata (automates boustrophédons). This connection is explored in detail and used to prove that the property of being a zigzag code is decidable for finite \(L\). For infinite rational \(L\) this decidability problem is open in general.

Reviewer: H. Jürgensen

MSC:

68Q45

Formal languages and automata

Keywords:

zigzag factorization; zigzag code

Citations:

Zbl 0355.20056; Zbl 0194.01601

References:

[1]	1. J. BERSTEL et D. PERRIN, Theory of Codes, Academic Press, 1985. Zbl0587.68066 MR797069 · Zbl 0587.68066
[2]	2. S. EILENBERG, Automata, Languages and Machines, Academic Press, A, 1974.
[3]	3. J. E. HOPCROFT et J. D. ULLMAN, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979. Zbl0426.68001 MR645539 · Zbl 0426.68001
[4]	4. J. M. HOWIE, An introduction to Semigroup Theory, Academic Press, 1976. Zbl0355.20056 MR466355 · Zbl 0355.20056
[5]	5. J. P. PÉCUCHET, Automates boustrophédons, langages reconnaissables de mots infinis et variétés de semi-groupes, (Thèse d’État), L.I.T.P., mai 1986, I; ou bien,
[6]	Automates boustrophédons, semi-groupe de Birget et monoïde inversif libre, R.A.I.R.O. Inform. Théor., 1985, 19, n^\circ 1 p. 17-100. Zbl0604.68094 MR795773 · Zbl 0604.68094
[7]	6. J. C. SHEPHERDSON, The reduction of Two-Way Automata to One-Way Automata, I.B.M. J. Res., 1959, 3, 2, p. 198-200 ; et dans E. F. MOORE éd., Sequential Machines: Selected Papers, Addison-Wesley, 1964. Zbl0158.25601 MR103796 · Zbl 0158.25601