Muutke küpsiste eelistusi

E-raamat: Bounded Variable Logics and Counting: A Study in Finite Models

4.00/5 (1 hinnangut Goodreads-ist)
(Rheinisch-Westfälische Technische Hochschule, Aachen, Germany)
  • Formaat: PDF+DRM
  • Sari: Lecture Notes in Logic
  • Ilmumisaeg: 02-Mar-2017
  • Kirjastus: Cambridge University Press
  • Keel: eng
  • ISBN-13: 9781316731550
Teised raamatud teemal:
  • Formaat - PDF+DRM
  • Hind: 137,07 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Lisa ostukorvi
  • Lisa soovinimekirja
  • See e-raamat on mõeldud ainult isiklikuks kasutamiseks. E-raamatuid ei saa tagastada.
Bounded Variable Logics and Counting: A Study in Finite ModelsSuurem pilt
  • Formaat: PDF+DRM
  • Sari: Lecture Notes in Logic
  • Ilmumisaeg: 02-Mar-2017
  • Kirjastus: Cambridge University Press
  • Keel: eng
  • ISBN-13: 9781316731550
Teised raamatud teemal:

DRM piirangud

  • Kopeerimine (copy/paste):

    ei ole lubatud

  • Printimine:

    ei ole lubatud

  • Kasutamine:

    Digitaalõiguste kaitse (DRM)
    Kirjastus on väljastanud selle e-raamatu krüpteeritud kujul, mis tähendab, et selle lugemiseks peate installeerima spetsiaalse tarkvara. Samuti peate looma endale  Adobe ID Rohkem infot siin. E-raamatut saab lugeda 1 kasutaja ning alla laadida kuni 6'de seadmesse (kõik autoriseeritud sama Adobe ID-ga).

    Vajalik tarkvara
    Mobiilsetes seadmetes (telefon või tahvelarvuti) lugemiseks peate installeerima selle tasuta rakenduse: PocketBook Reader (iOS / Android)

    PC või Mac seadmes lugemiseks peate installima Adobe Digital Editionsi (Seeon tasuta rakendus spetsiaalselt e-raamatute lugemiseks. Seda ei tohi segamini ajada Adober Reader'iga, mis tõenäoliselt on juba teie arvutisse installeeritud )

    Seda e-raamatut ei saa lugeda Amazon Kindle's. 

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.

Muu info

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.
Lisainfo e-raamatute kohta Lisainfo e-raamatute kohta
Püsilink: https://www.kriso.ee/db/97813167315502e.html