Atjaunināt sīkdatņu piekrišanu

E-grāmata: Bounded Variable Logics and Counting: A Study in Finite Models

4.00/5 (1 ratings by Goodreads)
(Rheinisch-Westfälische Technische Hochschule, Aachen, Germany)
  • Formāts: PDF+DRM
  • Sērija : Lecture Notes in Logic
  • Izdošanas datums: 02-Mar-2017
  • Izdevniecība: Cambridge University Press
  • Valoda: eng
  • ISBN-13: 9781316731550
Citas grāmatas par šo tēmu:
  • Formāts - PDF+DRM
  • Cena: 132,04 €*
  • * ši ir gala cena, t.i., netiek piemērotas nekādas papildus atlaides
  • Ielikt grozā
  • Pievienot vēlmju sarakstam
  • Šī e-grāmata paredzēta tikai personīgai lietošanai. E-grāmatas nav iespējams atgriezt un nauda par iegādātajām e-grāmatām netiek atmaksāta.
Bounded Variable Logics and Counting: A Study in Finite ModelsPalielināt
  • Formāts: PDF+DRM
  • Sērija : Lecture Notes in Logic
  • Izdošanas datums: 02-Mar-2017
  • Izdevniecība: Cambridge University Press
  • Valoda: eng
  • ISBN-13: 9781316731550
Citas grāmatas par šo tēmu:

DRM restrictions

  • Kopēšana (kopēt/ievietot):

    nav atļauts

  • Drukāšana:

    nav atļauts

  • Lietošana:

    Digitālo tiesību pārvaldība (Digital Rights Management (DRM))
    Izdevējs ir piegādājis šo grāmatu šifrētā veidā, kas nozīmē, ka jums ir jāinstalē bezmaksas programmatūra, lai to atbloķētu un lasītu. Lai lasītu šo e-grāmatu, jums ir jāizveido Adobe ID. Vairāk informācijas šeit. E-grāmatu var lasīt un lejupielādēt līdz 6 ierīcēm (vienam lietotājam ar vienu un to pašu Adobe ID).

    Nepieciešamā programmatūra
    Lai lasītu šo e-grāmatu mobilajā ierīcē (tālrunī vai planšetdatorā), jums būs jāinstalē šī bezmaksas lietotne: PocketBook Reader (iOS / Android)

    Lai lejupielādētu un lasītu šo e-grāmatu datorā vai Mac datorā, jums ir nepieciešamid Adobe Digital Editions (šī ir bezmaksas lietotne, kas īpaši izstrādāta e-grāmatām. Tā nav tas pats, kas Adobe Reader, kas, iespējams, jau ir jūsu datorā.)

    Jūs nevarat lasīt šo e-grāmatu, izmantojot Amazon Kindle.

Since their inception, the Perspectives in Logic and Lecture Notes in Logic series have published seminal works by leading logicians. Many of the original books in the series have been unavailable for years, but they are now in print once again. In this volume, the ninth publication in the Lecture Notes in Logic series, Martin Otto gives an introduction to finite model theory that indicates the main ideas and lines of inquiry that motivate research in this area. Particular attention is paid to bounded variable infinitary logics, with and without counting quantifiers, related fixed-point logics, and the corresponding fragments of Ptime. The relations with Ptime exhibit the fruitful exchange between ideas from logic and from complexity theory that is characteristic of finite model theory.

Papildus informācija

