Omega-rational expressions with bounded synchronization delay (Q2354594): Difference between revisions

In 1965, Schützenberger published his celebrated result that the class of all star-free languages SF and all aperiodic languages AP coincide over finite words, i.e. \(\mathrm{SF}=\mathrm{AP}\). Perrin generalized the equality \(\mathrm{SF}=\mathrm{AP}\) to infinite words in [\textit{D. Perrin}, Lect. Notes Comput. Sci. 176, 134--148 (1984; Zbl 0577.68076)]. As noted by the authors of the present paper, ``In 1973 Schützenberger presented another characterization of aperiodic languages in terms of rational expressions where the use of the star operation is restricted to prefix codes with bounded synchronization delay and no complementation is used.'' The authors denote this class of languages by SD. Let \(A\) be a finite alphabet and \(A^*\) (resp. \(A^{\omega}\)) denote the set of finite (resp. infinite) words over \(A.\) A language \(K\subseteq A^*\) is called \textit{prefix-free} or a \textit{prefix code} if \(u,uv\in K\) implies \(u=uv.\) A prefix code \(K\) has \textit{bounded synchronization delay} if for some natural number \(d\) and for all \(u,v,w\in A^*\) we have: if \(uvw\in K^*\) and \(v\in K^d,\) then \(uv\in K^*.\) The authors note at the end of their introduction that ``We see three contributions in this paper: (1) We considerably simplify the classical proof \(\mathrm{SD}=\mathrm{AP}\) by using the algebraic tool of a local divisor [\dots] (2) We easily extend \(\mathrm{SD}=\mathrm{AP}\) to infinite words by the very same proof technique. (3) We establish that \(\mathrm{SF}=\mathrm{AP}\) is an immediate consequence of \(\mathrm{SD}=\mathrm{AP}\).