Soutenance mémoire
Les automates cellulaires et le temps-réel
Automates cellulaires en dimension 1
Définition
Un automate cellulaire (AC) de dimension 1 consiste en une ligne d’automates finis tous identiques appelés cellules. Chacune de ces cellules tire sa valeur d’un ensemble d’états fini S et interagit avec les cellules voisines à des pas de temps discrets. Au temps initial t = 1, chaque cellule reçoit un état de S. Le calcul est ensuite réalisé localement : le nouvel état d’une cellule est le résultat d’une fonction de transition qui dépend des états de son voisinage au pas de temps précédent. Cette fonction de transition s’applique de façon synchrone à toutes les cellules et à chaque pas de temps. Formellement :
Définition 1.1.1 Un automate cellulaire (AC) est un triplet (S,N ,f) où :
— S est un ensemble fini d’états;
— N = {n1,…,n|N |} ⊂ Z est le voisinage ;
— f : S|N | → S est la fonction de transition.
En notant (c,t) l’état de la cellule c au temps t, l’évolution de l’état d’une cellule suit le schéma suivant : (c,t +1) = f((c+n1,t),…,(c+n|N | ,t)) .
Les automates cellulaires comme reconnaisseurs de langage
Dans cette thèse, on s’intéresse aux automates cellulaires comme reconnaisseurs de langage. De tels automates opèrent sur un mot d’entrée w ∈ Σ+ (avec Σ un alphabet) et donnent en sortie l’une des deux réponses “acceptation” ou “rejet”. Il convient alors de préciser comment le mot d’entrée est transmis à l’automate et comment le résultat du calcul est obtenu. Tout d’abord, on donne certaines conditions sur l’ensemble des états de l’automate S.
— Les lettres du mot d’entrée appartiennent à l’ensemble des états : Σ ⊂ S.
— Un sous-ensemble d’états acceptants Sacc ⊂ S est identifié.
— Deux états spéciaux sont aussi distingués : un état permanent ∦ et un état quiescent λ. Une cellule dans l’état permanent ∦ reste dans cet état indéfiniment. Une cellule dans l’état quiescent λ reste dans cet état tant que son voisinage est lui aussi quiescent.
Le temps-réel des automates cellulaires
Le calcul d’un automate s’effectue en temps-réel (ou temps minimal) sur une entrée w si ce calcul s’arrête dès que la cellule de sortie a reçu la totalité de l’information de w. On dit alors qu’un langage est reconnu en temps-réel si chacun des mots de ce langage est accepté en temps-réel. En ce qui concerne les AC de dimension 1, il existe 4 classes de langages temps-réel, selon si :
— le mode d’entrée est parallèle ou séquentiel;
— la communication est bidirectionnelle (avec le voisinage canonique {−1,0,1}) ou unidirectionnelle (avec le voisinage {−1,0}).
Formules de Horn sur des structures de mot
En vis-à-vis des automates cellulaires opérant en temps-réel, on introduit deux types de logiques. Le premier est celui des formules de Horn. Le second est une extension des formules de Horn avec une contrainte d’acyclicité : il s’agit des formules inductives. On présente d’abord ces notions dans le cadre du calcul propositionnel, ceci pour des raisons de simplicité pédagogique et aussi pour les preuves.
Sémantique propositionnelle
Une formule de Horn propositionnelle consiste en une conjonction de clauses appelées clauses de Horn portant sur des propositions, appelées aussi variables propositionnelles ou simplement variables. Ces clauses peuvent être
— soit des clauses de Horn strictes de la forme p1 ∧ p2 ∧···∧ ph → pc où les propositions (pi)i∈[1,h] avec h ≥ 0 jouent le rôle d’hypothèses et la proposition pc celui de conclusion, cette clause se lisant ainsi : “SI p1 est vraie ET p2 est vraie … ET ph est vraie ALORS pc est vraie”;
— soit des clauses (de Horn) négatives de la forme p1 ∧ p2 ∧… ph → ⊥ où ⊥ est la valeur faux et h ≥ 1.
Pour une formule propositionnelle F, on appelle interprétation une fonction I associant à chaque variable de F une valeur de vérité (1 pour le vrai et 0 pour le faux). I est un modèle de F, ce qu’on note I |= F, si F est évaluée à vrai quand chaque variable p est remplacée par son interprétation I(p). Une clause de Horn stricte sans hypothèse, notée → p ou simplement p, qu’on appelle un fait, exprime que p est vraie.
Modèle minimal
À toute conjonction de clauses de Horn strictes appelée formule de Horn stricte est associé un modèle minimal unique. Le modèle minimal d’une formule de Horn stricte F est défini comme le modèle I0 de l’équivalence : I0(p) = 1 ⇐⇒ l’implication F → p est une tautologie. Ainsi, pour toute proposition p de F on a l’implication I0(p) = 1 ⇒ (∀I : I |= F ⇒ I(p) = 1). Le modèle minimal de F est obtenu à partir des faits de F par la clôture de l’opération d’implication. On associe à une interprétation I l’ensemble des variables p telles que I(p) = 1, ensemble qu’on appelle aussi I par abus de notation : le modèle minimal de F est alors l’intersection de tous les modèles de F.
|
Table des matières
Introduction
1 Préliminaires
1.1 Les automates cellulaires et le temps-réel
1.1.1 Automates cellulaires en dimension 1
1.1.2 Le temps-réel des automates cellulaires
1.2 Formules de Horn sur des structures de mot
1.2.1 Sémantique propositionnelle
1.2.2 Sémantique en logique du premier ordre
1.2.3 Un exemple de formule de Horn pour le langage des palindromes
2 Concepts de base : circuit-grille et normalisation logique
2.1 Le circuit-grille
2.1.1 Principe et définition d’un circuit-grille
2.1.2 Trois modes d’entrée pour trois classes de complexité : GRID1, GRID2 et GRID3
2.2 Trois logiques pour trois modes d’entrée
2.2.1 Les classes pred-ESO-HORN, pred-dio-ESO-HORN et incl-ESO-HORN
2.2.2 Logiques inductives
2.3 Programmation par la logique et normalisation : un premier exemple
3 Équivalences entre logiques et automates
3.1 Égalité des classes pred-ESO-HORN, pred-ESO-IND et RealTimeCA
3.1.1 Inclusion de pred-ESO-IND dans normal-pred-ESO-IND
3.1.2 Inclusion de pred-ESO-HORN dans normal-pred-ESO-HORN
3.1.3 Inclusion de normal-pred-ESO-IND dans grid-pred-ESO-HORN
3.1.4 Égalité des classes grid-pred-ESO-HORN, GRID1 et RealTimeCA
3.2 Égalité des classes pred-dio-ESO-HORN, pred-dio-ESO-IND et RealTimeIA
3.2.1 Égalité de pred-dio-ESO-IND et normal-pred-dio-ESO-IND
3.2.2 Inclusion de pred-dio-ESO-HORN dans normal-pred-dio-ESO-HORN
3.2.3 Inclusion de normal-pred-dio-ESO-IND dans grid-pred-dio-ESO-HORN
3.2.4 Égalité de grid-pred-dio-ESO-HORN, GRID2 et RealTimeIA
3.3 Égalité entre les classes incl-ESO-HORN, incl-ESO-IND et Trellis
3.3.1 Inclusion de incl-ESO-IND dans normal-incl-ESO-IND
3.3.2 Inclusion de incl-ESO-HORN dans normal-incl-ESO-HORN
3.3.3 Inclusion de normal-incl-ESO-IND dans grid-incl-ESO-HORN
3.3.4 Égalité de grid-incl-ESO-HORN, GRID3 et Trellis
4 Un problème de référence : la synchronisation
4.1 Lien entre la synchronisation et le langage Culik
4.2 L’algorithme de synchronisation
4.3 Construction de l’arbre de potentiel sur la grille
4.3.1 Construction des branches gauche et droite d’un nœud pair
4.3.2 Construction de la branche gauche du fils droit et de la branche droite du fils gauche d’un nœud impair
4.3.3 Initialisation de la récurrence : construction des branches extérieures de l’arbre
4.3.4 Fin de la récurrence : caractérisation des feuilles de l’arbre
4.4 Une formule d’inclusion inductive définissant le langage Culik
4.4.1 Clauses définissant l’initialisation et la fin de la récurrence
4.4.2 Définition des nœuds de l’arbre de potentiel
4.4.3 Appartenance de Culik à incl-ESO-IND
5 Le circuit-grille et les logiques en dimension 3 ou plus
5.1 Les modes d’entrée équivalents aux dimensions inférieurs
5.2 Les classes de grille s’étendant à toutes les dimensions
5.2.1 Équivalence avec les automates cellulaires
5.2.2 Généralisation des logiques
5.3 Autres variantes
5.3.1 Deux circuits-cube intermédiaires
5.3.2 Un autre circuit-cube intéressant?
6 Les langages conjonctifs
6.1 Définitions
6.1.1 Langages conjonctifs
6.1.2 Formes normales binaires
6.2 Reconnaissance des langages conjonctifs
6.2.1 L’algorithme de Cocke-Kasami-Younger
6.2.2 Définir en logique les langages conjonctifs
6.2.3 Parallélisation de l’algorithme CKY
6.3 Les langages conjonctifs sur alphabet unaire
6.3.1 Pouvoir d’expression
6.3.2 Appartenance à pred-dio-ESO-HORN
6.3.3 Reconnaissance
6.4 Les langages linéaires conjonctifs
6.4.1 Définition et forme normale
6.4.2 Égalité des classes LinConj, Trellis et incl-ESO-HORN
6.4.3 Une grammaire pour les mots bien parenthésés
Conclusion
Bibliographie