This study introduces some central ideas and lines of research in finite model theory, particularly bounded variable infinitary logics.
Preface v
0 Introduction
1(14)
0.1 Finite Models, Logic and Complexity
1(6)
0.1.1 Logics for Complexity Classes
1(3)
0.1.2 Semantically Defined Classes
4(3)
0.1.3 Which Logics Are Natural?
7(1)
0.2 Natural Levels of Expressiveness
7(5)
0.2.1 Fixed-Point Logics and Their Counting Extensions
8(1)
0.2.2 The Framework of Infinitary Logic
9(2)
0.2.3 The Role of Order and Canonization
11(1)
0.3 Guide to the Exposition
12(3)
1 Definitions and Preliminaries
15(36)
1.1 Structures and Types
15(6)
1.1.1 Structures
15(2)
1.1.2 Queries and Global Relations
17(1)
1.1.3 Logics
18(1)
1.1.4 Types
19(2)
1.2 Algorithms on Structures
21(3)
1.2.1 Complexity Classes and Presentations
22(1)
1.2.2 Logics for Complexity Classes
23(1)
1.3 Some Particular Logics
24(11)
1.3.1 First-Order Logic and Infinitary Logic
24(1)
1.3.2 Fragments of Infinitary Logic
25(5)
1.3.3 Fixed-Point Logics
30(3)
1.3.4 Fixed-Point Logics and the L
33(2)
1.4 Types and Definability in the L and C
35(3)
1.5 Interpretations
38(5)
1.5.1 Variants of Interpretations
38(2)
1.5.2 Examples
40(1)
1.5.3 Interpretations and Definability
41(2)
1.6 Lindstrom Quantifiers and Extensions
43(4)
1.6.1 Cardinality Lindstrom Quantifiers
43(1)
1.6.2 Aside on Uniform Families of Quantifiers
44(3)
1.7 Miscellaneous
47(4)
1.7.1 Canonization and Invariants
47(2)
1.7.2 Orderings and Pre-Orderings
49(1)
1.7.3 Lexicographic Orderings
49(2)
2 The Games and Their Analysis
51(28)
2.1 The Pebble Games for L and C
51(16)
2.1.1 Examples and Applications
54(6)
2.1.2 Proof of Theorem 2.2
60(2)
2.1.3 Further Analysis of the Ck-Game
62(4)
2.1.4 The Analogous Treatment for Lk
66(1)
2.2 Colour Refinement and the Stable Colouring
67(6)
2.2.1 The Standard Case: Colourings of Finite Graphs
67(1)
2.2.2 Definability of the Stable Colouring
68(3)
2.2.3 C2 and the Stable Colouring
71(1)
2.2.4 A Variant Without Counting
72(1)
2.3 Order in the Analysis of the Games
73(6)
2.3.1 The Internal View
74(2)
2.3.2 The External View
76(1)
2.3.3 The Analogous Treatment for Lk
77(2)
3 The Invariants
79(18)
3.1 Complete Invariants for Lk and Ck
80(1)
3.2 The Ck-Invariants
81(4)
3.3 The Lk-Invariants
85(2)
3.4 Some Applications
87(6)
3.4.1 Fixed-Points and the Invariants
87(3)
3.4.2 The Abiteboul-Vianu Theorem
90(1)
3.4.3 Comparison of IC and IL
91(2)
3.5 A Partial Reduction to Two Variables
93(4)
4 Fixed-Point Logic with Counting
97(18)
4.1 Definition of FP+C and PFP+C
98(8)
4.2 FP+C and the Ck-Invariants
106(3)
4.3 The Separation from PTIME
109(2)
4.4 Other Characterizations of FP+C
111(4)
5 Related Lindstrom Extensions
115(16)
5.1 A Structural Padding Technique
117(7)
5.2 Cardinality Lindstrom Quantifiers
124(4)
5.2.1 Proof of Theorem 5.1
125(3)
5.3 Aside on Further Applications
128(3)
6 Canonization Problems
131(18)
6.1 Canonization
131(3)
6.2 PTIME Canonization and Fragments of PTIME
134(2)
6.3 Canonization and Inversion of the Invariants
136(3)
6.4 A Reduction to Three Variables
139(10)
6.4.1 The Proof of Theorems 6.16 and 6.17
141(6)
6.4.2 Remarks on Further Reduction
147(2)
7 Canonization for Two Variables
149(28)
7.1 Game Tableaux and the Inversion Problem
150(10)
7.1.1 Modularity of Realizations
156(4)
7.2 Realizations for IC2
160(9)
7.2.1 Necessary Conditions
160(2)
7.2.2 Realizations of the Off-Diagonal Boxes
162(1)
7.2.3 Magic Squares
163(3)
7.2.4 Realizations of the Diagonal Boxes
166(3)
7.3 Realizations for IL2
169(8)
7.3.1 Necessary and Sufficient Conditions
169(5)
7.3.2 On the Special Nature of Two Variables
174(3)
Bibliography 177(4)
Index 181
Martin Otto works in the Department of Mathematics at Rheinisch-Westfälische Technische Hochschule, Aachen, Germany.
Biežāk uzdotie jautājumi par e-grāmatām Biežāk uzdotie jautājumi par e-grāmatām
Permanent link: https://www.kriso.lv/db/97813167315502e.html