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

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

${\rm LOGSPACEK}^{\mathcal K}$       331
$(\Pi,P)\overline{t}$       246
$(\Pi,Q)\overline{t}$       249
$(\rm M){\Sigma}_{n}^{1},\;(\rm M){\Pi}_{n}^{1}$       39
$EVEN[\tau]$       21 37 41 53 59 72 156
$FO(IFP)\;\equiv\;I-DATALOG$       246
$FO(IFP)\;\equiv\;SO$       155
$FO[\tau]$       5
$IMP(FO)\;\le\;{\Delta}_{1}^{1}$       219
$K{\le}_{\mathcal L}L,\;K{\le}_{\mathcal L}^{k}L$       321
$l(K),\;{l}_{n}(\varphi),\;{l}(\varphi)$       72
$p\subseteq q,\;\overline{a}\mapsto\overline{b}$       15
$r({\mathcal A})$       57
$supp(\iverline{a})$       50
$[{\rm GFP}_{\overline{x},X}\;{\varphi}(\overline{x},X)]\overline{x}$       172
$[{\rm IFP}_{\overline{x},X\varphi}]$       169
$\ rm FO({\rm BER}_{r})$       236
$\bigvee{\Psi}$       40
$\bigwedge{\Phi},\;\bigvee{\Phi}$       7
$\bigwedge{\Psi}$       41
$\exists (\forall )x\psi (x)$       179
$\lambda$       105
$\overline{x},\;{\varphi}(\overline{x})$       6
$\rm FO(DTC)(rel-\omega-{\bf Q}_{{HAM}_{<}})$       334
$\rm FO(DTC)[rel-\omega-{\bf Q}_{{HAM}_{<}}]$       328
$\rm FO(DTC)\;\lefteqn{/}{\equiv}\;FO(TC)$       223
$\rm FO(DTC)\;\le\;FO({IFP}^{2})$       273
$\rm FO(DTC)\;\le\;FO({LFP}^{2})$       271
$\rm FO(DTC)\;\le\;FO({LFP}^{3})$       270
$\rm FO(DTC)\;\le\;FO({PFP}^{1})$       271
$\rm FO(DTC)\;\le\;FO({PFP}^{2})$       269
$\rm FO(IFP)\;\equiv\;FO(S-IFP)$       179
$\rm FO(IFP)\;\equiv\;{\Sigma}_{1}^{1}$       155
$\rm FO(IFP, \#)\;\equiv\;DATALOG(\#)$       248
$\rm FO(IFP, \#)\;\equiv\;FO({PFP}_{PTIME}, \#)$       210
$\rm FO(LFP) < {\rm L}_{\infty\omega}^{\omega}\;\cap\;PTIME$       206
$\rm FO(LFP)\;\equiv\;E(LFP)$       244
$\rm FO(LFP)\;\equiv\;FO(ATC)$       261
$\rm FO(LFP)\;\equiv\;FO(IFP)$       173
$\rm FO(LFP)\;\equiv\;FO(PFP)$       203 204
$\rm FO(LFP)\;\equiv\;FO(S-LFP)$       179
$\rm FO(LFP)\;\equiv\;FO({PFP}_{PTIME})$       205 206
$\rm FO(LFP)\;\equiv\;WF-DATALOG$       265
$\rm FO(LFP)\;\le\;IMP(FO)$       219
$\rm FO(LFP)\;\le\;{\Delta}_{1}^{1}$       212
$\rm FO(PFP)\;\equiv\;P-DATALOG$       249
$\rm FO(PFP)\;\le\;{\rm L}_{\infty\omega}^{\omega}$       199
$\rm FO(posDTC)\;\equiv\;FO(DTC)$       224
$\rm FO(posTC)\;\equiv\;FO(TC)$       226
$\rm FO(TC)\;\equiv\;{S-DATALOG}_{1}$       243
$\rm FO({DTC}^{r})$       268
$\rm FO({IFP}^{r})$       268
$\rm FO({LFP}^{1})\;<\;FO({IFP}^{1}$       273
$\rm FO({LFP}^{r})$       268
$\rm FO({PFP},\#)$       209
$\rm FO({PFP},\#)\;\le\;{\rm C}_{\infty\omega}^{\omega}$       209
$\rm FO({PFP}^{r})$       268
$\rm FO({PFP}_{PTIME})$       205
$\rm FO({PFP}_{PTIME},\#)$       210
$\rm FO({TC}^{1})\;\equiv\;MSO$       221
$\rm FO({TC}^{r})$       221 268
$\rm free(\varphi)$       5
$\rm IMP(FO(PFP))\;{\lefteqn{\le}{\;/}}\;{\rm L}_{\infty\omega}^{\omega}$       219
$\rm IMP({\mathcal L})$       218
$\rm Mod(\Phi)$       14
$\rm Mod(\varphi)$       10
$\rm Paxt({\mathcal A},{\mathcal B})$       15
$\rm S-DATALOG\;\equiv\;{\rm S-DATALOG}_{2}$       243
$\rm SO\;\le\;FO(PFP)$       211
$\rm SPACE({n}^{e})$       272
$\rm Str[\tau]$       158
$\rm {LOGSPACE}^{NPTIME}$       332 334
$\rm {LOGSPACE}^{NPTIME}\;=\;{LOGSPACE}^{{HAM}_{<}}$       332
$\rm {LOGSPACE}^{NPTIME}\;=\;{LOGSPACE}^{{HENK}_{<}}$       332
$\rm {LOGSPACE}^{O}$       334
$\rm {opt}_{\mathcal Q}$       276
$\rm {\rm G}_{m}({\mathcal A},{\mathcal B})$       38
$\tau$ -structure      1
$\varphi({{Y}_{-}}{\overline{y}})$       179
${( \tau,\Pi )}_{int},\;{( \tau,\Pi )}_{ext}$       239
${DATALOG}_{r}, S-$       242
${F}_{(\infty )}^{i}$       174
${F}_{n},\;{F}_{\infty},\;{F}^{\varphi}$       120
${G}_{m}({\mathcal A},\overline{a},{\mathcal B},\overline{b})$       16
${G}_{m}({\mathcal A},{\mathcal B})$       17
${G}_{m}^{s}({\mathcal A},\overline{a},{\mathcal B},\overline{b}),\;{G}_{\infty}^{s}({\mathcal A},\overline{a},{\mathcal B},\overline{b})$       50
${G}_{m}^{s}({\mathcal A},{\mathcal B}),\;{G}_{\infty}^{s}({\mathcal A},{\mathcal B})$       50
${G}_{\infty}({\mathcal A},\overline{a},{\mathcal B},\overline{b})$       42
${K}^{k}$       312
${K}_{<}$       64
${L}^{+}$       108
${L}_{n}(K),\;{L}_{n}(\varphi),\;{L}_{n}(\tau),\;{l}_{n}(K)$       71
${l}_{n}(K|H),\;{l}(K|H)$       74
${MAX}_{e}\;{\Sigma}_{1}$       281
${MAX}_{e}\;{\Sigma}_{1}\;\subseteq\;APX$       281
${PTIME}^{\mathcal O}$       334
${P}_{(n)}^{i},\;{P}_{(\infty)}^{i}$       240
${Q}\overline{x}{\psi}(\overline{x})$       309
${Q}_{K}{{\overline{x}}_{1},...,{\overline{x}}_{s}}[{\psi}_{1}({\overline{x}}_{1}),...,{\psi}_{s}({\overline{x}}_{s})]$       308
${Q}_{rel-k-L},\;rel-\omega -{\bf Q}_{L}$       322
${R}^{A}{a}_{1}...{a}_{n}$       1
${R}^{\mathcal A},\;{c}^{\mathcal A},\;{R}^{A},\;{c}^{A}$       1
${s}_{0},\;{s}_{+}.\;{s}_{-}$       125 133
${T}_{rand}({\varphi}_{0})$       76 84
${T}_{\rm rand}$       45 73
${T}_{\rm rand}({\varphi}_{0})$       76
      78
${U}_{n}(K),\;{u}_{n}(K),\;u(K)$       77
${u}_{n}(K|H)$       77
${W}_{m}({\mathcal A},{\mathcal B})$       20
${W}_{m}^{s}({\mathcal A},{\mathcal B}),\;{W}_{\infty}^{s}({\mathcal A},{\mathcal B})$       52
${W}_{\infty}({\mathcal A},{\mathcal B})$       43
${\#}_{x \varphi}$       208
${\bf Q}_{K}^{\omega}$       312
${\delta}_{i}^{l}({x}_{1},...,{x}_{l},v,\omega)$       179
${\Delta}_{n}^{1}$       40
${\exists}^{= n},\;{\exists}^{\le n}$       8
${\exists}^{\ge t}$       59
${\exists}^{\geqslant n}$       7
${\gamma}\leftarrow{\gamma}_{1},...,{\gamma}_{l}$       239
${\mathbb A},\;{\mathbb A}^{*},\;{\mathbb A}^{+}$       105
${\mathcal AB}$       336
${\mathcal A}/s$       54
${\mathcal A}[\Pi],\;(\Pi,P)\overline{t}$       240
${\mathcal A}[\Sigma],\;(\Sigma,P)\overline{t}$       241
${\mathcal A}\cong{\mathcal B}$       3
${\mathcal A}\cup{\mathcal B},\;{\mathcal A}\triangleleft{\mathcal B}$       4
${\mathcal A}\equiv{\mathcal B}$       9
${\mathcal A}\models{\varphi}[{a}_{1},...,{a}_{n}],\;{\mathcal A}\models{\varphi}$       6
${\mathcal A}\times{\mathcal B}$       3
${\mathcal A}^{I},\;{\dot{\cup}}_{I}{\mathcal A},\;{\triangleleft}_{I}{\mathcal A}$       4
${\mathcal A}^{\Pi},\;{\psi}^{- \Pi}$       297
${\mathcal A}{\cong}^{s}{\mathcal B},\;{\mathcal A}{\cong}^{{\rm L}_{\infty\omega}^{s}}{\mathcal B},\;{\mathcal A}{\cong}^{s}_{m}{\mathcal B}$       48
${\mathcal A}{\cong}^{\rm M}_{m}{\mathcal B}$       213
${\mathcal A}{\cong}^{{\rm L}_{\infty\omega}}{\mathcal B}$       42
${\mathcal A}{\cong}_{m}^{s}{\mathcal B},\;{({I}_{j})}_{j \le m}:\;{\mathcal A}{\cong}_{m}^{s}{\mathcal B}$       51
${\mathcal A}{\cong}_{m}^{\rm MSO}{\mathcal B}$       38
${\mathcal A}{\cong}_{m}{\mathcal B},\;{({I}_{j})}_{j \le m}:\;{\mathcal A}{\cong}_{m}{\mathcal B}$       20
${\mathcal A}{\cong}_{\rm part}{\mathcal B},\;I:\;{\mathcal A}{\cong}_{\rm part}{\mathcal B}$       43
${\mathcal A}{\equiv}^{\rm M}_{m}{\mathcal B}$       217
${\mathcal A}{\equiv}_{m}{\mathcal B}$       14
${\mathcal A}|{\tau}$       3
${\mathcal B}_{l},\;{\mathcal D}_{l}$       24
${\mathcal B}_{u}$       109
${\mathcal C}^{\mathcal K},\;{\mathcal C}^{L}$       331
${\mathcal G}_{l}$       23
${\mathcal L}({Q}_{k}), {\mathcal L}({\bf Q})$       309
${\mathcal L}[{\bf Q}]$       323
${\mathcal L}[{\tau}]$       122
${\mathcal L}_{1}\le{\mathcal L}_{2},\;{\mathcal L}_{1}\equiv{\mathcal L}_{2},\;{\mathcal L}_{1}{<}{\mathcal L}_{2}$       122

${\mathcal L}{[\tau]}_{0},\;{\models}^{{\mathcal L},\tau}$       289
${\mathcal L}{\equiv}_{\rm es}{\mathcal C}$       290
${\mathcal L}{\equiv}_{\rm es}{\mathcal C}\;{\rm on}\;S$       296
${\mathcal O}[{\sigma}]$       3
${\neg},\;{\vee},\;{\exists}$       4
${\overline{a}}^{a}_{\overline{i}}$       50
${\Phi}\models{\psi},\;\models{\psi}$       6
${\Phi}{\models}_{fin}{\psi},\;{\models}_{fin}{\psi}$       7
${\psi}^{j}_{\overline{a},\overline{P}}$       38
${\psi}_{\overline{a}}^{m},\;{\psi}_{{\mathcal A},\overline{a}}^{m},\;{\psi}_{{\mathcal A}}^{m}$       52
${\rm C - G}^{s}_{m}({\mathcal A},\overline{a},{\mathcal B},\overline{b}),\;{\rm C - G}^{s}_{\infty}({\mathcal A},\overline{a},{\mathcal B},\overline{b})$       60
${\rm co}-{\mathcal C}$       155
${\rm FO(BFP)}\;\equiv\;{\rm S-DATALOG}$       242
${\rm FO(C)},\;{\rm L}_{\infty\omega}({\rm C}),\;{\rm C}_{\infty\omega}$       59
${\rm FO(C)}^{c},\;{\rm C}_{\infty\omega}^{s},\;{\rm C}_{\infty\omega}^{\omega}$       59
${\rm FO(C)}^{s}$       59
${\rm FO}\;\equiv\;{\ rm S-DATALOG}_{0}$       243
${\rm FO}^{s}$       47
${\rm L}_{\infty\omega},\;{\rm L}_{{\omega}_{1}{\omega}}$       40
${\rm L}_{\infty\omega}^{s},\;{\rm L}_{\infty\omega}^{\omega}$       47
${\rm L}_{\infty\omega}^{\omega}({\bf Q})$       314
${\rm MLFP-G}_{m}({\mathcal A},{\mathcal B})$       213
${\rm MSO}-{\rm G}_{m}({\mathcal A},{\mathcal B})$       38
${\rm NDA},\;{\tilde{\delta}},\;{L}(M)$       106
${\rm qr}(\varphi)$       7
${\rm Str}[\tau]$       158
${\rm TC-G}_{m}^{r}({\mathcal A},{\mathcal B})$       229
${\rm{IT}}^{m}({\mathcal A},\overline{a})$       26
${\Sigma}_{1}^{1}$ and NPTIME      139 150 151 157
${\Sigma}_{1}^{1}({\forall}^{*}{\exists}^{*}),\;{\Sigma}_{1}^{1}({\exists}^{*}{\forall}^{*})$       86
${\Sigma}_{n},\;{\Pi}_{n},\;{\Delta}_{n}$       7
${\tau},\;{\sigma}$       1
${\tau}_{0}$       3
${\tau}_{<},\;{K}_{<}$       156
${\tau}_{int},\;{\tau}_{ext}$       239
${\varphi}({x}_{1},...,{x}_{n})$       6
${\varphi}\frac{{t}_{1}...{t}_{n}}{{x}_{1}...{x}_{n}},\;{\varphi}({t}_{1},...,{t}_{n})$       7
${\varphi}^{\mathcal A}(\_)$       10
${\varphi}_{\ge n},\;{\varphi}_{= n},\;{\varphi}_{\le n}$       8
${\varphi}_{{\mathcal A},\overline{a}}^{m},\;{\varphi}_{{\mathcal A}}^{m},\;{\varphi}_{\overline{a}}^{m}(\overline{v})$       18
${\wedge},\;{\rightarrow},\;{\leftrightarrow},\;{\forall}$       5
${{\rm rel}-L},\;{\rm rel}-k-L$       322
${|j|}_{r},\;{|j|}^{n}_{r}$       131
      107
      4
(M,f)      290
(M,O)      331
ACCEPT      126 132
Acceptable      126
Acceptor      162
Almost all      72
Alphabet      105
Antitone      167 172 192
Approximable      280
APX      281
Arity      1
Arity hierarchy      268 272 273
Arity, of a quantifier      309
ASSIGNMENT      6
ATC      261
Automaton      106
Automaton, deterministic      106
Automaton, nondeterministic      106
Axiomatizable, in ${\rm FO(DTC)}({\rm rel}-\omega-{\bf Q}_{O})$       333 334
Axiomatizable, in ${\rm FO(IFP)}({\rm rel}-\omega-{\bf Q}_{O})$       333 334
Axiomatizable, in ${\rm FO}^{s}$       54
Axiomatizable, in ${\rm L}_{{\infty}{\omega}}^{s}$       53
Axiomatizable, in ${\rm L}_{{\infty}{\omega}}^{\omega}$       53
Axiomatizable, in ${\rm L}_{{\omega}_{1}{\omega}}$       41
Axiomatizable, in a logic      124
Axiomatizable, in FO      14 20 150 252
Axiomatizable, in FO(M-LFP)      217
Axiomatizable, in SO      150
Back property      20
Back property, s-      51
Ball      26
Ball, r-      26
Base of an instruction      132
Basic term      248
Beth property      63
Beth's theorem      63
Blank letter      125 130
Body of a clause      239
Bounded      57 58
Bounded, fixed-point      204
Bounded, s-      57
Breadth, of a DATALOG program      242
Breadth, of an S-DATALOG program      242
Canonization, $\mathcal C$       294
Canonization, $\mathcal C$ on S      301
Canonization, LOGSPACE-      294
Canonization, PSPACE-      294
Canonization, PTIME-      291—293
Capture      157
Capture, a complexity class      151 288
Capture, effectively strongly      290 295 325
Capture, effectively strongly on S      296
Capture, PTIME effectively strongly      290 292 294 300
Capture, PTIME effectively strongly on GRAPH      300
Capture, strongly      157 288
Cardinality      4
cell      125
Cell, virtual      125 130
Circuit, Hamiltonian      2 113 327
Class, bounded      57
Class, elementary      14
Class, elementary relative to      14
Class, finitely axiomatizable      14
Class, fixed-point bounded      204
Class, free parametric      80
Class, indiscernible      222
Class, nontrivial free parametric      80
Class, nontrivial parametric      77
Class, of finite structures      14
Class, of structures      10
Class, parametric      75
Class, s-bounded      57
Class, s-rigid      204
Clause      239
CLIQUE      2 113
Closed subset      222
Closed under isomorphisms      10
Closure, alternating transitive      261
Closure, deterministic transitive      123 220
Closure, plus      108
Closure, positive      108
Closure, transitive      123 220
Co-NPTIME      157
Colour type      61
Compactness Theorem      8
Compatible      76
Complement of a complexity class      155
Complete, NPTIME- with respect to FO(DTC) reductions      328
Complete, NPTIME- with respect to logspace reductions      327 328
Complete, strongly PTIME- with respect to FO-reductions      325
Complete, with respect to $\mathcal C$ -reductions      321
Complete, with respect to $\mathcal L$ -reductions      324
Completeness theorem      8
Complexity class, as a class of ordered structures      153
Complexity class, in complexity theory      153
Component, connected      2 30
Component, of a graph      2
Computable, PTIME-      204 291
Concatenation of languages      107
Configuration      128 134
Configuration, accepting      134
Configuration, oracle      331
Configuration, starting      136
Conn      2 23 122
Connected component      30

1 2 3 4

О проекте