Automate linéairement borné

une machine de Turing non déterministe qui n'utilise qu'une portion contiguë du ruban de taille linéaire en la taille de l'entrée

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 qui n'utilise qu'une portion contiguë du ruban de taille linéaire en la taille de l'entrée.

Description

modifier

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 à droite ;
  2. ses transitions ne peuvent écrire sur la bande au-delà des marqueurs de fin ;
  3. ses transitions ne peuvent pas déplacer les marqueurs de gauche et de droite au-delà de leur position respectivement à gauche et à 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 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 et d'écriture. Ce segment est délimité par les cases contenant les marqueurs de fin.

Automates linéairement bornés et langages contextuels

modifier

Les automates linéairement bornés reconnaissent exactement la classe des langages contextuels. 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

modifier

En 1960, John Myhill introduit un modèle d'automate appelé maintenant automate linéairement borné déterministe[1]. Peu de temps après, Lawrence Landweber prouve que les langages reconnus par les automates linéairement bornés déterministes sont contextuels[2]. En 1964, Sige-Yuki Kuroda 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

modifier

Dans son article fondateur, Kuroda pose deux problèmes de recherche qui sont devenus célèbres sous 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é déterministe ? En termes de complexité algorithmique, ce problème s'énonce
A-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
A-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 d'Immerman-Szelepcsényi reliant les classes NSPACE et co-NSPACE. Ce résultat, prouvé indépendamment par Neil Immerman[4] et Róbert Szelepcsényi[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 et références

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

Bibliographie

modifier

Liens externes

modifier

Source de la traduction

modifier