Systèmes entiers d'équations sur un alphabet fini et conjecture d'Ehrenfeucht (Q1087020)

A system S of equations over an alphabet \(\Sigma\) is called entire if \(S=\alpha^{-1}\circ \alpha\) for some morphism \(\alpha\) of \(\Sigma^*\) into a free monoid. For each morphism \(\alpha\) as above with finite \(\Sigma\) and \(\alpha^{-1}(1)=\{1\}^ a \)''shuffle automaton'' \({\mathcal U}(\alpha)\) is introduced, which recognizes a rational language K(\(\alpha)\) over some alphabet \(\Delta\) such that \(\alpha^{-1}\circ \alpha =\{(\lambda (x),\mu (x))|\) \(x\in K(\alpha)\}\) for certain morphisms \(\lambda\), \(\mu\) of \(\Delta^*\) into \(\Sigma^*\). From a theorem of Nivat (characterization of rational relations) it follows that all entire systems over a finite alphabet are rational. The relation of these notions withthe Ehrenfeucht conjecture (recently solved by \textit{M. H. Albert} and \textit{J. Lawrence} [ibid. 41, 121-123 (1985; Zbl 0602.68066)] is then discussed and optimal algorithms for determining \({\mathcal U}(\alpha)\) and the finite equivalent subsystem of \(S=\alpha^{- 1}\circ \alpha\) are given.