Logique monadique du 2nd ordre pour les mots infinis · Logique monadique du 2nd ordre pour les...

Logique monadique du 2nd ordre pour les motsinfinis

Yohan Boichut

Cours Master IRAD – Semestre 1

Yohan Boichut Logique monadique du 2nd ordre pour les mots infinis Cours Master IRAD – Semestre 1 1 / 34

Outline

1 Mots infinis

2 Logique monadique du 2nd ordre

3 Epilogue

Expressions regulieres

Pour un alphabet Σ,

I Si a ∈ Σ alors a est une expression reguliereI Si e1 et e2 sont deux expressions regulieres

I e1.e2 est une expression reguliereI e1 + e2 est une expression reguliere

I Si e est une expression reguliere alors e∗ est une expressionreguliere

Expressions regulieres

Exemple

Soit Σ = {a, b, c} alors l’expression reguliere

(ab∗ + c)∗

denote la concatenation de sequences de lettres de la forme

I c ou

I a suivi d’un nombre nul ou fini de b

Expressions ω−regulieres

DefinitionLes expressions ω−regulieres sont definies inductivement a partirdes regles suivantes :

I Si e1, e2 sont des expressions regulieres (denotant E1, E2)alors e1.e

ω2 est une expression ω−reguliere (eω2 est une chaıne

infinie composee de mots de E2)

I Si e1, e2 sont des expressions ω−regulieres alors e1 + eω2 estune expression ω−reguliere

I Σ est un ensemble d’actions

TheoremeUne expression est ω−reguliere ssi elle est de la forme

