Fonctions séquentielles par morceaux

Fonctions séquentielles par morceaux

Dans la suite, nous nous intéressons à la fonction successeur d’un langage rationnel, en particulier à son calcul. Il apparaît donc utile de pouvoir classer cette fonction dans une sous-classe de fonctions rationnelles dans laquelle les fonctions peuvent avoir un calcul déterministe par des transducteurs.Nous étudions dans ce chapitre la classe des fonctions séquentielles par morceaux. Cette classe de fonctions a été définie dans [21] sous le nom de fonctions plurisousséquentielles. Les fonctions séquentielles par morceaux étendent naturellement les fonctions séquentielles, qui sont les fonctions qui peuvent être réalisés par des transducteurs ’déterministes en entrée’, c’est- à-dire tels que la lecture d’un mot se fait de manière déterministe et permet d’obtenir l’image de ce mot en un seul passage déterministe dans l’automate. Les fonctions séquentielles par morceaux peuvent être réalisées par une union finie de transducteurs réalisants des fonctions séquentielles ou, comme il a été montré dans [3], par des cascades de transducteurs séquentiels, c’est-à-dire une succession finie de transducteurs séquentiels telle que pour avoir l’image d’un mot, il faut lire celui-ci dans un transducteurs séquentiel puis l’état de sortie atteint détermine le transducteur séquentiel suivant qui lira l’image du mot obtenue.Nous étudions ensuite les classes Seqpm et coSeqpm des fonctions séquen- tielles et co-séquentielles par morceaux et leur positionnement dans l’espace des fonctions rationnelles par rapport aux classes des fonctions séquentielles et co-séquentielles [3].

Les transducteurs réalisant les fonctions séquentielles par morceaux ontdéjà été étudiés dans [21], et, en particulier, une preuve de la décidabilité deLes fonctions séquentielles sont particulièrement étudiées car elles peuvent être réalisées par des transducteurs dont le comportement ressemble à celui des automates déterministes. C’est-à-dire que l’on peut lire le mot d’entrée de manière déterministe dans le transducteur et obtenir ainsi l’image du mot avec une complexité linéaire en la taille du mot d’entrée. Nous rappe- lons dans cette section la définition et certaines caractérisations des fonctions séquentielles et des transducteurs qui leur sont associés. Pour les preuves manquantes de ce chapitre, le lecteur peut se référer à [43, IV].Par fonction séquentielle nous entendons ce qui est également commu- nément appelé dans la littérature fonction sous-séquentielle (cf. [19] ou [7]). Nous définissons tout d’abord les transducteurs séquentiels :Il est également possible de voir les transducteurs co- séquentiels, en prenant leur transposé, comme des transducteurs séquen- tiels qui lisent les mots de droite à gauche. Un tel transducteur sera appelé transducteur séquentiel droit – par opposition aux transducteurs séquentiels classiques qui pourront également être qualifiés de gauche –. Il est à noter que le terme gauche ou droit ne change pas la définition du transducteur séquentiel mais uniquement le sens de lecture du mot.

Nous choisissons de ne pas transcrire la notion de gauche/droit aux fonc- tions car elles associent des images à des mots sans tenir compte du sens de lecture du mot. Ainsi un fonction séquentielle sera réalisée par un trans- ducteur séquentiel – gauche – ou par un transducteur co-séquentiel droit – par exemple le transposé du précédent –. Les fonctions co-séquentielles sont réalisées par des transducteurs séquentiels droits ou des transducteurs co-séquentiels gauches.Nous avons vu que les fonctions séquentielles sont les fonctions réalisées par des transducteurs séquentiels. Nous donnons maintenant une autre ca- ractérisation, quasi-topologique, classique des fonctions séquentielles.Il existe naturellement une définition duale en prenant une distance suf- fixe dIl existe des fonctions rationnelles qui ne sont ni séquentielles ni co- séquentielles. En particulier ce résultat est connu pour les fonctions suc- cesseurs de langages rationnels (cf. par exemple [25]) : la fonction succes- seur d’un langage rationnel n’est pas nécessairement séquentielle ou co- séquentielle.

Comme séquentialité et co-séquentialité sont deux notions duales, il est facile d’imaginer à partir de cet exemple une fonction qui serait séquentielle mais non co-séquentielle. Ainsi, la fonction réalisée par le transducteur sé- quentiel de la Figure 7.2 n’est pas co-séquentielle.Rappelons qu’un ensemble de mots X est préfixe si et seulement si pour tout mot u de X il n’y a pas de préfixe propre de u dans X. Il est intéressant de donner le résultat suivant, qui correspond au Lemme 2 de [21] :Afin d’étudier la décidabilité de la séquentialité de fonctions rationnelles – ou co-séquentialité par dualité –, nous allons donner une caractérisation des fonctions séquentielles. Plus précisément, le problème est de décider si un transducteur fonctionnel τ donné réalise une fonction séquentielle ou non. Ce problème a été résolu pour la première fois dans [19] (cf. également [7]) par une méthode qui utilise une caractérisation structurelle des transducteurs qui réalisent des fonctions séquentielles, à savoir que tous les états sont jumeaux deux à deux.