+612 9045 4394
Finite Model Theory and Its Applications : Texts in Theoretical Computer Science. an Eatcs - Erich Gradel

Finite Model Theory and Its Applications

Texts in Theoretical Computer Science. an Eatcs

Hardcover Published: 1st June 2007
ISBN: 9783540004288
Number Of Pages: 437

Share This Book:


or 4 easy payments of $36.74 with Learn more
Ships in 5 to 9 business days

Other Available Editions (Hide)

  • Paperback View Product Published: 30th October 2014
    Ships in 5 to 9 business days

Finite model theory, as understoodhere, is an areaof mathematicallogic that has developed in close connection with applications to computer science, in particular the theory of computational complexity and database theory. One of the fundamental insights of mathematical logic is that our understanding of mathematical phenomena is enriched by elevating the languages we use to describe mathematical structures to objects of explicit study. If mathematics is the science of patterns, then the media through which we discern patterns, as well as the structures in which we discern them, command our attention. It isthis aspect oflogicwhichis mostprominentin model theory,"thebranchof mathematical logic which deals with the relation between a formal language and its interpretations." No wonder, then, that mathematical logic, and ?nite model theory in particular, should ?nd manifold applications in computer science: from specifying programs to querying databases, computer science is rife with phenomena whose understanding requires close attention to the interaction between language and structure. This volume gives a broadoverviewof some central themes of ?nite model theory: expressive power, descriptive complexity, and zero-one laws, together with selected applications to database theory and arti?cial intelligence, es- cially constraint databases and constraint satisfaction problems. The ?nal chapter provides a concise modern introduction to modal logic, which emp- sizes the continuity in spirit and technique with ?nite model theory.

Industry Reviews

From the reviews:

"This book has its origins in a workshop held in Philadelphia in 1999 ... . The chapters are of an expository nature, each one providing an excellent starting point to explore the research literature in the relevant topic. ... I found it to be a more accessible introduction to the subject ... and a useful starting point for graduate students entering the subject. ... This will appeal ... to those readers trained in classical traditions of logic who wish to approach the subject." (Anuj Dawar, Mathematical Reviews, Issue 2009 i)

