Ebbinghaus H.-D., Flum J. — Finite Model Theory :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Ebbinghaus H.-D., Flum J. — Finite Model Theory

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Finite Model Theory

Авторы: Ebbinghaus H.-D., Flum J.

Аннотация:

The book presents the main results of descriptive complexity theory, that is, the connections between axiomatizability of classes of finite structures and their complexity with respect to time and space bounds. The logics that are important in this context include fixed-point logics, transitive closure logics, and also certain infinitary languages; their model theory is studied in full detail. Other topics include DATALOG languages, quantifiers and oracles, 0-1 laws, and optimization and approximation problems. The book is written in such a way that the respective parts on model theory and descriptive complexity theory may be read independently. This second edition is a thoroughly revised and enlarged version of the original text.

Язык:

Рубрика: Математика/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Издание: Second Revised and Enlarged Edition

Год издания: 2006

Количество страниц: 360

Добавлена в каталог: 29.11.2009

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

Connective      4
Consequence      6
Constant      1
Constant symbol      1
Cost      276
Counting quantifier      59 309
Craig property      64
Craig's Theorem      64
Cut      275
CYCLE      2 302
Database      119
Database, relational      12
Datalog      239
DATALOG = E(LFP)      243 245
DATALOG program      239
DATALOG(#)      248
DATALOG, I-      245
DATALOG, P-      248
DATALOG, positive      245 250
DATALOG, S-      241
DATALOG, stratified      241
DATALOG, totally denned WF-      265
DATALOG, well-founded      264
DATALOG, WF-      264
DATALOG, with counting      248
Decidability, of validity for ${FO}^{2}$       98
Decidability, of validity for ${\forall}^{2}{\exists}^{*}$       100
Decidable      126
Definable, explicitly      63
Definable, implicitly      63 217
Definable, in first-order logic      114
Degree of a point in a graph      2
Depth      170
Deterministic transitive closure      123 220
Diameter of a graph      85
Digraph      1
Digraph, acyclic      24 30 253
Distance function, in a graph      2. 23
Distance function, in an ordering      22
DISTINCT      75
Do(p)      15
Domain      1
DTC      123 220
Duplicator      16
E(LFP)      243
EDGE      1
Ehrenfeucht — Fraisse      see “Game element”
Ehrenfeucht — Fraisse, existential      261
Ehrenfeucht — Fraisse, universal      261
Ehrenfeucht's Theorem      18
Enumerable      126
Enumeration, effective of a complexity class      295
Equality symbol      4
Equivalence relation, invariant      107 111
Equivalent      7
Equivalent, ${\rm L}_{\infty{\omega}^{-}}$       42
Equivalent, elementarily      9
Equivalent, logically      6
Equivalent, m-      14
Equivalent, m- in MSO      38 39
Equivalent, on ordered structures      152
Even      199 209
Existence of a fixed-point      166
Expression, plus free regular      114
Expression, regular      108
Expressive power of a logic      122
Extension Axiom      45 53 72
Extensional      239
F (truth value)      7
FALSE      7 10 11 241
Feasible solution      276
Finite model property      95
Finite model property, of ${FO}^{2}$       96 99
Finite model property, of ${\exists}^{*}{\forall}^{2}{\exists}^{*}$       103
Finite model property, of ${\forall}^{2}{\exists}^{*}$       100
Finite model property, of modal logic      99
fixed-point      120 166
Fixed-point logic      see “”Logic fixed-point”
Fixed-point, greatest      167 172
Fixed-point, least      16
Fixed-point, simultaneous      174
Fixed-point, simultaneous least      175
Fo      4
FO(3-PFP)      198
FO(ATC)      261 314
FO(BFP)      235
FO(BFP) < FO(LFP)      237
FO(C)      59
FO(DTC)      123 327
FO(DTC) < FO(PFP)      272
FO(DTC) and LOGSPACE      142 148 151 296 304
FO(IFP)      121 169
FO(IFP) and FO(PFP)      154
FO(IFP) and PTIME      138 149 151 297 302
FO(IFP, #)      208
FO(IFP, #) and PTIME      305 306 315
FO(LFP)      170
FO(M-LFP)      212
FO(PFP)      121 191
FO(PFP) = FO(S-PFP)      193
FO(PFP) = IMP(FO(PFP))      219
FO(PFP) and PSPACE      137 149 151
FO(posDTC)      224
FO(posTC)      143 159 224
FO(posTC) and NLOGSPACE      143 148
FO(S-IFP)      175
FO(S-LFP)      176
FO(S-PFP)      192
FO(TC)      123 159.
FO(TC) < FO(BFP)      237
FO(TC) < FO(LFP)      231
FO(TC) and NLOGSPACE      143 151
Forest      3
Forest, <-      59 60
Formula ${\rm L}_{\infty\omega}$       40 42
Formula atomic      5
Formula bounded DATALOG      250
Formula bounded positive DATALOG      250
Formula DATALOG      240
Formula existential      65
Formula existential FO(posTC)      225
Formula first-order      4 169
Formula I-DATALOG      246
Formula m-Hintikka      18
Formula monotone in a relation      67
Formula negative in X      169
Formula nontrivial      254
Formula normal      95 169
Formula P-DATALOG      249
Formula positive DATALOG      245
Formula positive in a relation      67
Formula positive in X      169
Formula S-DATALOG      241
Formula s-Scott      57
Formula totally denned      194
Formula totally denned WF-DATALOG      265
Formula universal      65
Formula WF-DATALOG      265
Forth property      20
Forth property, s-      51
Fraisse's theorem      21
Frame      99
Free parametric      80
Function symbol      11
Function system, inductive      175
Function system, inflationary      175
Function system, monotone      175
Function, antitone      167 172 192
Function, inductive      166 175
Function, inflationary      120 166 175

Function, monotone      166 175
Function, polynomial time computable      190
Gaifman graph      26
Gaifman's Theorem      31
Game, associated with a digraph      168 172 198
Game, Ehrenfeucht — Frai'sse for ${FO}^{s}$       50
Game, Ehrenfeucht — Frai'sse for ${\rm L}_{\infty\omega}$       42
Game, Ehrenfeucht — Frai'sse for ${\rm L}_{\infty\omega}^{s}$       50
Game, Ehrenfeucht — Frai'sse for FO(TC)      229
Game, Ehrenfeucht — Frai'sse for MSO      38
Game, Ehrenfeucht — Frai'sse with infinitely many moves      42
Game, Ehrenfeucht — Fraisse for counting quantifiers      60
Game, Ehrenfeucht — Fraisse for FO      16 21
Game, Ehrenfeucht — Fraisse for FO(M-LFP)      213
Game, of life      197
Game, pebble      50 60
Global relation      10 12
Global relation, ${\rm L}_{\infty\omega}^{\omega}$ -definable      54
Graph      1
Graph, acyclic      2 306
Graph, acyclic connected      306
Graph, balanced      112
Graph, bipartite      112 113 221 223
Graph, coloured      61
Graph, connected      2 23 29 40 41 85 86 122 123 169 221 309
Graph, connected ordered      23
Graph, directed      1
Graph, Gaifman      26
Graph, of a structure      26
Graph, planar      85
Graph, random      85
Graph, rigid      86
Graph, stable coloured      61
Graph, undirected      1
Graph, with a Hamiltonian circuit      113
grid      302
Halting problem      127
HAM      113 327
Hamiltonian circuit      2 113 327
Hamiltonian path      2
Hanf's Theorem      27
Hard, with respect to $\mathcal C$ -reductions      321
Hard, with respect to $\mathcal L$ -reductions      324
Head, of a clause      239
Head, of a Turing machine      125
Head, read-and-write      125 130
Head, read-only      130
HENK      328
Hierarchy, arity      268 273
Hierarchy, arity for FO(PFP)      272
Hierarchy, polynomial      159 338
Hintikka formula, m-      18
Hold, almost surely      72
Hold, in almost all finite structures      72
Homomorphism      34
Homomorphism, strict      34
Horn sentence      251
In-degree      2
Index of an equivalence relation      107
Induction, on the length of formulas      5
Induction, simultaneous      178
Induction, simultaneous for LFP and IFP      179
Induction, simultaneous for PFP      193
Inductive      166 175
Inflationary      120 166 175
Input inscription      131
Input instance      276
Input tape      127 130
Instr(M)      125 131
Instruction      125 131
Instruction, oracle      331
Intentional      239
Interpolant      64
Interpolation property      64
Interpretation      297 321
Interpretation, of $\sigma$ in $\tau$       297 321
Invariant, s- of a structure      55 200
Invariantization, $\mathcal C-$ on S      301
Invariantization, PTIME-      292—294 301
Invariantization, PTIME- on GRAPH      301
Isomorphic      3
Isomorphic, m-      20
Isomorphic, partially      43
Isomorphic, s-m-      51
Isomorphic, s-partially      51
Isomorphism      3
Isomorphism type      18 77
Isomorphism type, m-      18 25 26
Isomorphism type, s-m-      52
Isomorphism, generalized partial      213
Isomorphism, partial      15
Isomorphism, s-partial      50
Join simultaneous      178
King      97
Language      106 126
Language, acceptable      126
Language, accepted by a Turing machine      126
Language, accepted by an NDA      106
Language, decidable      126
Language, decided by a Turing machine      126
Language, definable by a ${\Sigma}_{1}^{1}$ -sentence      111
Language, definable in FO      114 116
Language, definable in monadic second-order logic      109 111
Language, enumerable      126
Language, noncounting      116
Language, plus free regular      114
Language, recognized by an automaton      111
Language, recognized by an NDA      106 111
Language, regular      108. 110 111
Language, ultimately periodic      112
Law, 0-1 for ${\rm L}_{\infty\omega}^{\omega}$       77
Law, 0-1 for FO      77
Law, labeled 0-1      72
Law, labeled 0-1 for $\Psi$       77
Law, labeled 0-1 for ${\rm L}_{\infty\omega}^{\omega}$       73
Law, labeled 0-1 for ${\Sigma}_{1}^{1}({\forall}^{*}{\exists}^{*})$       88
Law, labeled 0-1 for FO      73
Law, labeled 0-1 for FO(PFP)      200
Law, labeled 0-1 for parametric classes      77
Law, unlabeled 0-1      80
Law, unlabeled 0-1 for ${\rm L}_{\infty\omega}^{\omega}$       80
Law, unlabeled 0-1 for ${\Sigma}_{1}^{1}({\forall}^{*}{\exists}^{*})$       88
Law, unlabeled 0-1 for FO      80
Law, unlabeled 0-1 for FO(PFP)      200
Law, unlabeled 0-1 for parametric classes      80
Law, unlabeled 0-1, failure for ${\Sigma}_{1}^{1}-{FO}^{2}$       98
Leaf      3
Lemma, Pumping      107 111
Lemma, Simultaneous Induction      178
Lemma, Simultaneous Induction for LFP and IFP      179
Lemma, Simultaneous Induction for PFP      193
Lemma, Transitivity      182
Lemma, Transitivity for LFP      182
Lemma, Transitivity for PFP      195
Length of a path      2
Lindstroem extension      309
Lindstroem quantifier      309
Lindstroem quantifier, vectorization of      312
Loewenheim — Skolem theorem      8
LOG      132
Log space-bounded      160
Logarithmic space, deterministic      132
Logarithmic space, nondeterministic      132
Logic      159 289 314
Logic program general      239
Logic, alternating transitive closure      261 314
Logic, bounded fixed-point      235 263
Logic, closed under order-invariant sentences      64
Logic, deterministic transitive closure      123
Logic, existential fixed-point      243

1 2 3 4

О проекте