Voir la source de Automate fini inambigu

[[Fichier:AutomateNonD%C3%A9terministe_%C3%A0_n%2B1_%C3%A9tats.jpg|upright=1.5|thumb|Un automate fini inambigu à ''n''+1 états reconnaissant les mots qui ont un ''a'' en position ''n'' depuis la fin. Un automate déterministe équivalent a au moins <math>2^n</math> états]]
En [[théorie des automates]], un '''automate fini inambigu''' (on dit aussi '''non ambigu''', en anglais  {{Citation étrangère|langue=en|unambiguous finite automaton}}, abrégé en ''UFA'') est un [[automate fini non déterministe]] d'un type particulier. C'est un automate qui, pour chaque mot accepté, ne possède qu'un seul calcul réussi. Tout [[automate fini déterministe]] est inambigu, mais la réciproque est fausse. Les trois types d'automates : non déterministe, inambigu, déterministe, reconnaissent les mêmes  [[Langage formel|langages formels]], à savoir les [[langage rationnel|langages réguliers]].

Le nombre d'états d'un automate inambigu peut être exponentiellement plus petit qu'un automate déterministe équivalent. En contre-partie, certains problèmes sont plus difficiles à résoudre pour les automates inambigus que pour les automates déterministes. Par exemple, partant d'un automate ''{{math|A}}'', un automate ''{{math|A'}}'' reconnaissant le complément du langage accepté par ''{{math|A}}'' se construit en temps linéaire si ''{{math|A}}'' est déterministe, mais il a été démontré qu'il ne peut être calculé en temps polynomial si ''{{math|A}}'' est inambigu<ref name="Raskin">{{Article
|langue=
|auteur1=Mikhail Raskin
|titre= A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
|périodique= Arxiv
|volume=
|numéro=
|date= 14 février 2018 
|pages=
|issn=
|arxiv = 1711.03993
|consulté le=3 mai 2018
}}. Accepté pour ICALP 2018 à Prague.</ref>. 

La notion d'automate inambigu se généralise à d'autres modèles de machines ou de calcul. Un présentation générale a été donnée par Thomas Colcombet<ref>{{harvsp|Colcombet|2015|p=}}.</ref>.

== Définition ==
Un [[automate fini non déterministe]] <math>\mathcal{A}=(Q, I, \mathcal{F}, T)</math>, où <math>\mathcal{F}</math> est l'ensemble des transitions, <math>I</math> l’ensemble des états initiaux et <math>T</math> l'ensemble des états terminaux, est dit '''inambigu''' si, pour tout mot <math>w=a_1\cdots a_n</math> reconnu par l'automate, il existe un seul chemin réussi d'étiquette <math>w</math>, donc un seul chemin
:<math>c=(i,a_1,p_1)(p_1,a_2,p_2)\cdots(p_{n-1},a_n,t)</math>, avec <math>i\in I</math> et   <math>t\in T</math>.

== Exemple ==
Soit <math>L_n=A^*aA^{n-1}</math> l'ensemble des mots sur l'[[alphabet]] binaire <math>A=\{a,b\}</math> dont la lettre en position <math>n</math> depuis la fin est un <math>a</math>. Les figures ci-contre montrent un automate inambigu reconnaissant ce langage pour ''n=2'', et un automate déterministe pour ce même langage. 
[[File:Unambiguous finite autaton for (a+b)*a(a+b)^2.svg|thumbnail|Automate inambigu pour le langage <math>L_2</math>.]]
[[File:Unambiguous finite automaton.svg|thumbnail|Automate déterministe pour le langage <math>L_2</math>.]]

L'automate déterministe minimal acceptant <math>L_n</math> a <math>2^n</math> états, alors que l’automate inambigu pour le même langage n'a que <math>n+1</math> états.

== Propriétés ==

=== Test d'ambiguïté ===
On peut tester si un automate fini non déterministe à ''m'' transitions est inambigu en temps <math>O(m^3)</math>. On peut même calculer le ''degré'' d’ambiguïté, et savoir si l'ambiguïté est bornée, si elle croit polynomialement ou exponentiellement avec la longueur des mots<ref>{{harvsp|Allauzen|Mohri|Rastogi|2011}}.</ref>.

=== Inclusion ===
Le problème d'inclusion consiste à tester si le langage reconnu par un automate <math>A</math> est contenu dans le langage reconnu par un automate <math>B</math>. Le problème est bien entendu décidable. La question est celle de sa complexité.

Le problème de l'inclusion pour les automates inambigus est décidable en temps polynomial : il est dans la classe [[P (complexité)|PTIME]] alors que ce même problème est PSPACE-complet pour les automates non déterministes<ref name="L">{{harvsp|Löding|2013|loc=Transparents}}.</ref>{{,}}<ref name="StearnsHunt" />. C'est d'ailleurs ce problème, décrit par Meyer et Stockmeyer en 1972<ref>{{harvsp|id=MS|texte=Meyer et Stockmeyer, 1972|p=}}.</ref> qui est le premier problème de cette classe.

La démonstration de cette propriété utilise le fait que le [[produit cartésien]] de deux automates inambigus est également inambigu<ref name="L" />. 

{{Boîte déroulante/début|titre=Esquisse de la preuve}}

Soient <math>A</math> et <math>B</math> deux automates, et <math>L(A)</math> et <math>L(B)</math> les langages acceptés. On a <math>L(A)\subset L(B)</math> si et seulement si <math>L(A\times B)=L(A)</math>, où <math>A\times B</math> désigne l'automate produit reconnaissant <math>L(A)\cap L(B)</math>. Les deux ensembles <math>L(A\times B)</math> et <math>L(A)</math> sont égaux si et seulement si le nombre de mots de longueur <math>n</math> dans <math>L(A\times B)</math> et égal au nombre de mots de longueur <math>n</math> dans <math>L(A)</math> pour tout <math>n</math>. Comme ces suites de nombres de mots satisfont une relation de récurrence linéaire, il suffit de vérifier qu'elles sont égales sur leurs premiers termes, en fait pour <math>n</math> jusqu'au produit du nombre d'états de <math>A</math> et de <math>B</math>. Le nombre de mots de longueur <math>n</math> acceptés par un automate peut être calculé sur l'image commutative<ref name="L" />.

{{Boîte déroulante/fin}}

=== Universalité et équivalence ===

Le problème de l{{'}}''universalité'', c'est-à-dire de savoir si un automate accepte tous les mots, et le problème de l'équivalence, c'est-à-dire de savoir si deux automates acceptent les mêmes mots, sont tous deux dans la classe [[P (complexité)|PTIME]], par réduction au problème de l'inclusion.

==  Extensions==
Le coût en place de la transformation d'un automate inambigu en un automate déterministe est difficile à borner. Pour des alphabets unaires, une minoration est donnée par Okhotin<ref>{{harvsp|Okhotin|2012|p=}}.</ref> à l'aide d'une [[fonction arithmétique]] liée à la [[fonction de Landau]].
 
La notion d’ambiguïté s'étend aux [[Transducteur fini|transducteurs finis]] : un transducteur est ''fonctionnel'' si la transformation qu'il réalise est une fonction (partielle), il est inambigu si, pour tout mot, il existe un seul calcul de la valeur de la fonction. Il est décidable si la transduction réalisée par un transducteur est une fonction.

Il y a aussi une interprétation algébrique naturelle du degré d’ambiguïté au moyen d'[[automate pondéré|automates pondérés]] : on associe à chaque transition le poids 1 dans le [[monoïde]] des [[Entier naturel|entiers naturels]] ; le poids associé à un mot est alors la simplement le nombre de chemins acceptant ce mot.  

Enfin, il existe la même notion pour les mots infinis et les automates les reconnaissants comme les [[automate de Büchi|automates de Büchi]]. Dans ce cas, il y a différence entre automates non déterministes et automates déterministes, puisque ces derniers reconnaissent moins de langages. Les automates de Büchi inambigus reconnaissent les mêmes langages que les automates de Büchi non déterministes<ref name="L" />{{,}}<ref>{{harvsp|Arnold|1983|p=}}.</ref>.

L'ambiguïté d'un automate fini est simplement relié à la notion d'ambiguïté dans les grammaires formelles par le biais de la correspondance entre les automates et les grammaires régulières : chaque dérivation dans une grammaire régulière correspond à un calcul dans l'automate correspondant. C'est d'ailleurs la notion de grammaire qui est mise en avant dans l'article historique de Stearns et Hunt<ref name="StearnsHunt">{{harvsp|id=StearnsHunt|texte=Stearns, Hunt, 1981|p=}}.</ref>

== Complexité des opérations ==
{{article détaillé|Complexité en états}}
La complexité inambigüe d’un langage, notée usc(''L'') (pour {{Citation étrangère|langue=en|unambiguous state complexité}}) est par définition le nombre minimal d’états d’un automate inambigu reconnaissant le langage ''L''.

=== Bornes connues ===
Soient ''L'', ''M'' des langages rationnels sur un alphabet commun, avec usc(''L'')=''m'' et  usc(''M'')=''n''. On a les résultats suivants<ref name="jj">{{harvsp|id=jj|Jirásek ''et. al.''|2016}}.</ref> :
*image miroir : <math>\text{usc}(L^\sim) = \text{usc}(L)</math>, où <math>L^\sim</math> est le langage miroir ;
*intersection : <math>\text{usc}(L\cap M)\le  mn</math>, et la borne est atteinte sur un alphabet à au moins 2 lettres.
*quotient gauche : <math>\text{usc}(L^{-1} M)\le  2^n-1</math>, et la borne est atteinte sur un alphabet à au moins 2 lettres.
*quotient droit : <math>\text{usc}(L M^{-1})\le  2^n-1</math>, et la borne est atteinte sur un alphabet à au moins 2 lettres.
*[[Mot (mathématiques)#Terminologie supplémentaire|mélange]] :<math> \text{usc}(L \text{ш}\ M)\le  2^{nm}-1</math>, et la borne est atteinte sur un alphabet à au moins 5 lettres.
*produit : <math>\text{usc}(L M)\le 3/4 \cdot 2^{n+m}-1</math>,  pourvu que <math>n, m\ge 2</math>, et la borne est atteinte sur un alphabet à au moins 6 lettres.
*[[étoile de Kleene|étoile propre (opération plus)]] : <math>\text{usc}(L)\le 3/4 \cdot 2^{m}-1</math>,  pourvu que <math>m\ge 2</math>, et la borne est atteinte sur un alphabet à au moins 3 lettres.
*[[étoile de Kleene|étoile]] : <math>\text{usc}(L)\le 3/4 \cdot 2^{m}</math>,  pourvu que <math>m\ge 2</math>, et la borne est atteinte sur un alphabet à au moins 3 lettres.

Il est intéressant de comparer la complexité des opérations sur les langages au moyen d'[[automate fini déterministe | automates déterministes]], d'automates inambigus et [[automate fini non déterministe|automates non déterministes]]. Pour cela, on introduit les notations :
* sc(''L''), nombre minimal d’états d’un automate déterministe reconnaissant le langage ''L''.
* usc(''L''), comme ci-dessus le nombre minimal d’états d’un automate inambigu reconnaissant le langage ''L''.
* nsc(''L''), nombre minimal d’états d’un automate non déterministe déterministe reconnaissant le langage ''L''.
Dans la table suivante, les complexités sont résumées pour des langages donnés de complexité inambiguë ''n'' et ''m''<ref name="jj" /> :

{| class="wikitable center" style="width: 60%;font-size:95%;border:0px;text-align:left;line-height:150%;"
|-
! Opération
! sc
! nsc
! usc
|-
| miroir || <math>2^n</math> || <math>n+1</math> || <math>n</math>
|-
| intersection || <math>mn</math> ||<math>mn</math> ||<math>mn</math>
|-
| quotient gauche || <math>2^n-1</math> || <math>n+1</math> || <math>2^n-1</math>
|-
| quotient droit || <math>n</math> || <math>n</math> || <math>2^n-1</math>
|-
| étoile positive || <math>3/4\cdot 2^n-1</math> || <math>n</math> || <math>3/4\cdot 2^n-1</math>
|-
| étoile  || <math>3/4\cdot 2^n</math> || <math>n+1</math> || <math>3/4\cdot 2^n</math>
|-
| mélange || <math>\ge2^{(m-1)(n-1)}</math> || <math>mn</math> || <math>2^{mn}</math>
|-
| produit || <math>m\cdot 2^n</math> ||<math> m+n</math> || <math>3/4\cdot 2^{m+n}-1</math>
|-
| complément || <math>2^n</math> || <math> n</math> || <math>\le 2^{0,79n+\log n}</math> <br/> <math>\ge n^{d}\ \forall d</math><ref name="Raskin"/>
|}

=== Calcul de minorants ===

Il existe une méthode générale pour calculer des minorants de la complexité inambigüe. Couplée avec la construction en général plus facile, d'un automate  inambigu, elle fournit une borne inférieur à la complexité d'une opération sur les automates inambigus. La méthode est basée sur le calcul du [[Rang (mathématiques)|rang]] d'une matrice associée à un automate ; elle a été développée par Schmidt dans une thèse non publiée de 1978, puis par Leung<ref name="Leung2005">
{{article|langue=en
|nom1=Leung|prénom1=Hing
|titre=Descriptional complexity of nfa of different ambiguity
|journal=International Journal of Foundations of Computer Science
|volume=16|numéro=05
|année=2005|pages=975–984|doi=10.1142/S0129054105003418}}
</ref>, et par Hromkovič et al.<ref name="HromkovičSeibert2002">
{{article|langue=en
|auteur1=[[Juraj Hromkovič]]
|nom2=Seibert|prénom2=Sebastian
|nom3=Karhumäki|prénom3=Juhani
|nom4=Klauck|prénom4=Hartmut
|nom5=Schnitger|prénom5=Georg
|titre=Communication Complexity Method for Measuring Nondeterminism in Finite Automata
|journal=Information and Computation
|volume=172|numéro=2
|année=2002|pages=202–217
|doi=10.1006/inco.2001.3069}}</ref>, et est reprise dans Jirásek et al.<ref name="jj"/>. 

On considère un  [[automate fini non déterministe]] <math>\mathcal{A}=(Q, I, \mathcal{F}, T)</math> sur un alphabet ''A'', où  <math>I</math> et <math>T</math> sont des ensembles d'états initiaux et terminaux. 

Un état <math>q</math> est dit ''accessible'' à partir de l'état <math>p</math> par le mot <math>w</math> s'il existe un chemin d'étiquette <math>w</math> de <math>p</math> à <math>q</math>. Un ensemble <math>S\subseteq Q</math> d'états est dit ''accessible'' s'il existe un mot <math>w</math> tel que <math>S</math> est l'ensemble des états accessibles à partir d'un état initial par un chemin d'étiquette <math>w</math>. On dit qu'un ensemble <math>P</math> d'états  est ''coaccessible'' si <math>P</math> est accessible dans l'[[automate transposé]] de <math>\mathcal{A}</math><ref>L'automate transposé est l'automate obtenu en inversant le sens des transitions, et en échangeant les états initiaux avec les états terminaux.</ref>.

Les ensembles non vides d'états qui sont accessibles ou coaccessibles  sont notés
:<math>\mathcal{R}=\{S\subseteq Q\mid S \ \text{accessible}, S\ne\emptyset\}</math>   et   <math>\mathcal{C}=\{P\subseteq Q\mid P \ \text{accessible}, P\ne\emptyset\}.</math>

On a alors la propriété suivante :

:L'automate <math>\mathcal{A}</math> est inambigu si et seulement si deux ensembles d'états <math>S</math> de <math>\mathcal R</math> et <math>P</math> de <math>\mathcal C</math> quelconques ont au plus un élément en commun :  <math>|S\cap R|\le1.</math>

On s'en sert pour établir le résultat suivant, qui relie la complexité du langage au [[Rang (mathématiques)|rang]] d'une matrice : 
<!-- 
:Soit <math>M</math> la matrice dont les lignes sont indicées par les éléments de <math>\mathcal{R}</math> et le colonnes indicées par les éléments de <math>\mathcal{C}</math>, et dont le coefficient d'indice <math>(S,P)</math> est égal à 0 ou 1 selon que  l'intersection de <math>S</math> et <math>P</math> est vide ou non. Alors on a <math>\text{usc}(L)\ge \operatorname{rang}(M)</math>. -->

{{Théorème|Soit <math>M</math> la matrice dont les lignes sont indicées par les éléments de <math>\mathcal{R}</math> et le colonnes indicées par les éléments de <math>\mathcal{C}</math>, et dont le coefficient d'indice <math>(S,P)</math> est égal à 0 ou 1 selon que  l'intersection de <math>S</math> et <math>P</math> est vide ou non. Alors on a <math>\text{usc}(L)\ge \operatorname{rang}(M)</math>.}}

=== Exemple  ===
Pour vérifier que la complexité de l'intersection atteint bien la valeur  <math>mn</math> pour des automates à  <math>m</math> et  <math>n</math> états, on considère des langages et automates particuliers, et on montre que l'automate pour l'intersection, qui a <math>mn</math> états, ne peut être remplacé par un automate inambigu plus petit à l'aide du théorème.

On considère les langages sur l'alphabet <math>\{a,b\}</math> définis par
<math>K=\{w\mid |w|_a=m-1\}</math> et <math>L = \{w\mid |w|_b=n-1\}</math>, pour <math>m</math> et <math>n</math> fixés. Ce sont donc les langages de mots contenant exactement <math>m-1</math> lettres <math>a</math> respectivement exactement <math>n-1</math> lettres <math>b</math>.  Des automates inambigus (déterministe et incomplets) acceptant ces langages sont 
<math>\mathcal{A}=(Q_A, 0, m-1, F_A)</math> et <math>\mathcal{B}=(Q_B, 0, n-1, F_B)</math>, avec <math>Q_A=\{0,\ldots,m-1\}</math>, <math>Q_B=\{0,\ldots,n-1\}</math>, et les flèches de <math>F_A</math> composées de <math>(i,a,i+1)</math> pour <math>0\le i \le m-2</math> et  <math>(j,b,j)</math> pour tout j, et pour <math>F_B</math> composées de <math>(i,a,i)</math> pour tout i et <math>0\le i \le m-1</math> et  <math>(j,b,j+1)</math> pour <math>0\le j \le n-2</math>. 

L’automate produit est l’automate <math>(Q_A\times Q_B, (0,0), (m-1,n-1), F)</math>, où l'ensemble de flèches <math>F</math> est composé des flèches <math>((p,q),a,(p',q'))</math>  pour <math>(p,a,p')\in F_A</math> et <math>(q,a,q')\in F_B</math>.

Tout ensemble singleton <math>(i,j)</math> est accessible dans l’automate produit (par <math>a^ib^j</math>), et est coaccessible (par <math>a^{m-1-i},b^{n-1-j}</math>), et seuls des ensembles singletons sont accessibles ou coaccessibles.
La matrice <math>M</math> de l’énoncé est donc la [[matrice identité]] d’ordre <math>mn</math>, ce qui donne la borne inférieure pour l'intersection<ref name="jj" />.

== Notes et références ==
{{Références|taille=30}}
== Bibliographie ==
*{{article
 | libellé = '''Löding''' 
 |auteur=Christof Löding 
 |titre=Unambiguous Finite Automata
 |journal=Developments in Language Theory
 |année=2013|pages=29–30
 |url=http://old.automata.rwth-aachen.de/users/loeding/unambiguous-dlt13.pdf}} — Les transparents de sa présentation.
*{{Article 
 | libellé = '''Isaak et Löding''' 
 | auteur1 = Dimitri Isaak | auteur2 = Christof Löding 
 | titre = Efficient inclusion testing for simple classes of unambiguous \u03c9-automata 
 | périodique = Information Processing Letters 
 | volume = 112 | numéro = 14-15 
 | mois = août | année = 2012 
 | pages = 578-582 
 | doi = 10.1016/j.ipl.2012.04.010 
 | url texte = http://old.automata.rwth-aachen.de/download/papers/loeding/IPL-IL12.pdf}}.
*{{Article 
 | libellé = '''Meyer et Stockmeyer'''
 | auteur1 = Albert R. Meyer | auteur2 = Larry J. Stockmeyer 
 | titre = The equivalence problem for regular expressions with squaring requires exponential space
 | périodique = 13th Annual Symposium on Switching and Automata Theory (SWAT 1972) 
 | éditeur = Institute of Electrical & Electronics Engineers (IEEE) 
 | mois = octobre | année = 1972 | doi = 10.1109/swat.1972.29 |pages= 125-129|id=MS}}.
*{{Article 
 | libellé = '''Arnold''' 
 | auteur = André Arnold 
 | titre = Rational ω-languages are non-ambiguous 
 | périodique = Theoretical Computer Science 
 | volume = 26 | numéro = 1-2 | mois = septembre | année = 1983 
 | pages = 221-223  
 | doi = 10.1016/0304-3975(83)90086-5}}.
*{{Article 
 | libellé = '''Okhotin''' 
 | auteur = Alexander Okhotin 
 | titre = Unambiguous finite automata over a unary alphabet 
 | périodique = Information and Computation
 | volume = 212 
 | mois = mars | année = 2012 
 | pages = 15-36 
 | doi = 10.1016/j.ic.2012.01.003
 | url=http://ac.els-cdn.com/S0890540112000090/1-s2.0-S0890540112000090-main.pdf?_tid=fbc8bd62-2d3d-11e6-b5c9-00000aab0f26&acdnat=1465365672_b3c53f97e1ad2b07bde6f7525860bbd0}}.
*{{Article | id = StearnsHunt 
| libellé = '''Stearns et Hunt'''
| auteur1 = Richard E. Stearns | auteur2 = Harry B. Hunt 
| titre = On the equivalence and containment problems for unambiguous regular expressions, grammars, and automata 
| périodique = 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981) 
| éditeur = Institute of Electrical & Electronics Engineers (IEEE) 
| mois = octobre 
| année = 1981 
| pages=74–81
| doi = 10.1109/sfcs.1981.29}}.
*{{article
 |langue=|auteur1=|volume=22|date=|issn=|doi=10.1142/S0129054111008477|arxiv=0802.3254|lire en ligne=|pages=883–904
 |libellé = '''Allauzen et al.'''
 |nom1=Allauzen|prénom1=Cyril|nom2=Mohri|prénom2=Mehryar|nom3=Rastogi|prénom3=Ashish
 |titre=General algorithms for testing the ambiguity of finite automata and the double-tape ambiguity of finite-state transducers
 |journal=International Journal of Foundations of Computer Science
 |numéro=04
 |année=2011
 }}
*{{chapitre
 |libellé = '''Colcombet'''
 |nom1=Colcombet|prénom1=Thomas
 |titre=Unambiguity in Automata Theory
 |titre ouvrage= Descriptional Complexity of Formal Systems
 | numéro dans collection =9118 
 | collection=Lecture Notes in Computer Science 
 | année=2015
 | passage=3–18
 | doi=10.1007/978-3-319-19225-3_1
 | url = https://www.irif.fr/~colcombe/Publications/DCFS15-colcombet.pdf}}
*{{chapitre
 |id=jj
 |libellé = '''Jirásek et al.'''
 |nom1=Jirásek|prénom1=Jozef|nom2=Jirásková|prénom2=Galina|nom3=Šebej|prénom3=Juraj
 |titre= Operations on unambiguous automata
 |titre ouvrage= Developments in Language Theory
 |collection =Lecture Notes in Computer Science
 |numéro dans collection =9840
 |année=2016
 |passage=243–255
 |doi=10.1007/978-3-662-53132-7_20
 |url=http://im.saske.sk/~jiraskov/UFA/ufa.pdf|langue=|auteur1=|date=|issn=}}.

== Articles connexes ==
* [[Transducteur fini]]
* [[Automate pondéré]]
* [[Grammaire formelle]]
* [[Complexité en espace]]

{{Palette Automates finis et langages réguliers}}

{{portail|informatique théorique}}
[[Catégorie:Théorie des automates]]
[[Catégorie:Automates finis et langages réguliers]]