Acyclicité : Les réseaux d’automates acycliques

Les réseaux d’automates acycliques sont une famille de réseaux d’automates parmi les plus simples, et consécutivement une des rares familles de réseaux d’automates dont nous comprenons entièrement le comportement. L’acyclicité ici est définie dans le contexte du graphe d’interaction du réseau; un réseau d’automate est dit acyclique si son réseau d’interaction ne dispose d’aucun cycle. Définition 64 (Réseau d’automates acyclique). Soit F un réseau d’automates. Le réseau F est dit acyclique si et seulement si son graphe d’interaction est un graphe acyclique. Exemple 44. Soit F le réseau d’automates acyclique défini sur les automates S = {a,b,c} et qui admet les fonctions locales suivantes : fa(x) = 1 fb(x) = ¬xa fc (x) = xa ∨ xb Le graphe d’interaction du réseau d’automates acyclique F est représenté en figure 6.1, et le graphe de sa dynamique totale en figure 6.2. Cela signifie plus formellement qu’il n’existe aucun chemin partant d’un automate s et retournant sur l’automate s dans le graphe d’interaction du réseau d’automates. Cela signifie qu’il existera toujours au moins un automate qui n’est influencé par aucun autre automate; dans le cas contraire, on pourrait remonter l’influence dans le graphe sans fin, ce qui décrit naturellement un cycle. Ces automates sans aucune influence ont une fonction locale constante, puisqu’elle ne peut pas être influencée par aucun facteur, y compris la valeur de l’automate où elle est installée. Le reste du réseau prenant son influence toujours depuis ce sous-ensemble constant, et ne disposant d’aucun cycle, l’entièreté du réseau est destinée à se figer en un point fixe. Ce théorème est également évoqué en section 4.6. Théorème 6 (ROBERT 1980). Soit F un réseau acyclique. La dynamique totale de F n’a qu’un seul attracteur qui est un point fixe. Démonstration. Soit F un réseau d’automates acyclique. On construit la séquence (S1,S2,…,Sk) telle que S1 est l’ensemble des automates de F qui ne sont influencés par aucun autre automate, S2 est l’ensemble des automates qui ne sont influencés que par des automates de S1, et en général Si décrit les automates qui ne sont influencés que par des sommets dans les ensembles qui le précèdent dans la séquence. En pratique, k décrit la longueur du plus long chemin dans le graphe d’interaction de F. Par définition, l’ensemble des éléments de cette séquence produit une partition de l’ensemble S, et aucun élément de cette séquence n’est vide. On considère le graphe de la dynamique totale de F. Par définition, toute fonction locale d’un automate de S1 est une fonction constante. Par conséquent, mettre à jour n’importe quel automate dans S1 fige cet automate dans une valeur qui ne change plus. Plus formellement, toute configuration x qui vérifie xs 6= fs(x) pour s dans S1 ne fait pas partie d’un attracteur. Par conséquent, l’ensemble des attracteurs de la dynamique doit être inclus dans le sous-graphe dont les configurations vérifient xs = fs(x) pour tout s dans S1. Nous considérons ce sous-graphe. Dans ce sous-graphe et par définition, toute fonction locale d’un automate de S2 est une fonction qui ne dépend que d’automates dans S1. Par définition de nouveau, le sous-graphe de la dynamique ne considère qu’une valeur constante pour chaque automate dans S1. Par conséquent, le même raisonnement s’applique, et les attracteurs du réseau ne peuvent être que dans le sous-graphe de ce sous-graphe qui ne contient que les configurations qui vérifient xs = fs(x) pour s ∈ S2. On applique ce raisonnement pour l’ensemble de la séquence (S1,S2,…,Sk), et obtenons un sous-graphe de la dynamique qui contient nécessairement l’ensemble des attracteurs de F. De plus, l’ensemble de ce raisonnement a selectionné les configurations qui figent l’ensemble des automates du réseau à une valeur constante. Par conséquent, le sous-graphe que nous obtenons ne possède qu’une seule configuration, qui est nécessairement le seul attracteur du graphe, et donc un point fixe. Ce résultat connu illustre parfaitement que la complexité des réseaux d’automates réside dans les cycles de son graphe d’interaction. 