⋃ni=1(ei.f

ou ei et fi sont des expressions regulieres

DefinitionLes expressions ω−regulieres sont definies inductivement a partirdes regles suivantes :

I Si e1, e2 sont des expressions regulieres (denotant E1, E2)alors e1.e

ω2 est une expression ω−reguliere (eω2 est une chaıne

infinie composee de mots de E2)

I Si e1, e2 sont des expressions ω−regulieres alors e1 + eω2 estune expression ω−reguliere

I Σ est un ensemble d’actions

⋃ni=1(ei.f

Exemple

Soit Σ = {a, b, c} alors l’expression ω−reguliere

(c∗ac∗b)∗cω ∪ (c∗ac∗b)ω

denote l’ensemble des mots infinis pour lesquels

I toute occurence de a doit etre suivie de c∗b et

I toute occurence de b doit etre precedee de ac∗

Automate de Buchi

Structure reconnaissant des ω−mots

DefinitionUn automate de Buchi est un quintuplet 〈Σ,Q, qi,Qf ,∆〉 tel que :

I Q est l’ensemble des etats des automates

I qi ∈ Q est l’etat initial

I Qf ⊆ Q est l’ensemble des etats finaux

I ∆ ⊆ Q× Σ×Q est une relation de transition

Critere d’acceptation de BuchiUn ω−mot sur Σ est reconnaissable par B si la chaıne des etatsvisites par l’automate passe infiniment souvent par des etats de F

Automate de Buchi

Structure reconnaissant des ω−mots

DefinitionUn automate de Buchi est un quintuplet 〈Σ,Q, qi,Qf ,∆〉 tel que :

I Q est l’ensemble des etats des automates

I qi ∈ Q est l’etat initial

I Qf ⊆ Q est l’ensemble des etats finaux

I ∆ ⊆ Q× Σ×Q est une relation de transition

Critere d’acceptation de BuchiUn ω−mot sur Σ est reconnaissable par B si la chaıne des etatsvisites par l’automate passe infiniment souvent par des etats de F

Automate de Buchi

L’ensemble des ω−mots reconnaissable par l’automate est

(a∗bb∗a)ω + (a∗bb ∗ a)∗a∗b(b)ω

Proprietes d’un automate de Buchi

Proposition

La classe des langages de Buchi est close par union et parintersection.

Proposition

Si V ⊆ Σ∗ est regulier, alors V ω est Buchi-reconnaissable.

Proposition

Si U ⊆ Σ∗ est regulier et L ⊆ Σω Buchi-reconnaissable, alors U.Lest Buchi-reconnaissable.

Proposition

Et donc. . .

⋃ni=1(ei.f

TheoremeLangages ω-reguliers = langages de Buchi.

Et donc. . .

⋃ni=1(ei.f

TheoremeLangages ω-reguliers = langages de Buchi.

En d’autres mots

TheoremeUn ω−langage est reconnaissable par un automate de Buchi ssi ilest ω−regulier

Autre exemple d’automate de Buchi

Quel est le langage de cet automate de Buchi ?

Automate de Buchi

Le vide est decidable pour les automates de Buchi

Algorithme de Tarjan-Paige

I Enumeration des composantes fortement connexesatteignables a partir de qi

I Langage est vide si toutes les CFC ne passent pas par un etatfinal

Automate de Buchi

Le vide est decidable pour les automates de Buchi

Algorithme de Tarjan-Paige

I Enumeration des composantes fortement connexesatteignables a partir de qi

I Langage est vide si toutes les CFC ne passent pas par un etatfinal

Complementaire

Proposition

Si L est Buchi-reconnaissable, alors Σω \ L est egalement Buchireconnaissable.

Le seul soucis est que sa construction n’est pas aussi simple quepour les langages reguliers.

Complementaire

Proposition

Si L est Buchi-reconnaissable, alors Σω \ L est egalement Buchireconnaissable.

Le seul soucis est que sa construction n’est pas aussi simple quepour les langages reguliers.

Automate de Buchi et determinisme

L’automate reconnaissant le langage (a+ b)∗aω ne peut etre quenon-deterministe

LemmeL = L(A) pour un Buchi deterministe ssi il existe W ⊆ Σ∗ reguliertel que L = limW .

Automate de Buchi et determinisme

L’automate reconnaissant le langage (a+ b)∗aω ne peut etre quenon-deterministe

LemmeL = L(A) pour un Buchi deterministe ssi il existe W ⊆ Σ∗ reguliertel que L = limW .

Cependant. . .

Il existe d’autres automates pour les mots infinis :

I Automates de Muller : determinisables

I Automates de Rabin

Theoreme (Mc Naughton)

Langages de Buchi = Langages de Muller.

Langages de Muller sont equivalents aux langages de Rabin

Construction de Safra [88]:Buchi a n etats 7→ Rabin deterministe a O

(2n. log n

)etats

Cependant. . .

(2n. log n

)etats

Cependant. . .

(2n. log n

)etats

Cependant. . .

(2n. log n

)etats

Outline

1 Mots infinis

3 Epilogue

Logique monadique du second ordre a un successeur (S1S)

I pour exprimer des proprietes sur les suites (mots infinis).

I equivalent en expressivite aux automates de Buchi [Buchi1962].

I compilation en automate: algorithmes de decision.

Structure associee a un mot

I Soient Σ un alphabet fini, w ∈ Σω,

I Structure w :=⟨N, 0,+1, <, (Pa)a∈Σ

I 0 et +1 fonctions 0 et successeur,

I < ordre sur les entiers naturels

I predicat Pa(i) = true ssi wi = a.

S1SΣ: syntaxe

I variables du premier ordre x. . .

I variables du second ordre X. . . (ensembles)

I terme ::= x∣∣ 0

∣∣ terme + 1I

formule ::= terme = terme∣∣ terme < terme

∣∣ Pa(terme)∣∣ formule ∧ formule∣∣ formule ∨ formule

∣∣ ¬formule∣∣ ∃x formule∣∣ ∃X formule

∣∣ ∀x formule∣∣ ∀X formule∣∣ terme ∈ X

Notation φ(X1, . . . , Xn), X1, . . . , Xn sont les variables libres de φ.

S1SΣ: semantique

I interpretation σ des variables du premier ordre dans N,

I interpretation δ des variables du second ordre dans 2N,

I w, σ, δ |= t = t′ ssi σ(t) =N σ(t′),I w, σ, δ |= t < t′ ssi σ(t) <N σ(t′),I w, σ, δ |= Pa(t) ssi wσ(t) = a,

I w, σ, δ |= t ∈ X ssi σ(t) ∈ δ(X),I w, σ, δ |= φ1 ∧ φ2 ssi w, σ, δ |= φ1 et w, σ, δ |= φ2,

I w, σ, δ |= φ1 ∨ φ2 ssi w, σ, δ |= φ1 ou w, σ, δ |= φ2,

I w, σ, δ |= ¬φ ssi w, σ, δ 6|= φ,

S1SΣ: semantique

I w, σ, δ |= t ∈ X ssi σ(t) ∈ δ(X),

I w, σ, δ |= φ1 ∧ φ2 ssi w, σ, δ |= φ1 et w, σ, δ |= φ2,

I w, σ, δ |= ¬φ ssi w, σ, δ 6|= φ,

S1SΣ: semantique

I w, σ, δ |= t ∈ X ssi σ(t) ∈ δ(X),I w, σ, δ |= φ1 ∧ φ2 ssi w, σ, δ |= φ1 et w, σ, δ |= φ2,

I w, σ, δ |= ¬φ ssi w, σ, δ 6|= φ,

S1SΣ: semantique

I w, σ, δ |= ∃x φ ssi x /∈ dom(σ), x est libre dans φet il existe n ∈ N t.q. w, σ ∪ {x 7→ n}, δ |= φ,

I w, σ, δ |= ∀x φ ssi x /∈ dom(σ), x est libre dans φet pour tout n ∈ N t.q. w, σ ∪ {x 7→ n}, δ |= φ,

I w, σ, δ |= ∃X φ ssi X /∈ dom(δ), X est libre dans φet il existe P ⊆ N infini t.q. w, σ, δ ∪ {X 7→ P} |= φ,

I w, σ, δ |= ∀X φ ssi X /∈ dom(δ), X est libre dans φet pour tout P ⊆ N infini t.q. w, σ, δ ∪ {X 7→ P} |= φ.

S1SΣ: exemples

I inclusion:

X ⊆ Y ≡ ∀x(x ∈ X ⇒ x ∈ Y )

I union finie:

X =n⋃

Xi ≡( n∧i=1

Xi ⊆ X)∧ ∀x

(x ∈ X ⇒

n∨i=1

x ∈ Xi

)I intersection:

Z = X ∩ Y ≡ ∀x (x ∈ Z ⇔ (x ∈ X ∧ x ∈ Y ))

I vide:X = ∅ ≡ ∀x x /∈ X

S1SΣ: exemples

I inclusion:X ⊆ Y ≡ ∀x(x ∈ X ⇒ x ∈ Y )

I union finie:

X =n⋃

Xi ≡( n∧i=1

Xi ⊆ X)∧ ∀x

(x ∈ X ⇒

n∨i=1

x ∈ Xi

)I intersection:

Z = X ∩ Y ≡ ∀x (x ∈ Z ⇔ (x ∈ X ∧ x ∈ Y ))

I vide:X = ∅ ≡ ∀x x /∈ X

S1SΣ: exemples

I union finie:

X =n⋃

Xi ≡( n∧i=1

Xi ⊆ X)∧ ∀x

(x ∈ X ⇒

n∨i=1

x ∈ Xi

)I intersection:

Z = X ∩ Y ≡ ∀x (x ∈ Z ⇔ (x ∈ X ∧ x ∈ Y ))

I vide:X = ∅ ≡ ∀x x /∈ X

S1SΣ: exemples

I union finie:

X =n⋃

Xi ≡( n∧i=1

Xi ⊆ X)∧ ∀x

(x ∈ X ⇒

n∨i=1

x ∈ Xi

I intersection:

Z = X ∩ Y ≡ ∀x (x ∈ Z ⇔ (x ∈ X ∧ x ∈ Y ))

I vide:X = ∅ ≡ ∀x x /∈ X

S1SΣ: exemples

I union finie:

X =n⋃

Xi ≡( n∧i=1

Xi ⊆ X)∧ ∀x

(x ∈ X ⇒

n∨i=1

x ∈ Xi

)I intersection:

Z = X ∩ Y ≡ ∀x (x ∈ Z ⇔ (x ∈ X ∧ x ∈ Y ))

I vide:X = ∅ ≡ ∀x x /∈ X

S1SΣ: exemples

I union finie:

X =n⋃

Xi ≡( n∧i=1

Xi ⊆ X)∧ ∀x

(x ∈ X ⇒

n∨i=1

x ∈ Xi

)I intersection:

Z = X ∩ Y ≡ ∀x (x ∈ Z ⇔ (x ∈ X ∧ x ∈ Y ))

I vide:X = ∅ ≡ ∀x x /∈ X

S1SΣ: exemples

I union finie:

X =n⋃

Xi ≡( n∧i=1

Xi ⊆ X)∧ ∀x

(x ∈ X ⇒

n∨i=1

x ∈ Xi

)I intersection:

Z = X ∩ Y ≡ ∀x (x ∈ Z ⇔ (x ∈ X ∧ x ∈ Y ))

I vide:

X = ∅ ≡ ∀x x /∈ X

S1SΣ: exemples

I union finie:

X =n⋃

Xi ≡( n∧i=1

Xi ⊆ X)∧ ∀x

(x ∈ X ⇒

n∨i=1

x ∈ Xi

)I intersection:

Z = X ∩ Y ≡ ∀x (x ∈ Z ⇔ (x ∈ X ∧ x ∈ Y ))

I vide:X = ∅ ≡ ∀x x /∈ X

S1SΣ: exemples

I union finie:

X =n⋃

Xi ≡( n∧i=1

Xi ⊆ X)∧ ∀x

(x ∈ X ⇒

n∨i=1

x ∈ Xi

)I intersection:

Z = X ∩ Y ≡ ∀x (x ∈ Z ⇔ (x ∈ X ∧ x ∈ Y ))

I vide:X = ∅ ≡ ∀x x /∈ X

S1SΣ: exemples (suite)

I partition:

X1, . . . , Xn partitionX ≡ X =n⋃

Xi ∧n−1∧i=1

n∧j=i+1

Xi ∩Xj = ∅

I singleton:

singleton(X) ≡ ¬X = ∅ ∧ ∀Y(Y ⊆ X ⇒ (Y = X ∨ Y = ∅)

)I ≤ (sans <):

x ≤ y ≡ ∀X(y ∈ X ∧ ∀z (z + 1 ∈ X ⇒ z ∈ X)

)⇒ x ∈ X

I partition:

Xi ∧n−1∧i=1

n∧j=i+1

Xi ∩Xj = ∅

I singleton:

)I ≤ (sans <):

x ≤ y ≡ ∀X(y ∈ X ∧ ∀z (z + 1 ∈ X ⇒ z ∈ X)

)⇒ x ∈ X

I partition:

Xi ∧n−1∧i=1

n∧j=i+1

Xi ∩Xj = ∅

I singleton:

I ≤ (sans <):

x ≤ y ≡ ∀X(y ∈ X ∧ ∀z (z + 1 ∈ X ⇒ z ∈ X)

)⇒ x ∈ X

I partition:

Xi ∧n−1∧i=1

n∧j=i+1

Xi ∩Xj = ∅

I singleton:

)I ≤ (sans <):

x ≤ y ≡ ∀X(y ∈ X ∧ ∀z (z + 1 ∈ X ⇒ z ∈ X)

)⇒ x ∈ X

I partition:

Xi ∧n−1∧i=1

n∧j=i+1

Xi ∩Xj = ∅

I singleton:

)I ≤ (sans <):

x ≤ y ≡ ∀X(y ∈ X ∧ ∀z (z + 1 ∈ X ⇒ z ∈ X)

)⇒ x ∈ X

S1SΣ: langages

Soit φ une formule close (formule sans variable libre).

L(φ) :={w ∈ Σω

∣∣ w |= φ}

I ω-mots dans lesquels tout a est suivi d’un b:

∀x Pa(x) ⇒ ∃y (x < y ∧ Pb(y))

I ω-mots dans lesquels entre 2 occurrences successives de a il ya un nombre pair de b ou c:

∀x∀y Pa(x) ∧ Pa(y) ∧ x < y ∧ ¬∃z(x < z ∧ z < y ∧ Pa(z)

)⇒ ∃X

(x ∈ X ∧ ∀z (z ∈ X ⇔ ¬z + 1 ∈ X) ∧ ¬y ∈ X

S1SΣ: langages

L(φ) :={w ∈ Σω

∣∣ w |= φ}

∀x Pa(x) ⇒ ∃y (x < y ∧ Pb(y))

)⇒ ∃X

(x ∈ X ∧ ∀z (z ∈ X ⇔ ¬z + 1 ∈ X) ∧ ¬y ∈ X

S1SΣ: langages

L(φ) :={w ∈ Σω

∣∣ w |= φ}

∀x Pa(x) ⇒ ∃y (x < y ∧ Pb(y))

)⇒ ∃X

(x ∈ X ∧ ∀z (z ∈ X ⇔ ¬z + 1 ∈ X) ∧ ¬y ∈ X

S1SΣ: langages

L(φ) :={w ∈ Σω

∣∣ w |= φ}

∀x Pa(x) ⇒ ∃y (x < y ∧ Pb(y))

)⇒ ∃X

(x ∈ X ∧ ∀z (z ∈ X ⇔ ¬z + 1 ∈ X) ∧ ¬y ∈ X

)Yohan Boichut Logique monadique du 2nd ordre pour les mots infinis Cours Master IRAD – Semestre 1 25 / 34

formules de S1S = formules de S1SΣ sans les predicats Pa

interpretees sur la structure:⟨N, 0,+1, <

S1SΣ S1S

Σ {0, 1}n

Pa variables libres X1, . . . , Xn

w ∈ Σω interpretation δ|{X1,...,Xn}

Pa(x)∧

x ∈ Xi ∧∧

x /∈ Xi

avec a = (a1, . . . , an) ∈ {0, 1}n

φ(Y ) ψ(Y ,X1, . . . , Xn)

Theoreme de Buchi

TheoremeBuchi 1962 Un sous ensemble de Σω est definissable en S1S ssi ilest ω-regulier.

⇐: (Q, qi, F,∆) automate de Buchi sur Σ avec Q = {0, . . . ,m},qi = 0.Existence d’un calcul acceptant sur w ∈ Σω en S1SΣ (Y0, . . . , Ym

sont les positions respectives des etats):

∃Y0 . . .∃Ym Y0, . . . , Ym partition N∧ 0 ∈ Y0 ∧ ∀x

∧i−→a j∈∆

(x ∈ Yi ⇒ (Pa(x) ⇒ x+ 1 ∈ Yj))

∧∧i∈F

∀x∃y (x < y ∧ y ∈ Yi)

I pas de variables du premier ordre

I X ⊆ Y

I Y = X + 1 (X = {x}, Y = {y} et y = x+ 1)

ex: singleton(X) ≡ ∃Y(Y ⊆ X ∧ Y 6= X ∧ ¬∃Z (Z ⊆ X ∧ Z 6=

X ∧ Z 6= Y ))

LemmeToute formule de S1S peut etre transformee en une formule deS1S0 equivalente.

pr.: reecriture de la formule en plusieurs etapes:

1. elimination des 0 et <.

2. elimination des +1 imbriquesatomes apres elimination: x = y, y = x+ 1, x ∈ X.

3. elimination des variables du premier ordre.

Theoreme de Buchi: ⇒

LemmeUn sous ensemble de Σω est definissable en S1S0 est ω-regulier.

pr.: φ(X1, . . . , Xn) → Buchi sur {0, 1}n, par recurrence.I X1 ⊆ X2

0 0 10 1 1

I X2 = X1 + 1

Theoreme de Buchi: ⇒

LemmeUn sous ensemble de Σω est definissable en S1S0 est ω-regulier.

pr.: φ(X1, . . . , Xn) → Buchi sur {0, 1}n, par recurrence.

I ∧, ∨, ¬ (formules avec meme variables libres -cylindrification): operations Booleennes.

I ∃: projection.

Theoreme de Buchi

TheoremeS1S est decidable.

Complexite non elementaire [Meyer 1975].

Outline

1 Mots infinis

3 Epilogue

Epilogue

Nous avons vu

I Logique monadique faible du 2nd ordre avec un successeur –Automates de mots finis.

I Logique monadique du 2nd ordre avec un successeur –Automates de Buchi.

Et alors ?

I Bases theoriques du Model-checking – Technique deverification de systemes critiques.

I Le point faible est le calcul du complement d’un automate deBuchi.

I Comment faire de la verification avec cette difficulte ?

Epilogue

Nous avons vu

Et alors ?

Epilogue

Nous avons vu

Et alors ?

Epilogue

Nous avons vu

Et alors ?

Epilogue

Nous avons vu

Et alors ?

Epilogue

Nous avons vu

Et alors ?

Coming Next

Master 2 : Modelisation et Verification

Encore avec moi :-)

Coming Next

Master 2 : Modelisation et Verification

Encore avec moi :-)

