Sur les générateurs algébriques et linéaires

Summary

We study some properties of algebraic and linear generators. We show that the algebraic language E generated by the grammar: S → aSbSc + d dominates every algebraic language by faithful sequential mappings. We deduce that, for every algebraic language L′ and every algebraic generator L, there exists a faithful rational function τ such that L′=τ(L). This result, which does not hold for the family of linear languages, permits us to show that no algebraic generator belongs to the family EDTOL. Also, we prove if L is a linear generator then L # is a ‘sequential’ generator for Lin.

Résumé

Nous étudions certaines propriétés des générateurs algébriques et linéaires. Nous montrons que le langage algébrique E engendré par la grammaire: S → aSbSc + d domine tous les langages algébriques par applications séquentielles fidèles. Nous en déduisons que pour tout langage algébrique L′ et tout générateur algébrique L, il existe une transduction rationnelle τ fonctionnelle et fidèle telle que L′=τ(L). Ce résultat, qui n'est pas vérifié pour la famille, Lin, des langages algébriques linéaires, nous permet de montrer qu'aucun générateur algébrique n'appartient à la famille EDTOL. Enfin, nous établissons que si L est un générateur linéaire, L # est un générateur ‘séquentiel’ pour Lin.