Modules acycliques

 Les modules sont une généralisation qui complexifie le comportement des réseaux étudiés. Nous développons dans cette section la restriction des modules sur des réseaux acycliques. Les réseaux d’automates acycliques étant des objets dont la dynamique est simple à comprendre, leur version modulaire dispose d’un comportement dynamique qui semble accessible à la caractérisation. Définition 65 (Module acyclique). Soit M un module. Le réseau M est acyclique si et seulement si son graphe d’interaction est un graphe acyclique. Exemple 45. Soit M le module acyclique défini sur les automates S = {a,b,c}, les entrées I = {α,β,γ} et qui admet les fonctions locales suivantes : fa(x ·i) = iα fb(x ·i) = xa ∨iβ ∨ ¬iα fc (x ·i) = ¬xb ∧ xa ∧ ¬iγ. Le graphe d’interaction de M est représenté en figure 6.3. Les modules acycliques diffèrent des réseaux d’automates acycliques car, en général, leurs entrées les empêchent de converger. Lorsque la valeur d’une entrée change dans une exécution, cette entrée provoque une cascade potentielle de réévaluations de fonctions locales le long du module. L’absence de cycle empêche le stockage de toute information; et dès que les entrées sont figées sur une certaine configuration d’entrée, le réseau entier reprend le fonctionnement d’un réseau d’automates acyclique, et atteint un point fixe. L’étude des modules acycliques nous semble justifiée par la simple réalisation que tout réseau d’automates, et même tout module, peut être exprimé comme le branchement récursif d’un module acyclique. Ce dernier se construit facilement en trouvant un coupe-cycle de sommets (ou Feedback Vertex Set) du graphe d’interaction du réseau, c’est-à-dire un ensemble d’automates qui, lorsque l’on remplace leur influence par des entrées, confèrent un réseau d’interaction acyclique. Afin de conserver au mieux la structure du réseau initial, il est préférable de trouver un Minimal Feedback Vertex Set du graphe d’interaction, ce qui est un problème NP-complet (KARP 1972). Propriété 14. Soit M un module. Il existe un module acyclique M0 et un branchement récursif w tel que w M0 = M. Démonstration. Soit M un module. Nous considérons une solution du problème Minimal Feedback Vertex Set du graphe d’interaction de M que nous dénotons comme l’ensemble d’arêtes orientées A ⊆ S × S. Par définition, retirer ces arêtes au graphe d’interaction de M nous donne un graphe acyclique. On considère l’ensemble des automates S 0 ⊆ S, défini tel que s 0 ∈ S 0 si et seulement s’il existe s 0 tel que (s 0 ,s) ∈ A. On définit un ensemble de variables I 0 = {α 0 s | s 0 ∈ S 0 } tel que I ∩ I 0 = ;. Soit M0 le module basé sur l’ensemble d’automates S et l’ensemble d’entrées I ∪ I 0 , et qui, pour tout s ∈ S, définit la fonction locale f 0 s comme la copie de la fonction fs dans laquelle chaque variable x 0 s est remplacée par iαs 0 , pour tout s 0 dans S 0 . Soit w la fonction de branchement avec domaine I 0 qui définit w(αs 0) = s 0 . Ces constructions impliquent w M0 = M. Par définition, le graphe d’interaction de M0 est acyclique. Il semble clair qu’une caractérisation du comportement des modules acycliques permet une compréhension plus approfondie du fonctionnement des modules en général, et en particulier des réseaux d’automates. 

