Synthèse pour une logique temps-réel faible, Synthesis for a weak real-time logic

Description

Sous la direction de Igor Walukiewicz
Thèse soutenue le 07 décembre 2009: Bordeaux 1
Dans cette thèse, nous nous intéressons à la spécification et à la synthèse de contrôleurs des systèmes temps-réels. Les modèles pour ces systèmes sont des Event-recording Automata. Nous supposons que les contrôleurs observent tous les évènements se produisant dans le système et qu'ils peuvent interdirent uniquement des évènements contrôlables. Tous les évènements ne sont pas nécessairement contrôlables. Une première étude est faite sur la logique Event-recording Logic (ERL). Nous proposons des nouveaux algorithmes pour les problèmes de vérification et de satisfaisabilité. Ces algorithmes présentent les similitudes entre les problèmes de décision cité ci-dessus et les problèmes de décision similaires étudiés dans le cadre du $\mu$-calcul. Nos algorithmes corrigent aussi des algorithmes présents dans la littérature. Les similitudes relevées nous permettent de prouver l'équivalence entre les formules de ERL et les formules de ERL en forme normale disjonctive. La logique ERL n'étant pas suffisamment expressive pour décrire certaines propriétés des systèmes, en particulier des propriétés des contrôleurs, nous introduisons une nouvelle logique WT$_\mu$. La logique WT$_\mu$ est une extension temps-réel faible du $\mu$-calcul. Nous proposons des algorithmes pour la vérification des systèmes lorsque les propriétés sont écrites en WT$_\mu$. Nous identifions deux fragments de WT$_\mu$ appelés WT$_\mu$ bien guardé ($WG$-WT$_\mu$) et WT$_\mu$ pour le contrôle ($C$-WT$_\mu$). La logique $WG$-WT$_\mu$ est plus expressif que $C$-WT$_\mu$. Nous proposons un algorithme qui permet de vérifier si une formule de $WG$-WT$_\mu$ possède un modèle (éventuellement déterministe). Cet algorithme nécessite de connaître les ressources (horloges et constante maximale comparée avec les horloges) des modèles. Dans le cadre de $C$-WT$_\mu$ l'algorithme que nous proposons et qui permet de décider si une formule possède un modèle n'a pas besoin de connaître les ressources des modèles. En utilisant $C$-WT$_\mu$ comme langage de spécification des systèmes, nous proposons des algorithmes de décision pour le contrôle centralisé et le $\Delta$-contrôle centralisé. Ces algorithmes permettent aussi de construire des modèles de contr\^oleurs. Lorsque les objectifs de contrôle sont décrits à l'aide des formules de $WG$-WT$_\mu$, nous montrons également comment synthétiser des contrôleurs décentralisés avec des ressources fixées à l'avance et ceci, lorsqu'au plus un contrôleur est non déterministe.
-Systèmes temps-réel
-Event-Recording automata
-Logique temps-réel
-Satisfaisabilité
-Event-Recording Logic
-Méthodes formelles
-Vérification
-Synthèse de contrôleurs
In this dissertation, we consider the specification and the controller synthesis problem for real-time systems. Our models for systems are kinds of Event-recording automata. We assume that controllers observe all the events occurring in the system and can prevent occurrences of controllable events. We study Event-recording Logic (ERL). We propose new algorithms for the model-checking and the satisfiability problems of that logic. Our algorithms are similar to some algorithms proposed for the same problems in the setting of the standard $\mu$-calculus. They also correct earlier proposed algorithms. We define disjunctive normal form formulas and we show that every formula is equivalent to a formula in disjunctive normal form. Unfortunately, ERL is rather weak and can not describe some interesting real-time properties, in particular some important properties for controllers. We define a new logic that we call WT$_\mu$. The logic WT$_\mu$ is a weak real-time extension of the standard $\mu$-calculus. We present an algorithm for the model-checking problem of WT$_\mu$. We consider two fragments of WT$_\mu$ called well guarded WT$_\mu$ ($WG$-WT$_\mu$) and WT$_\mu$ for control ($C$-WT$_\mu$). We show that the satisfiability of $WG$-WT$_\mu$ is decidable if the maximal constants appearing in models are known a priori. Our algorithm allows to check whether a formula of $WG$-WT$_\mu$ has a deterministic model. The algorithm we propose to decide whether a formula of $C$-WT$_\mu$ has a model does not need to know the maximal constant used in models. All the algorithms for the satisfiability checking construct witness models. Using $C$-WT$_\mu$, we present algorithms for a centralised controller synthesis problem and a centralised $\Delta$-controller synthesis problems. The construction of witness controllers is effective. We also consider the decentralised controller synthesis problem with limited resources (the maximal constants used in controllers is known a priory) when the properties are described with $WG$-WT$_\mu$. We show that this problem is decidable and the computation of witness controllers is effective.
-Real-time systems
-Event-recording automata
-Formal methods
-Real-time logic
-µ-calculus
-Event-recording logic
-Satisfiability
-Model-checking
-Controller synthesis
Source: http://www.theses.fr/2010BOR13931/document