Logique monadique du 2nd ordre pour les mots infinis · Logique monadique du 2nd ordre pour les...

Documents

Logique du premier ordre (Logique de prédicats)

Systèmes distribués : Rappel sur ordre et temps …ecariou.perso.univ-pau.fr/cours/sd-m1/cours-rappel-temps.pdf1 Systèmes distribués : Rappel sur ordre et temps logique Eric Cariou

2nd Marine Division

«2nd BAC» Projet 03 «2nd BAC» Page 1 sur 5 Bordes …docs-avms.com/classeurs/Plans/2nd BAC/Projet 03 #Bordes 2nd BAC… · Projet 03 «2nd BAC » «2nd BAC» Projet ... Dalle

Le calcul des prédicats Motivations - irif.frkesner/enseignement/licence/logique/Predicats-syntaxe.pdf · Le calcul des prédicats ou logique du premier ordre Le calcul propositionnel

La quantification du premier ordre en logique temporelle

Théorie de la correspondance - Mikael Cozicmikael.cozic.free.fr/correspondance.pdf · intervenir la logique du second ordre. Ainsi elle hérite de la compacité et du théorème

Programmation logique - zegour.esi.dzzegour.esi.dz/Site secondaire/Mcp/Cours ppt/18_logic1.pdf · Programmation logique Logique des prédicats du premier ordre ˜ Introduction •

