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.

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

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Linear bounded automata » (voir la liste des auteurs)