Automate linéairement borné

Automate linéairement borné

En informatique théorique, et en particulier en théorie des automates, un automate linéairement borné (en anglais linear bounded automaton, abrégé en LBA) est une machine de Turing non déterministe assujettie à des restrictions dans son mode opératoire.

Sommaire

Description

Un automate linéairement borné vérifie les trois conditions suivantes :

  1. Son alphabet d'entrée possède deux symboles particuliers qui servent comme marqueurs de fin gauche et droit.
  2. Ses transition ne peuvent écrire sur la bande au delà des marqueurs de fin.
  3. Ses transition ne peuvent pas déplacer les marqueurs gauche et droit au delà de leur position gauche respectivement droite.

Comme pour les machines de Turing, un automate linéairement borné possède une bande composée de cases susceptibles de contenir un symbole pris dans un ensemble fini appelé l'alphabet, une tête peut lire le contenu d'une case et y écrire et qui peut être déplacée d'une case à la fois, et enfin il possède un nombre fini d'états.

À la différence d'une machine de Turing, où la bande est supposée avoir une longueur potentiellement infinie, dans un automate linéairement borné, seule une portion contiguë de la bande, dont la longueur est une fonction linéaire de la longueur de la donnée, est accessible par la tête de lecture-écriture. Ce segment est délimité par les cases contenant les marqueurs de fin.

Automates linéairement bornés et langages contextuels

Les automates linéairement bornés reconnaissent exactement la classe des langage contextuel. Pour montrer qu'un langage contextuel est reconnu par un automate linéairement borné, on observe que dans une grammaire contextuelle, une étape d'une dérivation allonge toujours le mot produit. Si l'on essaie donc de réduire un mot en l'axiome, chaque étape revient à raccourcir le mot. C'est pourquoi une mémoire bornée suffit.

L'argument, dans l'autre sens, est un peu plus long.

Histoire

En 1960, Myhill (en) introduit un modèle d'automate appelé maintenant automate linéairement borné déterministe[1].

Peu de temps après, Landweber (en) prouve que les langages reconnus par les automates linéairement bornés déterministes sont contextuels[2].

En1964, Kuroda (en) introduit le modèle plus général d'automate linéairement borné (non déterministe) tel que décrit plus haut et a prouvé qu'ils acceptent exactement les langages contextuels[3].

Deux problèmes sur les automates linéairement bornés

Dans son article fondateur, Kuroda pose deux problèmes de recherche qui sont devenu célèbres sou le nom anglais LBA problems.

  • Le premier problème est de déterminer si la classe des langages acceptés par les automates linéairement bornés coïncide avec la classe des automates linéairement bornés déterministes. En d'autres termes, est-ce que tout langage contextuel peut être accepté par un automate linéairement bornés déterministe. En termes de complexité algorithmique, ce problème s'énonce
As-t-on l'égalité : NSPACE(O(n)) = DSPACE(O(n)) ou, avec d'autres notations, NLIN-SPACE=LIN-SPACE?
  • Le deuxième problème est de déterminer si la classe des langages reconnus par les automates linéairement bornés est fermée par complémentation. En termes de complexité algorithmique, ce problème s'énonce
As-t-on l'égalité :NSPACE(O(n)) = co-NSPACE(O(n))?

Déjà Kuroda a remarqué qu'une réponse négative au deuxième problème aurait entraîné une réponse négative au premier. Mais en fait, le deuxième problème a une réponse positive. Ceci est une conséquence du Théorème de Immerman-Szelepcsényi (en) reliant les classes NSPACE et co-NSPACE. Ce résultat, prouvé indépendamment par Neil Immerman (en)[4] et Róbert Szelepcsényi (en)[5] en 1987, leur a valu le prix Gödel en 1995. En ce qui concerne le premier problème, il est, en 2010, toujours ouvert.

Notes

  1. ↑ Myhill (1960)
  2. ↑ Landweber (1963)
  3. ↑ Kuroda (1964)
  4. ↑ Immerman (1988)
  5. ↑ Szelepcsényi (1988)

Références

  • John Myhill: Linearly Bounded Automata, WADD Technical Note 60-165, Wright-Patterson Air Force Base, Wright Air Development Division, Ohio, June 1960.
  • Peter S. Landweber: Three Theorems on Phrase Structure Grammars of Type 1, Information and Control (en) 6(2): 131-136 (1963)
  • Sige-Yuki Kuroda: Classes of Languages and Linear-Bounded Automata, Information and Control (en), 7(2): 207–223 (1964)
  • N. Immerman, Nondeterministic Space is Closed under Complementation, SIAM Journal on Computing 17, 1988, pp. 935–938.
  • R. Szelepcsényi, The Method of Forcing for Nondeterministic Automata, Bulletin of the EATCS 33, 1987, pp. 96–100 et Acta Informatica (en) 26(3): 279-284 (1988)

Traduction


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Automate linéairement borné de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Automate cellulaire — À gauche, une règle locale simple : une cellule passe d un état (i) au suivant (i+1) dans le cycle d états dès que i+1 est présent dans au moins 3 cellules voisines. À droite, le résultat (complexe) de l application répétée de cette règle… …   Wikipédia en Français

  • Automate fini — Pour les articles homonymes, voir Automate. Fig. 1 : Automate fini reconnaissant les écritures binaires des multiples de 3. Un automate fini (on dit parfois, par une traduction littér …   Wikipédia en Français

  • Automate sur les mots infinis — En informatique théorique, et spécialement en théorie des automates un automate sur les mots infinis ou ω automate est un automate fini, déterministe ou non, qui accepte des mots infins. Comme un tel automate ne s arrête pas, les conditions d… …   Wikipédia en Français

  • Automate de Muller — En informatique théorique, et en particulier en théorie des automates, un automate de Muller est un automate fini reconnaissant des mots infinis, doté d une famille d ensemble d états terminaux distingués. Le mode de reconnaissance est le suivant …   Wikipédia en Français

  • Grammaire formelle — Une grammaire est un formalisme permettant de définir une syntaxe et donc un langage formel, c est à dire un ensemble de mots admissibles sur un alphabet donné. La notion de grammaire formelle est particulièrement utilisée en programmation… …   Wikipédia en Français

  • Langage contextuel — En informatique théorique, et spécialement en théorie des langages, un langage contextuel (en anglais context sensitive langauge) est un langage formel engendré par une grammaire contextuelle. C est un langage de type 1 dans la hiérarchie de… …   Wikipédia en Français

  • Expression rationnelle — Pour les articles homonymes, voir régulier et rationnel. Une expression rationnelle ou expression régulière[1] est en informatique une chaîne de caractères que l’on appelle parfois un motif et qui décrit un ensemble de chaînes de caractères… …   Wikipédia en Français

  • Heuristique —  Ne doit pas être confondu avec Éristique ni Herméneutique. L heuristique (du grec ancien εὑρίσκω, eurisko, « je trouve » [1]), parfois orthographiée euristique, est un terme de didactique qui signifie « l art d inventer, d …   Wikipédia en Français

  • Matroïde — La notion de matroïde (introduite en 1935 par Whitney) a pour vocation initiale de saisir l essence du concept d indépendance linéaire. Elle est donc naturellement liée à l algèbre linéaire (déjà au niveau du vocabulaire : indépendant, base …   Wikipédia en Français

  • Langage rationnel — Les langages rationnels ou langages réguliers ou encore langages reconnaissables peuvent être décrits de plusieurs façons équivalentes: ce sont les langages décrits par les expressions régulières ou rationnelles,d où le nom de langages réguliers; …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”