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

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

Logic, first-order      4 13
Logic, first-order with counting quantifiers      59
Logic, fixed-point with counting      208 248
Logic, inductive fixed-point      169
Logic, infinitary      40
Logic, inflationary fixed-point      121 169 313
Logic, least fixed-point      170 263
Logic, monadic least fixed-point      212
Logic, monadic second-order      38 110
Logic, partial fixed-point      121 191 263 313
Logic, partial fixed-point with counting      209
Logic, positive existential fixed-point      245
Logic, second-order      37 210
Logic, simultaneous inflationary fixed-point      175
Logic, simultaneous least fixed-point      176
Logic, simultaneous partial fixed-point      192
Logic, stratified fixed-point      235
Logic, transitive closure      123 220 263
Logically equivalent      6
Logically valid      6
logspace      132
LOGSPACE and FO(DTC)      142 148 151 296 304
MAX ${\Pi}_{n}$       278
MAX ${\Sigma}_{n}$       278
MAX FO      278
MAX PB      278
MAXCLIQUE      284
MAXCUT      275 276 284
Maximization      276
MAXIMUM CONNECTED COMPONENT      285
Method, Ehrenfeucht — Frasse      21
MIN FO      278
MIN PB      278
Minimization      276
MINVERTEX      276 277
Modal logic      99
Model checker      147
Model class      10
Model theory      26
Model, minimal      34 35
Model, of a formula      6
Model, random      84
Monotone      166 175
Move      16 168 213 229
Move, $\exists -$       25
Move, $\forall -$       25
Move, in ${\rm G}_{m}^{s}({\mathcal A},\overline{a},{\mathcal B},\overline{b})$       50
Move, LFP      213
Move, negative LFP      213
Move, point      38 213 229
Move, positive LFP      213
Move, set      38
Move, TC      229
MSO      38. 212
NDA      106
NLOGSPACE      132
NLOGSPACE and FO(posTC)      143 148
NLOGSPACE and FO(TC)      143 151
NLOGSPACE=co-NLOGSPACE?      161
Noncounting      116
Nontrivial parametric      75
Normal form, for $\rm {FO}^{2}$ -sentences      96
Normal form, for FO(IFP)      138 152 189 253 255
Normal form, for FO(LFP)      174 188 254 259
Normal form, for FO(PFP)      138 152 192 194 196 197 255
Normal form, for FO(posTC)      226
Normal form, for FO(TC)      228
Normal form, prenex      7 39
NOT      4
NPSPACE      126
NPTIME      126 132 328 329
NPTIME and Sj      139 150 151 157
NPTIME optimization problem      276 280
NPTIME optimization problem, first-order definable      277
NPTIME optimization problem, polynomially bounded      277
NPTIME=co-NPTIME?      158
Number part      208
Number sort      208
Number variable      208
Numerical invariant      204
Occurrence, bound      5
Occurrence, free      5 6 37 41 172
Operation, boolean      111
Optimization problem, first-order definable      277
Optimization problem, NPTIME      276 280
Optimization problem, polynomially bounded      277
OR      4
Oracle answer state      333
Oracle configuration      331
Oracle instruction      331
Oracle machine $(\tau ,\sigma)$       330
Oracle tape      330
Oracle transducer      331
ord      88
Order-invariant in the finite      64 156 288
Ordered representation      156
Ordering      3 88
Ordering, as {<, S, min, max}-structure      3
Ordering, lexicographic      131
Ordering, minimal      219
Ordering, of even cardinality      22
OrdMod      130
Out-degree      2
Output tape      162
parametric      75
Partial isomorphism      15
Partially isomorphic      43
Path      2
Pebble      50 60
Pebble game      50 60
PFP(k,l)      263
Ph      159
Plus closure      108
Plus free regular      114
Point sort      208
Point variable      208
Point, drawn      168 172 192 198
Point, of a graph      1
Point, won      168 172 192 198
Polynomial hierarchy      159 338
Polynomial space      126 132
Polynomial space, nondeterministic      126
Polynomial time      126 132
Polynomial time, nondeterministic      126 132
Positive closure      108
pow      106
Predecessor of a vertex      2
Prenex normal form      7 39
Preservation theorem      65
Preservation, under extensions      66
Preservation, under homomorphisms      34
Preservation, under strict homomorphisms      34 35
Preservation, under substructures      65
Probability, labeled      74
Probability, labeled asymptotic      72 74 79 80 89
Probability, unlabeled      77
Probability, unlabeled asymptotic      77—80
Problem, maximization      276
Problem, minimization      276
Product of structures      3 24
Program, DATALOG      239
Program, general logic      239
Program, I-DATALOG      245
Program, P-DATALOG      248
Program, positive DATALOG      250
Program, S-DATALOG      241
Program, stratified DATALOG      241
Program, totally defined WF-DATALOG      265
Programming language      152
Projective Horn      251—253