Subjects

• Documents
• Knowledge
• Méthode formelle (informatique)
• Vérification

Informations

• Published by: Thesee
• Reads: 20
• Language: English

Exrait

.
Lime
.
vité
.
d'ordre
.
:
Professeur,
3931
Nan
THÈSE
.
PRÉSENTÉE
.
À
Rec
L'UNIVERSITÉ
.
DE
aris
BORDEA
.
UX
.
ÉCOLE
.
DOCTORALE
.
DE
.
MA
.
THÉMA
.
TIQUES
HDR
ET
.
D'INF
orteur
ORMA
aris
TIQUE
.
P
.
ar
École
Omer
W
Landry
herc
Nguena
.
Timo
.
POUR
André
OBTENIR
Professeur
LE
.
GRADE
.
DE
.
DOCTEUR
In
SPÉCIALITÉ
.
:
Chargé
INF
he
ORMA
.
TIQUE
.
SYNTHESE
.
POUR
.
UNE
rançois
LOGIQUE
ersité
TEMPS-REEL

F
.
AIBLE
orteur
(SYNTHESIS
.
F
.
OR
de
A
trale
WEAK
Examinateur
REAL-TIME
.
LOGIC)
de
Souten
CNRS
ue
.
le
.
:
.
07
.
Décem
de
bre
.
2009
.
Après
la
a
.
vis
.
des
.
rapp
.
orteurs
.
:
.
F
2009
ranc
Cassez
k
.
Cassez
.
.
.
.
de
.
herc
.
CNRS,
.
.
.
.
Chargé
.
de
.
Rec
.
herc
.
he
.
CNRS,
Rapp
HDR
F
F
Laroussinie
rançois
Univ
Laroussinie
P
Professeur,
Diderot
Univ
P
ersité
7
P
.
aris
Rapp
Diderot
Didier

