Embed Size (px)
Citation preview
Die Korrespondenz zwischenAutomaten und Logik
Logische Aspekte von XML (SS03)
Jens Kerber
Betreuer: Tim Priesnitz
Gert SmolkaProgramming Systems LabUniversität des Saarlandes
[Moshe Vardi: “A match made in heaven“]
Einführendes Beispiel
q0 q1
a
b
b a
))(.)(.( yPyxyxPx ba
Überblick
• Darstellungen mit Hilfe der charakteristischen Mengen
• schwache SkS
• Korrespondenz zwischen Baumautomaten und schwacher SkS
• Komplexität
• Anwendung auf Presburger Arithmetik
Isomorphie zwischen Prädikaten und Mengen
Charakteristische Funktion:
Charakteristische Menge:
Ba falls 0,
Ba falls 1,
}1,0{
(a)A: fa
Af
AB
B
B
}1)(|{
afAaS
AS
f
f
String als Matrix
*
*
*
*
0000
0
0
0
0
...
00000
10000
00110
01001
43210
},,,{
d
c
b
a
f
f
f
f
cabba
dcba
Charakterisierende Mengen als String
d
c
b
a
S
S
S
S
}4{
}2,1{
}3,0{
*
*
*
*
0000
0
0
0
0
...
00000
10000
00110
01001
43210
},,,{
d
c
b
a
f
f
f
f
cabba
dcba
String als Matrix
*
*
*
*
0
0
0
0
...
00000
10000
00110
01001
43210
d
c
b
a
f
f
f
f
String als Matrix
Tupel-Automat
*
*
*
*
0
0
0
0
...
00000
10000
00110
01001
43210
d
c
b
a
f
f
f
f
String als Matrix
Tupel-Automat
Logik
*
*
*
*
0
0
0
0
...
00000
10000
00110
01001
43210
d
c
b
a
f
f
f
f
schwache SkS
Nur Variablen 2. Ordnung
Atomare Formeln:
Logische Verknüpfungen:
YiXYX ,
X.φ, φφ, φ 21
Abgeleitete PrädikateTeilmenge).( YxXxxYX
def
Abgeleitete PrädikateTeilmenge
Wurzel
).( YxXxxYXdef
YiXYXdef
.}{
Abgeleitete PrädikateTeilmenge
Wurzel
Endliche Vereinigung).(111
i
n
ii
n
i
def
i
n
iXxXxxXXXX
U
).( YxXxxYXdef
YiXYXdef
.}{
Abgeleitete PrädikateTeilmenge
Wurzel
Endliche Vereinigung
Schnittmenge)(. YxXxZxxZYXdef
).(111
i
n
ii
n
i
def
i
n
iXxXxxXXXX
U
).( YxXxxYXdef
YiXYXdef
.}{
Abgeleitete PrädikateTeilmenge
Wurzel
Endliche Vereinigung
Schnittmenge
Disjunkte Zerlegung
ji
n
ij
n
ii
n
i
def
n XXXXXXX1
1
111 ),...,,Partition( U
)(. YxXxZxxZYXdef
).(111
i
n
ii
n
i
def
i
n
iXxXxxXXXX
U
).( YxXxxYXdef
YiXYXdef
.}{
Abgeleitete PrädikateTeilmenge
Wurzel
Endliche Vereinigung
Schnittmenge
Disjunkte Zerlegung
PräfixabgeschlossenheitXyzyXzyz(X)def
).(.edPrefixClos
ji
n
ij
n
ii
n
i
def
n XXXXXXX1
1
111 ),...,,Partition( U
)(. YxXxZxxZYXdef
).(111
i
n
ii
n
i
def
i
n
iXxXxxXXXX
U
).( YxXxxYXdef
YiXYXdef
.}{
Abgeleitete PrädikateTeilmenge
Wurzel
Endliche Vereinigung
Schnittmenge
Disjunkte Zerlegung
Präfixabgeschlossenheit
GleicheitYXXYXYdef
XyzyXzyz(X)def
).(.edPrefixClos
ji
n
ij
n
ii
n
i
def
n XXXXXXX1
1
111 ),...,,Partition( U
)(. YxXxZxxZYXdef
).(111
i
n
ii
n
i
def
i
n
iXxXxxXXXX
U
).( YxXxxYXdef
YiXYXdef
.}{
Abgeleitete PrädikateTeilmenge
Wurzel
Endliche Vereinigung
Schnittmenge
Disjunkte Zerlegung
Präfixabgeschlossenheit
Gleicheit
Leerheit).( XYXYYXdef
YXXYXYdef
XyzyXzyz(X)def
).(.edPrefixClos
ji
n
ij
n
ii
n
i
def
n XXXXXXX1
1
111 ),...,,Partition( U
)(. YxXxZxxZYXdef
).(111
i
n
ii
n
i
def
i
n
iXxXxxXXXX
U
).( YxXxxYXdef
YiXYXdef
.}{
Abgeleitete PrädikateTeilmenge
Wurzel
Endliche Vereinigung
Schnittmenge
Disjunkte Zerlegung
Präfixabgeschlossenheit
Gleicheit
Leerheit
Einelementige Menge)(.()Sing( YXYXYYXXdef
).( XYXYYXdef
YXXYXYdef
XyzyXzyz(X)def
).(.edPrefixClos
ji
n
ij
n
ii
n
i
def
n XXXXXXX1
1
111 ),...,,Partition( U
)(. YxXxZxxZYXdef
).(111
i
n
ii
n
i
def
i
n
iXxXxxXXXX
U
).( YxXxxYXdef
YiXYXdef
.}{
Abgeleitete Prädikate
XxXzXzizXyXyxk
i
def
))).((.(
1
Teilmenge
Wurzel
Endliche Vereinigung
Schnittmenge
Disjunkte Zerlegung
Präfixabgeschlossenheit
Gleicheit
Leerheit
Einelementige Menge
Ordnung auf Individuen
)(.()Sing( YXYXYYXXdef
).( XYXYYXdef
YXXYXYdef
XyzyXzyz(X)def
).(.edPrefixClos
ji
n
ij
n
ii
n
i
def
n XXXXXXX1
1
111 ),...,,Partition( U
)(. YxXxZxxZYXdef
).(111
i
n
ii
n
i
def
i
n
iXxXxxXXXX
U
YiXYXdef
.}{
).( YxXxxYXdef
Kodiere Bäume inschwacher SkS
X
),...,XTerm(X,Xdef
n1
Nicht leer
Kodiere Bäume inschwacher SkS
),...,X(X,X
X
),...,XTerm(X,X
n
def
n
1
1
Partition
Nicht leer
X disjunkte Vereinigung von X1,...,Xn
Kodiere Bäume inschwacher SkS
(X)
),...,X(X,X
X
),...,XTerm(X,X
n
def
n
edPrefixClos
Partition 1
1
Nicht leer
X disjunkte Vereinigung von X1,...,Xn
Präfixabgeschlossen
Kodiere Bäume inschwacher SkS
X))ylXy.(yX)xlXx.(x(
(X)
),...,X(X,X
X
),...,XTerm(X,X
jjj
f
k
ilf
i
li)arity(f
k
i
n
def
n
111
1
1
edPrefixClos
PartitionNicht leer
X disjunkte Vereinigung von X1,...,Xn
Präfixabgeschlossen
Anzahl Nachfolger entspricht Stelligkeit
Wörter und Bäume in schwacher SkS
Wort:
),,,,(:
}1111{
}11 1,{
}111 ε,{
}1111 111, 11, 1, ε,{
},,,{ 0000
dcba
d
c
b
a
SSSSSKodierung
S
S
S
S
S
abbac
dcba
),,,,,(:
}21{
}11{
}2,1{
}{
}21,11,2,1,{
))1(),0((
}1,0,,,{
10
1
0
00212
SSSSSSKodierung
S
S
S
S
S
S
notnotor
notor
notor
not
or
Baum:
Entscheidbarkeit
Satz: [Büchi,1960][Thatcher&Wright,1968]
schwache SkS ist entscheidbar
Beweisidee:
Rückführung auf Automaten
• Satz: [Büchi,1960][Thatcher&Wright,1968]
Schwache SkS und Baumautomatenhaben die gleiche Expressivität
• Beweisidee Automat nach Formel:Entwickle Formel die genau dann erfüllt ist wennder entsprechende Automat den Baum akzeptiert
• Beweisidee Formel nach Automat:- Induktion über die Struktur der Formel- Baue Automaten für jede Basisformel- Verknüpfe Automaten für Basisformeln
Bottom-up Baumautomat
durch schwache SkS.,...,
1 lqq YY Es existiert Zustandsfolge
Bottom-up Baumautomat
durch schwache SkS
),...,,(
.,...,
1
1
m
l
ff
XXXTerm
YY Es existiert Zustandsfolge
Baum markiert mit Funktionssymbolen
Bottom-up Baumautomat
durch schwache SkS
),...,,(
),...,,(
.,...,
1
1
1
l
m
l
ff
YYXTerm
XXXTerm
YY
Es existiert Zustandsfolge
Baum markiert mit Funktionssymbolen
Baum markiert mit Zuständen
Bottom-up Baumautomat
durch schwache SkS
qQq
ff
Y
YYXTerm
XXXTerm
YY
f
l
m
l
),...,,(
),...,,(
.,...,
1
1
1 Es existiert Zustandsfolge
Baum markiert mit Funktionssymbolen
Baum markiert mit Zuständen
Wurzel im Endzustand
Bottom-up Baumautomat
durch schwache SkS
))()((.
),...,,(
),...,,(
.,...,
)(
1),...,( )(1
1
1
1
ifarity
f
l
m
l
q
farity
iqqqfqf
QqFf
qQq
ff
YxiYxXxx
Y
YYXTerm
XXXTerm
YY
Es existiert Zustandsfolge
Baum markiert mit Funktionssymbolen
Baum markiert mit Zuständen
Wurzel im Endzustand
Alle Transitionsregeln im Lauf respektiern Δ
Endlicher Automat für atomare Formel
YX
01101
11001
Y
Xq0
1
1
1
0
0
0
Endlicher Automat für atomare Formel
YX
*
*
001101
011001
Y
Xq0
1
1
1
0
0
0
Endlicher Automat für atomare Formel
YX
**
**
0001101
0011001
Y
Xq0
1
1
1
0
0
0
q1
Endlicher Automat für atomare Formel
YX
**
**
0001101
0011001
Y
X
q0
1
1
1
0
0
0
q1
Baumautomat für atomare Formel
YX
q
q q
0 0 q
q q
1 1 q
q q
0 1 q
10
11
01
00
Endlicher Automat für atomare Formel
1YX
01000
10000
Y
X
q0 q1 q2
0
0
1
0
0
1
Endlicher Automat für atomare Formel
1YX
*
*
001000
010000
Y
X
q0 q1 q2
0
0
1
0
0
1
0
0
Endlicher Automat für atomare Formel
1YX
**
**
0001000
0010000
Y
X
q0 q1 q2
0
0
1
0
0
1
0
0
q3
Endlicher Automat für atomare Formel
1YX
**
**
0001000
0010000
Y
X
q0 q1 q2
0
0
1
0
0
1
0
0
q3
Baumautomat für atomare Formel
1YX q
q´ q
0 1 q´´
q´´ q
0 0 q´´
q q
1 0 q´
q q´´
0 0 q´´
Akzeptierter Baum für
1YX 0 0
0 1 …
1 0
… …
…
Endliche charakteristische
Funktion in schwacher SkS
0 1 0 1 0 0 1 0 0 0 ...
1 1 1 1 1 1 1 0 0 0 ...
fX
Shape(X)
Endliche charakteristische
Funktion in schwacher SkS
0 1 0 1 0 0 1 0 0 ...
1 1 1 1 1 1 1 0 0 0 ...
fX
Shape(X)
Endliche charakteristische
Funktion in schwacher SkS
0 1 0 1 0 0 1 0 0 ...
1 1 1 1 1 1 1 0 0 0 ...
fX
Shape(X)
),,...,,(rmmodifiedTe 1 coln XXXShape
VerknüpfungNegation:
• Determinisierung • Automat vervollständigen• Normal- und Endzustände vertauschen
Disjunktion:
• Zylindrifikation
Existenzquantifizierung:
• Projektion
Zylindrifikation am Beispiel der Transitivität
ZXZYYX
ZXZYYX
)()(
)(
)(
ZY
YX
q0
1
1
1
0
0
0
q1 q2
0
1
*
*
*
*
Automat fürZXZYYX
q0
q5
q1 q2 q3
q6q7
q8 q9
1
*
1
1
*
0
0
*
0
1
1
*
1
0
*
0
0
*
0
1
*
*
*
*
*
*
*
*
1
1
*
1
0
*
0
0
*
0
1
*
*
*
*
*
*
Projektion am BeispielZYYX
q0
q1 q2
1
1
*
1
0
*
0
0
*
*
1
1
*
1
0
*
0
0
q3 q4
Projektion am BeispielZYYXY .
q0
q1 q2
1
*
0
*
*
1
*
0
q3 q4
Rückführung k-när auf binär
0 1 2 3
0 1 2
0
0
1 1 1
1 1
Rückführung k-när auf binär
0 1 2 3
0 1 2
WSkS WS2S
0
0
1 1 1
1 1
Komplexität• Existenz (Projektion) führt zu ND-Automaten
• Negation führt zu D-Automaten
• ND nach D führt zu exponentieller Größenzunahme
• Sei N Anzahl Quantoralternierungen:
• Sogar WS1S nicht elementar
)(2 22...2 NO
Presburger Arithmetik
}|),,{( 3 cbacba
Satz: [Presburger,1929][Büchi,1960][Elgot,1961]
Presburger Arithmetik ist entscheidbar
),(
Binärdarstellung in schwacher S1S
Ni
in
Nn
2
durch definiert wird
Binärdarstellung in schwacher S1S
Ni
in
Nn
2
durch definiert wird
20 21 22 23 24 25 ...
1 1 0 1 0 0 ...Binärdarstellung der Zahl (11)10: }3,1,0{11 N
Endlicher Automat für Addition
q0 q1
1
1
0
1
0
1
0
0
0
0
1
1
1
0
0
1
1
1
0
1
0
0
0
1
q2
Endlicher Automat für Addition
11
6
5
c
b
a
}3,1,0{
}2,1{
}2,0{
c
b
a
N
N
N
q0 q1
1
1
0
1
0
1
0
0
0
0
1
1
1
0
0
1
1
1
0
1
0
0
0
1
q2
1 0 1 0 0 ...
0 1 1 0 0 ...
1 1 0 1 0 ...
Referenzen[1] Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis Lugiez, Sophie Tison, Marc Tommasi; Tree Automata Techniques and Applications; Online Publication 2002
[2] Wolfgang Thomas; Languages, Automata and Logic; Technical Report 1996
[3] Erich Grädel, Wolfgang Thomas, Thomas Wilke; Automata, Logics, and Infinite Games: A Guide to Current Research; Springer 2002 (LNCS 2500)
[4] Bakhadyr Khoussainov, Anil Nerode; Automata Theory and Its Applications; Birkhäuser 2001
[5] Frank Neven; Automata, Logic, and XML; CSL 2002
[6] Frank Neven, Thomas Schwentick; Query Automata on finite trees; Theoretical Computer Science 2002
[7] Frank Neven; Automata theory for XML researchers; to appear in Sigmod Record
![ChristophLange:Schriftenverzeichnis Inhaltsverzeichnis · Veröffentlichungen: ChristophLange [JA8] Marco B. Caminati, Manfred Kerber, ChristophLangeund Colin Rowat. „VCG – CombinatorialVickrey-Clarke-GrovesAuctions](https://img.pdfslide.org/doc/110x75/5f633fc6456f93284378b3bd/christophlangeschriftenverzeichnis-inhaltsverzeichnis-verffentlichungen-christophlange.jpg)
