Automates two-way à multiplicité

Automates two-way à multiplicité

Une question classique en théorie des automates concerne la puissance d’expression d’un outil et plus particulièrement la différence entre les sys- tèmes unidirectionnels et les systèmes bidirectionnels. Il est bien connu que les automates bidirectionnels peuvent être convertis en automates unidirec- tionnels et donc reconnaissent la même famille de langages [46, 43]. Cela dit depuis quelques années, il s’est avéré que cette équivalence n’est plus vraie dans le cas des automates bidirectionnels pondérés. Ainsi, dans ce cha- pitre, nous traitons des versions à multiplicité de ces outils. Dans [2] une construction pour passer d’un automate bidirectionnel à multiplicité (2-WFA pour two-way weighted finite automaton) à un automate unidirectionnel à multiplicité (1-WFA) est décrite ; cela requiert quelques hypothèses sur le semi-anneau (la commutativité) et sur l’automate lui-même. Une étude pour permettre de caractériser les langages reconnus par les transducteurs bidirec- tionnels a été proposée dans [22]. Dans une première partie, nous étudions plus précisément cette trans- formation et nous montrons qu’elle préserve la non-ambiguïté, mais pas le déterminisme. Nous présentons également une construction pour convertir un 1-WFA non-ambigu en un 2-WFA déterministe. En conséquence, sur les semi-anneaux commutatifs, à la différence du cas des automates unidirec- tionnels, les 2-WFA non-ambigus ne sont pas plus puissants que les 1-WFA déterministes.

Dans la seconde partie, nous traitons le cas particulier des automates min-plus qui se sont vus accordé beaucoup d’attention ces 3 dernières décennies. Le semi-anneau N-min-plus est l’une des extensions les plus simples du semi- Ici, nous étudions les automates bidirectionnels min-plus. Quand les poidssont tous positifs, nous étendons le résultat classique [46, 43] qui établit qu’un automate bidirectionnel fini est équivalent à un automate unidirectionnel fini. Ensuite, nous montrons qu’en règle générale certains mots peuvent être acceptés dans un automate bidirectionnel par une famille de calculs dont la borne inférieure des poids est −∞. Dans ce cas, le comportement de l’auto- mate peut ne pas être rationnel. Nous prouvons que l’existence de tels mots acceptés est décidable. En revanche, nous prouvons que pour un automate Z-min-plus donné, il est indécidable s’il existe un mot accepté avec un poids Jusqu’à présent, les automates que nous avons manipulés se « contentaient » d’accepter ou non des éléments d’un monoïde. Il est possible d’être plus pré- cis en comptant les calculs réussis pour un élément donné. Les compter ne veux pas nécessairement dire à l’aide d’entiers, tout ensemble dont la struc- ture permet de faire les calculs qui nous intéressent serait acceptable. Cette structure est celle des semi-anneaux . . .gie (lorsque M est quelconque) qui nécessiterait des notions de limite et de continuité, nous allons nous contenter de traiter le cas des automates sur le monoïde libre qui permettent une définition quasi directe d’une topologie sur KhhA∗ii.

Les définitions de calcul, de calcul réussi et d’étiquette de calcul restent les mêmes. On ajoutera seulement que le poids d’un calcul est égal au produit (dans l’ordre) des poids des transitions qui le composent et que le poids d’un mot u de A∗ dans l’automate est égal à la somme des poids des calculs réussis étiquetés par u. autrement dit des automates à multiplicité dans B. De ce fait, on peut dé- finir une construction qui passe d’un K-automate au B-automate associé en basculant à 1B les poids non nuls (différents de 0K) de toutes les transitions de l’automate de départ. C’est sur la base de cette remarque que l’on pose cative dans ce semi-anneau est la somme ordinaire, le poids d’un calcul dans cet automate est la somme des poids de ses transitions. Cet automate est déterministe (cf. Définition 1) et donc il y a un unique calcul pour chaque mot. Le comportement de cet automate est très simple. Pour tout block de ’a’, il vérifie à l’aide d’une lecture gauche-droite, si la longueur de ce block est impaire ; si elle l’est, une lecture droite-gauche calcule la longueur du block ; sinon l’automate va au block de ’a’ suivant. Au final, le poids d’un mot cor- respond à la somme des longueurs des blocks de ’a’ de longueur impaire.Le poids d’un mot est défini si et seulement si la famille de poids de tous les calculs étiquetés par ce mot est sommable et le comportement de A est défini si le poids de tout mot accepté est défini. Pour plus de détails et discussion sur les semi-anneaux topologiques, se référer à [36].