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

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


68Q45 Formal languages and automata
Full Text: DOI EuDML


[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
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.