Unifying Themes in Finite Model Theoryp. 1
Definability Theoryp. 2
Classification of Concepts in Terms of Definitional Complexityp. 2
What More Do We Know When We Know a Concept Is L-Definable?p. 4
Logics with Finitely Many Variablesp. 7
Distinguishing Structures: L-Equivalence and Comparison Gamesp. 8
Random Graphs and 0-1 Lawsp. 10
Constraint Satisfaction Problemsp. 11
Descriptive Complexityp. 12
Satisfactionp. 13
What Is a Logic for PTIME?p. 16
Finite Model Theory and Infinite Structuresp. 18
Tame Fragments and Tame Classesp. 20
Referencesp. 22
On the Expressive Power of Logics on Finite Modelsp. 27
Introductionp. 27
Basic Conceptsp. 28
Ehrenfeucht-Fraisse Games for First-Order Logicp. 34
Computational Complexityp. 50
Complexity Classesp. 50
The Complexity of Logicp. 51
Ehrenfeucht-Fraisse Games for Existential Second-Order Logicp. 54
Logics with Fixed-Point Operatorsp. 59
Operators and Fixed Pointsp. 60
Least Fixed-Point Logicp. 64
Datalog and Datalog([NotEqual])p. 74
The Complementation Problem for LFP[subscript 1] and a Normal Form for LFPp. 79
Partial Fixed-Point Logicp. 82
Infinitary Logics with Finitely Many Variablesp. 86
The Infinitary Logic L[Characters not reproducible]p. 87
Pebble Games and L[Characters not reproducible]-Definabilityp. 89
0-1 Laws for L[Characters not reproducible]p. 97
Definability and Complexity of L[Characters not reproducible]-Equivalencep. 99
Least Fixed-Point Logic vs. Partial Fixed-Point Logic on Finite Structuresp. 104
Existential Infinitary Logics with Finitely Many Variablesp. 106
The Infinitary Logics [Characters not reproducible] and [Characters not reproducible] ([NotEqual])p. 107
Existential Pebble Gamesp. 109
Descriptive Complexity of Fixed Subgraph Homeomorphism Queriesp. 116
Referencesp. 119
Finite Model Theory and Descriptive Complexityp. 125
Definability and Complexityp. 125
Complexity Issues in Logicp. 126
Model Checking for First-Order Logicp. 128
The Strategy Problem for Finite Gamesp. 129
Complexity of First-Order Model Checkingp. 132
Encoding Finite Structures by Wordsp. 135
Capturing Complexity Classesp. 138
Capturing NP: Fagin's Theoremp. 138
Logics That Capture Complexity Classesp. 144
Capturing Polynomial Time on Ordered Structuresp. 145
Capturing Logarithmic Space Complexityp. 149
Transitive Closure Logicsp. 151
Fixed-Point Logicsp. 152
Some Fixed-Point Theoryp. 153
Least Fixed-Point Logicp. 155
The Modal [mu]-Calculusp. 157
Parity Gamesp. 160
Model-Checking Games for Least Fixed-Point Logicp. 165
Definability of Winning Regions in Parity Gamesp. 169
Simultaneous Fixed-Point Inductionsp. 170
Inflationary Fixed-Point Logicp. 174
Partial Fixed-Point Logicp. 177
Datalog and Stratified Datalogp. 180
Logics with Countingp. 186
Logics with Counting Termsp. 187
Fixed-Point Logic with Countingp. 188
Datalog with Countingp. 190
Capturing PTIME via Canonizationp. 193
Definable Linear Ordersp. 193
Canonizations and Interpretationsp. 194
Capturing PTIME up to Bisimulationp. 198
Is There a Logic for PTIME?p. 203
Algorithmic Model Theoryp. 205
Beyond Finite Structuresp. 205
Finitely Presentable Structuresp. 206
Metafinite Structuresp. 210
Metafinite Spectrap. 213
Descriptive Complexity over the Real Numbersp. 216
Appendix: Alternating Complexity Classesp. 222
Referencesp. 225
Logic and Random Structuresp. 231
An Instructive Examplep. 231
Random Graphsp. 234
Extension Statementsp. 235
Closurep. 237
The Almost Sure Theoryp. 239
The Case p Constantp. 241
Countable Modelsp. 242
A Dynamic Viewp. 243
Infinite Spectra via Almost Sure Encodingp. 244
The Jump Conditionp. 246
The Complexity Conditionp. 247
Nonconvergence via Almost Sure Encodingp. 249
No Almost Sure Representation of Evennessp. 251
The Ehrenfeucht Gamep. 253
About the Referencesp. 254
Referencesp. 255
Embedded Finite Models and Constraint Databasesp. 257
Introductionp. 257
Organizationp. 258
Relational Databases and Embedded Finite Modelsp. 258
Constraint Databasesp. 262
Collapse and Genericity: An Overviewp. 266
Approaches to Proving Expressivity Boundsp. 267
Active-Generic Collapsep. 269
The Ramsey Propertyp. 269
Collapse Resultsp. 272
Natural-Active Collapsep. 273
Collapse: Failure and Successp. 274
Good Structures vs. Bad Structures: O-minimalityp. 276
Collapse Theorem and Corollariesp. 277
Collapse Algorithm: the Linear Casep. 278
Collapse Algorithm: the General Casep. 280
Collapse Without O-minimalityp. 285
Natural-Generic Collapsep. 287
Model Theory and Collapse Resultsp. 288
Pseudo-finite Homogeneityp. 289
Finite Cover Property and Collapsep. 290
Isolation and Collapsep. 292
The VC Dimension and Collapse Resultsp. 295
Random Graph and Collapse to MSOp. 298
Complexity Bounds for Generic Queriesp. 299
Expressiveness of Constraint Query Languagesp. 301
Reductions to the Finite Casep. 301
Topological Propertiesp. 303
Linear vs. Polynomial Constraintsp. 305
Query Safetyp. 307
Finite and Infinite Query Safetyp. 308
Safe Translationsp. 309
Finite Query Safety: Characterizationp. 311
Infinite Query Safety: Reductionp. 316
Deciding Safetyp. 319
Dichotomy Theorem for Embedded Finite Modelsp. 321
Database Considerationsp. 322
Aggregate Operatorsp. 323
Higher-Order Featuresp. 326
Bibliographic Notesp. 330
Referencesp. 334
A Logical Approach to Constraint Satisfactionp. 339
Introductionp. 339
Preliminariesp. 340
The Computational Complexity of Constraint Satisfactionp. 344
Nonuniform Constraint Satisfactionp. 347
Monotone Monadic SNP and Nonuniform Constraint Satisfactionp. 350
Datalog and Nonuniform Constraint Satisfactionp. 352
Datalog, Games, and Constraint Satisfactionp. 355
Games and Consistencyp. 357
Uniform Constraint Satisfaction and Bounded Treewidthp. 362
Referencesp. 367
Local Variations on a Loose Theme: Modal Logic and Decidabilityp. 371
Introductionp. 371
Modal Systems and Bisimulationsp. 373
Basic Modal Logicp. 378
Notesp. 388
Some Variationsp. 389
Neither Locality nor Looseness: Grid Logicsp. 390
Universal Access: Kp. 395
Generalizing Looseness: the Until Operatorp. 397
Modal Complexityp. 404
NP and the Polysize Model Propertyp. 405
PSPACE and Polynomially Deep Pathsp. 406
EXPTIME and Exponentially Deep Pathsp. 408
Notesp. 412
Modal Logic and First-Order Logicp. 413
Guarded Fragmentsp. 413
Decidability and Complexityp. 418
Notesp. 425
Referencesp. 426
Indexp. 431
Table of Contents provided by Ingram. All Rights Reserved.

ISBN: 9783540004288
ISBN-10: 3540004289
Series: Texts in Theoretical Computer Science. an Eatcs
Audience: General
Format: Hardcover
Language: English
Number Of Pages: 437
Published: 1st June 2007
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 24.13 x 15.88  x 1.91
Weight (kg): 0.74