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

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

Theorem, Beth's      63
Theorem, compactness      8
Theorem, completeness      8
Theorem, Craig's      64
Theorem, Ehrenfeucht's      18
Theorem, Fraisse's      21
Theorem, Gaifman's      31
Theorem, Hanf's      27
Theorem, Loewenheim — Skolem      8
Theorem, Trahtenbrot's      8 127
Time-bounded      126
Tournament      75
Trahtenbrot's theorem      8 127
Transducer, $(\tau,\sigma)-$       162
Transducer, log space-bounded      163
Transducer, oracle      331
Transducer, polynomially time-bounded      164
Transducer, space-bounded      162
Transition relation      106
Transitive closure      24 123 220
Transitive closure logic      see “Logic transitive
Transitive closure relation      11
Transitive closure, alternating      261
Transitivity Lemma      182
Transitivity Lemma, for LFP      182
Transitivity Lemma, for PFP      195
TREE      3 170 305
Tree, labeled binary      206
Tree-width      171
TRUE      6
Turing machine      125
Turing machine, $(\tau,\sigma)-$       162
Turing machine, deterministic      125 132
Turing machine, f space-bounded      126 132
Turing machine, f time-bounded      126 132
Turing machine, for $\tau$ -structures      130
Turing machine, nondeterministic      125 132
Turing machine, with oracle tapes      330
Type, m-isomorphism      18 25 26
Type, r-ball      27
Type, s-m-isomorphism      52
Ultimately periodic      112
Undecidability, of finite satisfiability for FO      127
Undecidability, of order-invariance      288

Undecidability, of satisfiability in finite graphs      129
Undecidability, of the Halting Problem      127
Union, disjoint, of structures      4 24 39
Union, of m-equivalent structures      24
Union, of structures      4
Universal algebra      26
Universe      1
Valid, logically      6
Variable      4
Variable, free      5 6 37 41 172
Variable, predicate      37
Variable, relation      37
Vectorization, of a class      312
Vectorization, of a Lindstrom quantifier      312
Vectorization, relativized of a class      322
Vectorization, relativized of a Lindstrom quantifier      322
Vertex      1
Vertex cover      275
Virtual letter      125
Vocabulary      1
Vocabulary, containing function symbols      11
Vocabulary, function-free      11
Vocabulary, relational      1
Width of an interpretation      297 321
Win, ${G}_{m}({\mathcal A},\overline{a},{\mathcal B},\overline{b})$       18 21
Win, ${G}_{m}({\mathcal A},{\mathcal B})$       17
Win, ${G}_{m}^{s}({\mathcal A},\overline{a},{\mathcal B},\overline{b})$       52
Win, ${G}_{m}^{s}({\mathcal A},{\mathcal B})$       52
Win, ${G}_{\infty}({\mathcal A},\overline{a},{\mathcal B},\overline{b})$       42 43
Win, ${G}_{\infty}({\mathcal A},{\mathcal B})$       44
Win, ${G}_{\infty}^{s}({\mathcal A},\overline{a},{\mathcal B},\overline{b})$       52
Win, ${G}_{\infty}^{s}({\mathcal A},{\mathcal B})$       52
Win, ${\rm MSO-G}_{m}(({\mathcal A},{\overline{P}},{\overline{a}}),({\mathcal B},{\overline{Q}},{\overline{b}}))$       38
Win, a pebble game      50
Winning position      20 43 52
Winning strategy      17
Witness, negative      263
Witness, positive      263
Witness, strongly      148 153
Word      105
Word model      109 221
Word, empty      105
Work tape      127 130
{<, S, min, max}      3

1 2 3 4

О проекте