Fonctions de sortie

 Le comportement d’un automate d’un module acyclique peut être caractérisé comme une fonction de l’historique récent des entrées données au réseau. Ainsi, lorsqu’un module acyclique est mis à jour pour assez longtemps à partir d’une configuration initiale et avec une séquence de configurations d’entrée, l’influence de la configuration initiale sur l’évaluation des automates devient nulle. Cela se comprend clairement lorsque l’on se rappelle qu’un module acyclique ne dispose d’aucun mécanisme pour retenir de l’information. Nous caractérisons cette propriété par l’association d’une fonction de sortie à tout automate. Ici, nous faisons une différence entre séquence d’entrée (composée par des configurations d’entrées mises dans un certain ordre) et historique d’entrée (composé de configurations d’entrées organisées par ancienneté). Si l’ensemble des séquences d’entrées d’un module est (Λ I ) ∗ , les historiques d’entrées de longueur n se définissent dans l’ensemble Λ I×{1, …,n} . Définition 66. Pour tout séquence d’entrée J et tout entier n tel que |J| ≥ n, on définit l’historique de taille n extrait de J comme l’historique noté Hn(J), qui pour tout α ∈ I et k ∈ {1,…,n} définit Hn(J)(α,k) = (J|J|−k+1)α. Une fonction de sortie est définie sur O : Λ I×{1, …,D} → Λ, pour D un entier suffisament grand. L’historique définit dans Λ I×{1, …,D} passé en entrée d’une fonction de sortie contient les configurations d’entrée récentes. Ainsi, pour α une variable de I, l’index (α,1), que nous notons α1, de ce vecteur, correspond à la valeur de l’entrée α à la mise à jour actuelle. L’index α2 représente la valeur de l’entrée α une mise à jour dans le passé, et en général αk représente la valeur de l’entrée α k − 1 mises à jour dans le passé. Une fonction de sortie est une fonction qui, pour tout historique de longueur D, retourne une valeur dans Λ. Pour O une fonction de sortie donnée, la valeur k maximale telle qu’il existe α ∈ I qui vérifie que αk a une influence sur l’évaluation de O s’appelle le délai de O. Nous notons ce délai par la lettre d, et il correspond à la profondeur minimale de l’historique nécessaire pour calculer O. Ainsi l’évaluation de O sur une séquence d’entrée consiste à en extraire un historique de longueur d, et d’évaluer O sur cet historique. On note que si d < D, alors un historique de taille d ne contient pas assez d’information pour permettre un appel correct de la fonction O. Cependant, puisque par définition aucune variable qui manque à cet historique n’a d’influence sur le calcul de O, ne prenons le raccourcis de noter O(Hd(J)) comme une évaluation correcte de O. Définition 67 (Évaluation d’une fonction de sortie). Soit O : Λ I×{1, …,D} → Λ une fonction de sortie avec délai d, et J une séquence d’entrée de taille k ≥ d. On définit l’évaluation de O sur J, notée O(J), comme O(J) = O(Hd(J)). Nous définissons maintenant l’incrémentation d’une fonction de sortie, qui consiste à déplacer la fenêtre des variables considérées par la fonction dans le temps, ce qui a l’effet immédiat d’augmenter son délai de 1. Cette notion simple est centrale dans les preuves qui reposent sur le calcul de ces fonctions de sortie dans le contexte de la prédiction de la valeur d’automates dans un module acyclique. Définition 68 (Incrémentation de fonction de sortie). Pour O une fonction de sortie de délai d, nous définissons l’incrémentation de la fonction O, notée O +1 , comme la fonction de délai d+1 définie telle que, pour toute séquence d’entrée J de taille k telle que k ≥ d+1, O +1 (J) = O(J[1,…,k−1]). Notre caractérisation du comportement sous mode de mise à jour parallèle des modules acycliques consiste à énoncer que, partant d’une configuration x, et pour une séquence d’entrée suffisament longue J, le comportement de tout automate peut être prédit par une fonction de sortie, dont l’évaluation ne dépend que de J et non de x. Propriété 15. Soit M un module acyclique. Pour s un automate, et J une séquence de configurations d’entrée suffisament longue de taille k, il existe au moins une fonction de sortie Os de délai d ≤ k telle que M(x,J)s = Os(J). Démonstration. Dans cette preuve nous supposons disposer des fonctions locales du module M sous la forme de formules. Soit prof(s) la fonction qui donne la profondeur d’un automate dans le graphe d’interaction définie telle que prof(s) = 1 si et seulement si s n’est influencé par aucun automate, et prof(s) = maxs 0∈prec(s)prof(s 0 )+1 pour prec(s) l’ensemble des automates qui influencent s dans le cas contraire. Soit s tel que prof(s) = 1. Nous construisons Os comme la copie de la fonction locale fs dans laquelle chaque variable α est substituée par la variable α1, pour tout α dans 11. Nous pouvons vérifier que pour toute séquence J de taille k au moins supérieure à 0, et toute configuration x, que M(x,J)s = Os(J). Supposons que, pour un certain entier i, nous disposons d’une fonction de sortie Os pour chaque entier s qui vérifie prof(s) = i telle que, pour toute séquence J de taille au moins i, M(x,J)s = Os(J). Dans la suite de cette preuve, nous montrons que cette hypothèse implique la même proposition pour l’entier i +1, ce qui implique le résultat par induction. Soit s un entier tel que prof(s) = i +1. Nous construisons la fonction de sortie Os comme la copie de la fonction locale fs dans laquelle chaque variable xs 0 est substituée par la fonction O +1 s 0 , et chaque variable α par α1. Soit J une séquence d’entrée de taille k au moins i +1. Nous observons que M(x,J)s = M(M(x,J[1,…,k−1]),J[k] )s M(x,J)s = fs(M(x,J[1,…,k−1])· Jk). Cependant, par définition la fonction fs n’est influencée que par des automates dont les fonctions de sorties sont déjà définies. Soit R l’ensemble des automates dont la profondeur est inférieure à s, et T l’ensemble des automates dont la profondeur est supérieure ou égale à s. Soit OR(J) la configuration définie sur R qui pour tout r ∈ R définit la valeur Or (J). Pour toute configuration xT sur T , nous observons que M(x,J)s = fs(OR(J[1,…,k−1])· xT · Jk) M(x,J)s = Os(J), ce qui implique le résultat. L’ensemble des fonctions de sortie qui prédisent la valeur de s sont toutes très similaires. En effet, il ne s’agit que des variantes de la même fonction qui décalent leur analyse de l’historique dans le temps d’une valeur arbitraire, entraînant des délais plus grands. Plus formellement, chacune de ces différentes fonctions sont obtenues comme les incrémentations successives d’une fonction de sortie à délai minimal. Nous proposons donc la définition naturelle de fonction de sortie canonique associée à un automate comme la fonction de sortie qui prédit la valeur de l’automate, tout en ayant le délai minimal. Définition 69 (Fonction de sortie canonique). Soit M un module acyclique et s un automate de M. La fonction de sortie canonique de s, notée Os , est la fonction de sortie qui vérifie la propriété 15, avec délai minimal. Exemple 46. Soit S = {a,b,c} un ensemble d’automates. Soit M le module qui définit les fonctions locales suivantes : fa(x ·i) = iα fb(x ·i) = xa ∨iβ fc (x ·i) = xb ∧ ¬xa Ce module vérifie les fonctions de sortie canoniques suivantes : Oa = α1 Ob = α2 ∨ ¬β1 Oc = (α3 ∨ ¬β2)∧ ¬α2 Considérons la séquence d’entrée J = (i,i 0 ,i 00), avec iα = iβ = i 00 α = 0, et i 0 α = i 0 β = i 00 β = 1. Pour prédire la valeur de a, b ou c après que la séquence d’entrée J soit appliquée au module M, on calcule Oa(J), Ob(J), et Oc (J). Pour cela, on doit transformer J, qui est une séquence d’entrée, en un historique des valeurs de α et β défini sur Λ {α,β}×{1,2,3}. Ici, la longueur de notre séquence est k = 3, et nos fonctions de sorties ont chacune un délai que nous notons da = 1, db = 2 et dc = 3. En appliquant la définition 67, on obtient que Oa(J) = Oa(H1(J)), Ob(J) = Ob(H2(J)) et Oc (J) = Oc (H3(J)). Les historiques H1(J), H2(J) et H3(J) sont tous issus de J, et tous de longueur différentes. On peut les évaluer de cette façon : ∀k ∈ {1, 2, 3},Hk(J)(α,1) = (J|J|−1+1)α = i 00 α ∀k ∈ {1, 2, 3},Hk(J)(β,1) = (J|J|−1+1)β = i 00 β ∀k ∈ {2, 3},Hk(J)(α,2) = (J|J|−2+1)α = i 0 α ∀k ∈ {2, 3},Hk(J)(β,2) = (J|J|−2+1)β = i 0 β H3(J)(α,3) = (J|J|−3+1)α = iα H3(J)(β,3) = (J|J|−3+1)β = iβ. Pour obtenir la valeur de Oa(H1(J)), sachant que Oa = α1, il suffit de prendre la valeur de α dans la première configuration de l’historique, ce qui est H1(J)(α,1) = i 00 α = 0. On a donc Oa(J) = Oa(H1(J)) = H1(J)(α,1) = i 00 α = 0. Similairement, pour calculer Ob(H2(J)), sachant que Ob = α2 ∨ ¬β1, on note que α2 est la valeur de α donnée par la seconde configuration de l’historique, et que β1 est la valeur de β donnée dans la première configuration de l’historique. Ces valeurs sont H2(J)(α,2) = i 0 α = 1 et H2(J)(β,1) = i 00 β = 1, ce qui signifie que Ob(J) = Ob(H2(J)) = H2(J)(α,2) ∨ ¬H2(J)(β,1) = i 0 α ∨ ¬i 00 β = 1∨ ¬1 = 1. Enfin, pour calculer Oc (H3(J)), en sachant que Oc = (α3 ∨ ¬β2) ∧ ¬α2, on calcule α3 = H3(J)(α,3) = iα = 0, β2 = H3(J)(β,2) = i 0 β = 1 et α2 = H3(J)(α,2) = i 0 α = 1. On a donc Oc (J) = Oc (H3(J)) = (H3(J)(α,3) ∨¬H3(J)(β,2))∧H3(J)(α,2) = (iα ∨¬i 0 β )∧¬i 0 α = (0∨¬1)∧ ¬1 = 0. L’évaluation des fonctions de sortie Ob et Oc sur J est illustrée en figure 6.4. Exemple 47. Soit M le module développé dans l’exemple 45, dont les fonctions locale sont fa(x ·i) = iα fb(x ·i) = xa ∨iβ ∨ ¬iα fc (x ·i) = ¬xb ∧ xa ∧ ¬iγ. Le module M vérifie les fonctions de sortie canoniques suivantes : Oa = α1 Ob = α2 ∨β1 ∨ ¬α1 Oc = ¬α3 ∧ ¬β2 ∧α2 ∧α2 ∧ ¬γ1. Les fonctions Oa, Ob et Oc ont délai 1, 2 et 3 respectivement.