.
P
.
aris
.
7
.
Dev
Maître
an
Conférences,
t
Cen
la
de
commission
tes
d'examen
Igor
comp
alukiewicz
osée
.
de
Directeur
:
Rec
Marc
he
Zeitoun
.
.
.
.
.
.
.
.
.
.
.
.
.
Professeur,
.
Univ
.
ersité
Directeur
Bordeaux
Thèse
1
Arnold
.
.
.
.
.
.
.
à
.
retraite
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Présiden
.
t
.
du
.
jury
.
F
ranc
k
oNprésidé
ymeric
plus.
ts
p
Ce
promptemen
man
enric
uscrit
a
témoigne
et
du
fait
tra
séjour
v
de
ail
aux.
que
v
j'ai
de
réalisé
Je
duran
un
t
Cassez
ma
Didier
thèse,
c
non
t.
pas
Je
en
v
solitaire,
orté
mais
soutenance.
a
Rollet
v
sein
ec
V
le
de
concours
conn
d'une
remercie
m
et
ultitude
clin
de
thèse,
p
Laroussinie
ersonnes:
ortan
des
honoré
p
tra
ersonnes
k
qui
a
m'on
est
t
un
aidé,
bres
encour-
MVTSI
agé,
eu
écouté,
qui
inspiré,
à
encadré.
nom
Ces
particulier
p
uel
ersonnes
Castanet,
on
et
t
ANR
con
ma
tribué
ez
au
ers
ra
et
y
thèse.
onnemen
vide
t
de
de
administrativ
ce
l'Univ
tra
metten
v
tra
ail
Remerciemen
et
jury
je
ranc
tiens
F
à
m'on
les
en
remercier.
cette
Je
qui
ne
acceptan
p
d'examiner
ourrai
aux.
toutes
ami
les
Brlek,
citer;
LA
mais,
très
j'esp
qui
ère
l'est
qu'elles
te
se
grand
reconnaîtron
les
t.
group
André
v
Arnold,
LaBRI
tu
qui
as
éc
débuté
ts
l'encadremen
t
t
l'in
de
tra
cette
ous
thèse.
à
Je
remercie
regrette
G.,
que
et
nos
An
démarc
Ric
hes
ous
de
souten
rec
tégré
herc
pro
he
esTEC
de
an
nancemen
de
t
m'a
n'aien
p
t
diriger
pas
autre
ab
herc
outi.
des
Cep
nir
endan
n'ai
t,
le
je
l'après
garde
ous
de
cela.
b
équip
ons
tec
souv
tretien
enirs
Bordeaux
des
LaBRI
discussions
en
que
agréable
nous
ail.
a
à
v
t
ons
mon
eu
de
p
F
endan
k
t
et
et
rançois
après
qui
la
t
thèse.
honneur
Elles
rapp
étaien
t
t
thèse,
viv
Lime
an
m'a
tes,
en
en
t
thousiastes,
t
motiv
mes
an
v
tes
Mon
et
her
éclairan
Srec
tes.
o
T
mon
u
au
as
CIM
pris
été
de
marquan
ton
Ce
temps
en
de
ressorti
rep
encore
os
Je
p
dis
our
très
assister
merci.
à
remercie
ma
mem
soutenance
du
et
e
témoigner
tra
ainsi
ail
de
du
l'in
a
térêt
ec
p
j'ai
our
des
ce
hanges
tra
hissan
v
et
ail.
on
Je
p
te
de
remercie
térêt
p
mes
our
v
tout
V
cela.
étiez
Igor
breux
W
ma
alukiewicz,
Je
j'ai
en
probablemen
Alain
t
A
écrit
V.,
ou
Emman
dit
F.
b
toine
eaucoup
et
de
hard
c
v
hoses
m'a
erronées.
ez
Cep
u
endan
in
t,
au
tu
du
as
jet
guidé
T
mes
bien
tra
v
v
t
aux
soutenance
a
thèse.
v
ous
ec
v
b
ainsi
eaucoup
ermis
de
me
patience,
v
de
une
rigueur,
thématique
leur
rec
donnan
he
t
d'obtenir
une
ressources
qualité
our
meilleure.
ma
Les
Je
qualités
pas
scien
u
tiques
fameux
qu'on
de
p
thèse.
eut
v
m'attribuer
remercie
son
tout
t
Je
le
les
fruit
es
de
es,
ton
hniques
encadremen
d'en
t.
de
Je
ersité
te
1
remercie
du
p
qui
our
t
tout
place
cela.
cadre
Je
de
remercie
v
Marc
Un
Zeitoun
d'÷il
qui
Jean-louis
a
honorablemenk,
M.,
Saady
Lebna
l'ASECB
M.
mes
et
Larissa
Phillip
N.,
e
organisé
B..
en
Je
Á
remercie
ainsi
les
Jacqueline
équip
Jonathan
es
W.,
p
Camerounais
édagogiques
our
de
je
l'UFR
reconnaissan
Math-Info
t
de
quotidiennes
l'Univ
je
ersité
Sarah
Bordeaux
y
1
W.,
et
Picasso
du
Herv
départemen
I.,
t
des
d'informatique
Stagiaires
de
tous
l'IUT
de
Bordeaux
on
1
euvré
qui
mes
m'on
t'en
t
remercie
in
eurs
tégré
our
comme
L.,
A
cette
TER
E.
ou
profondémen
enseignan
Nathalie
t
Agnes
v
F
acataire.
Aude
En
V
particulier,
atric
je
k
remercie
Dominique
Marie-Christine
Benoît
C.,
N.,
Olivier
I.,
G.,
E.,
Pierre
N.,
C.
bres
Je
ciation
remercie
Étudian
les
Bordeaux)
collègues
on
et
p
amis
Merci
du
cela.
labri
Pierre
qui
as
on
ce
t
oursuiv
fa
sup
v
rance.
orisé
innimen
des
Enn
éc
paren
hanges
et
rendan
ne
t
eort
la
bien
vie
et
au
les
lab
de
oratoire
thèse?
plus
a
sympathique.
que
Si
remercie
je
t
ne
que,
p
R.,
eux
S.,
pas
I.,
tous
K.,
les
ann
citer,
B.,
je
F.,
p
N.,
ense
alery
à:
P
Jérémie
k
C.,
Eric
Olivier
M.,
B.,
Z.,
Bilel
B.,
D.,
B.,
Maxime
M.,
A.,
é
Jo
Mathias
celyn
Wilfrid
F.,
Siméon
Alexandre
Benoît
D.,
Roger
Saad-F
Luc
arès
et
K.,
mem
Joan
de
M.,
(Asso
Hedi
des
H.,
et
Alexander
ts
H.,
de
Y
et
oussou
ceux
D.,
t
Ismail
mon
D.,
ot
Kan
thèse.
té
p
M.,
tout
Maissa
T
M.,
ton
Y
Nguefac
v
tu
es
o
M.,
à
A
que
ymeric
p
V.,
e
Jean-F
études
rançois
érieures
M.,
F
Floren
Je
t
suis
L..
t
Commen
t.
t
je
ne
mes
pas
ts,
faire
frères
un
so
clin
qui
d'÷il
ménagen
à
aucun
v
p
ous
mon
qui
être.
a
Maman
v
papa.
ez
suiviour
construire
algorithme
thèse
des
P
con
our
sp
une
trôleurs.
Logique
WT
T
Nous
emps-Réel
v
F
v
aible
cen
Dans
temps-réel,
cette
certaines
thèse,
nouv
nous
ération,
nous
propriétés
in
la
téressons
prop
à
-WT
la
ressources
sp
utilisan
écication
algorithmes
et
tralisé.
à
:
la
des
syn
e
thèse
en
de
in
con
T
trôleurs
extension
des
osons
systèmes
des
temps-réels.
en
Les
fragmen
mo
de
dèles
-WT
p
qui
our
form
ces
un
systèmes
esoin
son
te
t
des
des
Univ
Ev
nous
en
our
t-recording
LaBRI,
Automata.
ermetten
Nous
de
supp
en
osons
en
que
syn
les
(FRANCE).
con
our
trôleurs
des
observ
des
en
trôleurs,
t
duisons
tous
logique
les
La
év
est
ènemen
faible
ts
Nous
se
algorithmes
pro
v
duisan
lorsque
t
t
dans
Lib
le
tions
système
de
et
elé
qu'ils
our
p
(
euv
).
en
un
t
ermet
in
si
terdiren
de
t
p
uniquemen
dèle.
t
pas
des
connaître
év
et
ènemen
comparée
ts
les
con
dèles.
trôlables.
ersité
T
langage
ous
des
les
osons
év
décision
ènemen
con
ts
et
ne
trôle
son
algorithmes
t
aussi
pas
mo
nécessairemen
trôleurs.
t
temps-réel,
con
automata,
trôlables.
abilité,
Une
Logic,
première
v
étude
de
est
:
faite
expressiv
sur
p
la
décrire
logique
alence-Cedex
Ev
systèmes,
en
particulier
t-recording
propriétés
Logic
con
(ERL).
nous
Nous
tro
prop
une
osons
elle
des
WT
nouv
.
eaux
logique
algorithmes
33405
p
une
our
temps-réel
les
du
problèmes
-calcul.
de
prop
v
des
érication
p
et
la
de
érication
satisfaisabilité.
systèmes
Ces
les
algo-
son
rithmes
écrites
présen
WT
ten
.
t
iden
les
un
similitudes
t
en
WT
tre
app
les
WT
problèmes
p
de
le
décision
trôle
cités
cours
ci-dessus
351,
et
Nous
les
osons
prob-
algorithme
lèmes
p
de
de
décision
érier
similaires
une
étudiés
ule
dans
1,
le
Bordeaux
cadre
ossède
du
mo
Syn
Cet
-calcul.
n'a
Nos
b
algorithmes
de
corrigen
les
t
(horloges
aussi
constan
des
maximale
algorithmes
a
présen
ec
ts
horloges)
dans
mo
la
En
litérature.
t
Les
-WT
similitudes
comme
relev
de
ées
écication
nous
systèmes,
p
prop
ermetten
des
t
de
de
p
prouv
le
er
trôle
l'équiv
tralisé
alence
le
en
-con
tre
cen
les
Ces
form
p
ules
t
de
de
ERL
des
et
dèles
les
con
form
Mots-clés
ules
Systèmes
de
Ev
ERL
t-Recording
en
logique
forme
satisfais-
normale
Ev
disjonctiv
t-Recording
e.
métho
La
formelles,
logique
érication,
ERL
thèse
n'étan
con
t
Discipline
pas
Informatique.
susammen
t
propriétés



C
C
C
Δsho
(FRANCE).
,
thesis
the
F
a
or
eectiv
a
w
W
of
eak
w
Real-Time
mo
Logic
a
In
-calculus,
this
alence-Cedex
dissertation,
-calculus.
w
Lib
e
trol
consider
-WT
the
form
sp
kno
ecication
a
and
cen
the
problems.
con
t-Recording
troller
mo
syn
w
thesis
WT
problem
of
for
t
real-time
king
systems.
consider
Our
WT
mo
351,
dels
satisabilit
for
The
systems
for
are
-WT
kinds
es
of
constan
Ev
enables
en
Using
t-recording
t
automata.
syn
W
-con
e
witness
assume
Real-time
that
ds,
con
Logic,
trollers
con
observ
logic
e
call
all
The
the
is
ev
real-time
en
standard
ts
e
o
algorithm
ccurring
del-c
in
of
the
W
system
fragmen
and
la
can
for
prev
cours
en
W
t
that
o
of
ccurrences
is
of
rithm
con
prop
trollable
whether
ev
of
en
,
ts.
del
W
need
e
the
study
used
Ev
and
en
construction
t-recording
mo
Logic
-WT
(ERL).
e
W
for
e
con
prop
problem
ose
tralised
new
syn
algorithms
construction
for
trollers
the
Keyw
mo
Ev
del-c
formal
hec
logic,
king
en
and
y
the
hec
satisabilit
syn
y
new
problems
that
of
e
that
WT
logic.
T
Our
logic
algorithms
33405
are
a
similar
eak
to
extension
some
the
algorithms
ération,
prop
W
osed
presen
for
an
the
for
same
mo
problems
hec
in
problem
the
WT
setting
.
of
e
the
a
standard
t
Syn
WT
-calculus.
called
They
de
also
con
correct
(
earlier
-WT
prop
).
osed
e
algorithms.
w
W
the
e
y
dene
1,
disjunctiv
Bordeaux
e
decidable.
normal
algo-
form
that
form
e
ulas
ose
and
deciding
w
a
e
ula
sho
ersité
w
Univ
that
has
ev
mo
ery
do
form
not
ula
to
is
w
equiv
maximal
alen
t
t
in
to
dels
a
it
form
the
ula
of
in
witness
disjunctiv
del.
e
LaBRI,
normal
Science.
form.
w
Unfortunately
presen
,
algorithms
ERL
a
is
tralised
rather
troller
w
thesis
eak
and
and
cen
can
Computer
not
troller
describ
thesis
e
The
some
of
in
con
teresting
is
real-time
e.
prop-
ords:
erties,
systems,
in
en
particular
automata,
some
metho
imp
real-time
ortan
Discipline:
t
Ev
prop
t-Recording
erties
satisabilit
for
,
con
del-c
trollers.
king,
W
troller
e
thesis.
dene
a
.



C C
C
C
Δ
.
.
Constrain
ten
29
ts
.
In
.
tro
Sp
duction
.
1
.
1
2.2.1
Preliminaries
.
15
.
1.1
.
Automata
for
on
.
W
V
ords
Constrain
.
.
.
.
.
.
.
.
.
.
.
.
.
The
.
.
.
Madh
.
28
.
.
.
c
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Zone
.
.
.
2.3.2
.
.
.
del
.
.
.
.
15
.
1.2
Approac
T
.
w
et
o
ecication
Pla
.
y
cesses
er
Constrain
P
.
arit
.
y
.
Games
Clo
and
.
Multi-P
.
arit
.
y
.
Games
.
.
.
.
.
.
.
.
35
.
.
.
.
.
.
.
.
.
.
.
F
.
.
.
.
.
2.2.2
.
.
.
.
.
.
17
and
1.3
.
The
.
Con
.
-Calculus
.
.
.
.
.
.
.
.
Op
.
.
.
.
.
Automata
.
.
.
.
.
.
.
.
.
.
.
.
.
1.6.2
.
et
.
for
.
.
.
.
.
The
.
Approac
.
.
.
.
.
.
.
.
.
Timed
.
2.1
.
V
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
35
.
ks
18
.
1.3.1
.
Denitions
.
and
.
Seman
.
tics
.
.
.
.
35
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Regions
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
for
.
Constrain
.
.
.
.
18
.
1.3.2
.
Mo
.
del-Chec
for
king
.
and
.
Satisabilit
.
y
.
Results
.
.
.
.
2.3
.
Bounded
.
.
.
.
.
.
.
.
.
.
.
45
.
Represen
.
.
.
.
.
.
.
.
.
.
.
.
.
.
22
of
1.3.3
on
Disjunctiv
.
e
.
Normal
.
F
i
orm
46
.
Mo
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
26
.
The
.
usudan
.
al.
.
h
.
Automata
.
ecication
.
.
.
.
.
.
.
1.6.3
.
Laroussinie
.
al.
23
h
1.4
.
Alternating
Sp
T
.
ree
.
Automata
.
.
.
.
.
.
.
.
2
.
Pro
.
33
.
Clo
.
k,
.
aluation,
.
ts
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.1.1
.
c
.
and
.
aluations
.
.
23
.
1.5
.
F
.
ramew
.
orks
.
for
.
Discrete-Time
.
Con
.
trol
.
.
.
.
.
.
.
.
.
.
2.1.2
.
ts
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
24
2.2
1.5.1
.
The
.
Ramadge
.
et
.
al.
.
Approac
.
h
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
41
.
Regions
.
Diagonal
.
ree
.
ts
.
.
.
.
.
.
.
.
.
.
.
.
25
.
1.5.2
.
The
.
Arnold
42
et
Regions
al.
General
Approac
ts
h
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
45
.
Zones
.
Dierence
.
Matrices
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
25
2.3.1
1.6
and
F
tation
ramew
.
orks
.
for
.
Dense-Time
.
Sup
.
ervisory
.
Con
.
trol
.
.
.
.
.
.
.
.
.
.
.
.
45
.
Computation
.
some
.
erations
.
DBMs
.
.
.
.
.
.
.
.
.
.
.
.
.
.
26
1.6.1
Timed

L.
.
.
Mo
.
dels
Mo
for
.
Timed
82
Pro
.
cesses
.
.
3.2.4
.
.
.
.
.
y
.
.
.
Constrain
.
.
.
.
.
.
.
.
.
.
.
.
.
3.3.1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Zone
.
e
.
.
.
T
.
.
.
93
.
.
.
.
.
.
48
.
2.4.1
.
Denitions
y
.
.
.
.
.
.
.
.
.
3.3.2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Pro
.
82
.
.
.
Existen
.
.
.
.
.
.
.
.
.
.
.
Results
.
.
.
Bac
.
Concluding
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
48
.
2.4.2
.
Seman
.
tics
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
T
.
.
.
.
.
.
.
3.3.3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Earlier
.
.
.
.
.
.
.
Seman
.
F
.
.
.
ableau
.
.
.
.
50
.
2.4.3
y
Represen
.
tations
.
for
Not
Timed
.
Pro
.
cesses
.
.
.
.
.
.
.
.
.
.
Denition
.
.
.
.
.
.
.
and
.
.
.
.
.
.
.
.
.
.
.
.
.
4
.
.
.
.
.
.
.
.
51
.
2.5
69
Pro
king
duct
.
of
.
Timed
.
Pro
.
cesses
.
.
.
.
.
.
y
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.3
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ableau
.
.
.
.
.
.
.
.
.
.
.
.
52
.
2.6
.
Reac
.
habilit
tics
y
.
Analysis
.
.
.
.
.
.
.
.
.
.
.
.
.
.
y
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.3.4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Comparison
.
orks
.
.
.
.
.
.
.
.
.
.
.
.
.
3.4.1
.
for
53
and
2.6.1
ulas
Region-based
.
Algorithms
.
.
Sorea's
.
of
.
.
.
.
.
.
.
.
.
.
.
83
.
Mo
.
y
.
Division
.
.
.
.
.
83
.
h
.
.
.
.
.
.
.
.
.
.
.
.
.
3.5
.
F
.
.
.
.
.
.
54
.
2.6.2
.
Zone-based
.
Algorithms
.
.
87
.
Satisabilit
.
.
.
.
.
.
.
.
.
.
.
87
.
Equiv
.
ableau
.
Edges
.
.
.
.
.
88
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Logic
.
2.4
.
.
.
.
.
.
55
.
2.7
.
Diagonal
.
Constrain
.
ts
.
Can
.
Be
.
Safely
3.2.3
Remo
del-Chec
v
Results
ed
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
70
.
Complexit
.
.
.
.
.
.
.
.
.
.
58
.
2.8
.
Concluding
.
Remarks
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
71
.
Satisabilit
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
72
.
T
.
.
.
.
60
.
3
.
Results
.
on
.
Ev
.
en
.
t-Recording
.
Logic
.
61
.
3.1
.
Ev
.
en
.
t-Recording
.
Logic
.
.
.
.
.
.
72
.
Seman
.
of
.
ableau
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
76
.
Satisabilit
.
Results
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
63
.
3.1.1
.
Denitions
.
.
.
.
.
.
77
.
Complexit
.
Issues
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.4
.
With
.
W
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
63
.
3.1.2
.
Seman
82
tics
Sorea's
.
tics
.
Timed
.
cess
.
ERL
.
orm
.
.
.
.
.
.
.
.
.
.
.
3.4.2
.
T
.
System
.
Rules
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.4.3
.
tial
.
dalit
.
Ma
.
Cause
.
t
.
.
.
.
.
.
.
.
63
.
3.2
.
Mo
3.4.4
del-Chec
Approac
king
Is
.
Correct
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
85
.
Disjunctiv
.
Normal
.
orm
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3.5.1
.
and
.
y
.
.
.
.
66
.
3.2.1
.
Abstract
.
Seman
.
tics
.
for
.
F
.
orm
.
ulas
.
.
3.5.2
.
ableau
.
alence
.
T
.
With
.
k
.
.
.
.
.
.
.
.
.
.
.
.
.
3.6
.
Remarks
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
67
.
3.2.2
.
Fixp
.
oin
.
t
.
Appro
.
ximation
.
.
.
.
92
.
The
.
WT
.
.
.
.
.
.
Syn
.
tax
.
and
.
Seman
.
tics
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Sp
.
.
.
.
.
Restricted
.
.
.
rom
.
Mo
.
Automata
.
.
.
.
.
126
.
.
.
.
.
.
.
.
.
tralised
.
Mo
.
.
.
.
.
.
.
.
.
.
.
.
.
5.2
.
.
94
.
4.1.1
.
Denitions
.
.
.
.
.
.
.
.
.
.
thesis
.
.
.
thesis
.
.
.
.
.
.
.
.
.
.
.
and
.
.
.
.
.
.
.
.
.
.
.
thesis
.
Mo
.
Con
.
.
.
and
.
.
.
.
.
.
.
del-
.
.
.
.
.
.
.
.
.
.
.
.
.
.
94
.
4.1.2
.
Seman
.
tics
.
of
.
WT
to
4.1
.
.
.
.
118
.
F
.
.
.
.
.
5.3
.
.
.
.
.
.
.
.
.
tralised
.
.
.
.
.
.
.
tralised
.
.
.
.
.
.
.
-Dense-Time
.
.
.
.
.
127
.
.
.
.
.
.
.
.
.
.
.
es
.
.
.
.
95
.
4.1.3
.
Restricted
.
Logics:
.
Index
.
133
.
-WT
.
.
5
and
troller
.
C-WT
-WT
111
.
Automata
.
Automata
.
Syn
.
.
.
.
.
5.1.1
.
tics
.
.
.
.
.
.
.
.
.
.
.
.
.
5.1.2
.
king
.
.
.
.
.
.
97
.
4.1.4
.
Rectangular
.
F
.
orm
115
ulas
dal
.
-MA
.
.
.
.
.
.
.
.
.
and
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.2.1
.
orm
.
dal
.
.
.
.
.
.
.
.
.
.
.
F
.
Automata
.
ulas
.
.
.
.
.
.
98
.
4.1.5
.
Relation
t
b
.
et
.
w
.
een
.
ERL
.
and
.
WT
.
.
.
.
5.4
.
troller
.
.
.
.
.
.
.
.
.
.
.
.
.
5.4.1
.
troller
.
.
.
.
.
.
.
.
.
.
.
.
.
The
.
trol
.
.
.
.
.
.
.
.
99
.
4.2
Conclusion
Mo
.
del-c
.
hec
.
king
.
.
.
.
.
.
.
.
.
.
.
.
129
.
ersp
.
Bibliograph
.
.
.
.
.
.
.
.
.
.
.
.
.
145
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
109
.
Cen
.
Con
.
Syn
.
using
.
.
.
ecication
.
5.1
.
dal
.
and
101
dal
4.2.1
for
Abstract
troller
Seman
thesis
tics
.
for
.
F
.
orm
.
ulas
113
.
Denition
.
Seman
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
113
.
Mo
.
Chec
.
.
.
.
.
.
.
.
101
.
4.2.2
.
Mo
.
del-Chec
.
king
.
Results
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.1.3
.
Mo
.
Automata:
.
.
.
and
.
-MA
.
.
.
.
.
.
.
.
.
.
.
.
.
117
.
Automata
.
Logic
.
.
.
.
.
.
.
.
.
.
.
.
102
.
4.3
.
Satisabilit
.
y
.
of
.
the
.
.
.
-WT
.
.
.
F
.
ragmen
118
t
F
.
F
.
ulas
.
Mo
.
Automata
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.2.2
.
rom
.
dal
.
to
.
orm
.
.
.
.
.
.
.
.
103
.
4.3.1
.
T
.
ableaux
.
.
.
.
.
.
121
.
Quotien
.
for
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
123
.
Cen
.
Con
.
Syn
.
for
.
-WT
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
103
.
4.3.2
.
Satisabilit
126
y
Cen
Results
Con
.
Syn
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.4.2
.
.
.
Con
.
Problem
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5.5
.
.
106
.
4.3.3
.
Existence
.
of
.
Deterministic
.
Mo
.
dels
.
for
.
F
.
orm
.
ulas
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Conclusion
.
P
.
ectiv
.
131
.
y
.
.
108
.
4.4
.
Concluding
.
Remarks
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

WG C

C

WG C
C
Δ