Proof formal      8
PSPACE      126 132 150
PSPACE and FO(PFP)      137 149 151
PTAS      284
PTIME      126 132 261 314 315 325
PTIME and FO(IFP)      138 149 151 297 302
PTIME and FO(IFP, #)      305 306 315
PTIME=NPTIME?      155 290
PTIME=PSPACE?      153 154 204 206
Pumping lemma      107 111
Quantifier      309
Quantifier rank      7
Quantifier rank, for FO(M-LFP)      213
Quantifier, counting      59 309
Quantifier, existential      4 309
Quantifier, Lindstrom      309
Quantifier, simple      309
Quantifier, universal      309
Query language      12
Query, PTIME-computable      204
Random structure theory      45
Random structure, infinite      45
Rank function      185
Rank, s- of a structure      57
Reducibility many-one      320
Reducible, $\mathcal C$ -many-one      320
Reducible, $\mathcal C-$       320
Reducible, $\mathcal L-$       321
Reducible, logspace      327
Reduct      3
Refinement, stable coloured      62
Regular expression      108
Regular language      108
Reject      126
Relation      1
Relation symbol      1
Relation symbol, extensional      239
Relation symbol, intentional      239
Relation, defined in a structure      10
Relation, global      10 12
Relation, global on a class      10
Relation, nontrivial      254
Relation, transitive closure      11 24
Relativization of a complexity class      331
Represent effectively      281
Rg(p)      15
Rig      78 83
Rigid      78
Root      3
round      168
Run      125
Run, accepting      126
Run, rejecting      126
S(r,a)      26
Satisfaction relation      6
Satisfiable      6
Satisfy in a structure      6
Scattered, l-      30
Second-order logic      37
Second-order logic, monadic      38
Section      177
Sentence      5
Sentence, ${\forall}^{2}{\exists}^{*} -$       100
Sentence, ${\forall}^{2}{\exists}^{*}{\forall}^{2} -$       103
Sentence, ${\rm L}_{\infty\omega}$       41
Sentence, ${\rm L}_{{\omega}_{1}\omega}$ , positive in a relation      67
Sentence, ${\Sigma}_{1}^{1}$       110
Sentence, ${\Sigma}_{1}^{1}({\exists}^{*}{\forall}^{2})$       86 87
Sentence, ${\Sigma}_{1}^{1}({\forall}^{2}{\exists}^{*})$       86
Sentence, basic local      31
Sentence, existential positive      34
Sentence, first-order      5
Sentence, local      31
Sentence, monadic ${\Sigma}_{1}^{1}$       89
Sentence, monotone in a relation      67
Sentence, nontrivial free parametric      89
Sentence, nontrivial parametric      75 86 87
Sentence, order-invariant in the finite      64 156 288
Sentence, parametric      75
Sentence, positive in a relation      67
Sentence, universal ${\rm L}_{{\omega}_{1}\omega -}$       67
Sentence, universal Horn      251
SIMPLE      309
Simultaneous join      178
so      37
SO(PFP)      159
Space bound for oracle machines      331
Space-bounded      126
Spectrum of a sentence      46
Spoiler      16
Square      125
Stage      166 199
Stage comparison      185
Start of a Turing machine      125 131
Starting configuration      136
State      131
State(M)      125 131
State, accepting      106 125 131
State, final      106
State, initial      106 125 131
State, of a Turing machine      125
State, of an automaton      106
State, oracle answer      333
State, rejecting      125 131
State, starting      131
STR      291
String      105
Strongly PTIME-complete      325
Structure      1
Structure, $\tau -$       1
Structure, finite      13
Structure, indiscernible      222
Structure, infinite random      45 74
Structure, input      276
Structure, labeled      71
Structure, numerical      161
Structure, of vocabulary r      1
Structure, ordered      3 130
Structure, random      72
Structure, rigid      78
Structure, s-rigid      204
Structures, ${C}_{\infty\omega}^{s}$ -equivalent      61
Structures, ${\rm L}_{\infty\omega}$ -equivalent      42 44
Structures, elementarily equivalent      9
Structures, equivalent in FO(M-LFP)      214
Structures, F0S-equivalent      48 56
Structures, FO(TC)-equivalent      230
Structures, m-equivalent      14 19 21 48 52 55 57
Structures, m-equivalent in ${\rm L}_{\infty\omega}^{s}$       50
Structures, m-equivalent in FOs      50 52
Structures, m-equivalent in MSO      38
Structures, m-isomorphic      21
Structures, partially isomorphic      43 44
Structures, s-m-isomorphic      51 52
Structures, s-partially isomorphic      51 52
Successor relation k-adic      172
Successor, of a configuration      134
Successor, of a vertex      2
Sum, ordered, of m-equivalent structures      24 25
Sum, ordered, of structures      4 24 39
Support      50 83
T (truth value)      7
Tape      125
Tape, input      127 130
Tape, oracle      330
Tape, output      162
Tape, work      127 130
TC      11 24 123 220
TC, DTC      123
Term      4

1 2 3 4

О проекте