1 Logique du premier ordre (Logique de prédicats) Chap. 8

SCIENCES ECO GRENOBLE - ftp.oceanix.netftp.oceanix.net/DiagFNCI/Cours/ADF_v01.pdf · Ce polycopié constitue votre cours d’analyse ﬁnancière. Il est organisé dans un ordre logique

Landscape 2nd Lec

Intelligence Artificielle Logique (2/3)bouzy/Doc/IAL3/07_IA_logique_BB.pdf · Logique du premier ordre Domaine des liens de parent e La m ere d’une personne est son parent f eminin

Logique du premier ordre - FIL Lille 1salvati/cours/logique/...opérateur unaire : S, le successeur opérateurs binaires : + et , l’addition et la multiplication S(+(S(0); (S(S(0));S(0))))

Calendriercomplet 2nd semestre

Diapositive 1 - CESI...30 40 50 60 2009 2nd semestre 2010 1er semestre 2010 2nd semestre 2011 2nd semestre 2012 2nd semestre 2013 2nd semestre ... 30 9 9 11 12 6 ... La France et la

2nd draft_attempter_la_musique

Programmation logique Logique des prédicats du premier ordre

1. Identification d’un système du 1er ordre...Identification d’un système du 1er ordre et du 2nd ordre TD Page 1/5 Système Entrée Sortie 1. Identification d’un système du

I. Système du 1 er ordre: 1.1 Définition 1.2 Exemples 1.3 Etude temporelle Réponse à un échelon Réponse à une rampe II. Système du 2nd ordre: 2.1 Définition

ULTRASONIC 2nd Generation