Finite Model Theory and Its Applications

>> Google Books

Finite Model Theory and Its Applications / Erich Grädel, W. Brauer, J. Hromkovic, Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema, Scott Weinstein, M. Marx, G. Rozenberg, J. Spencer, Scott A. Weinstein

資料種別:

電子ブック

出版情報:

SpringerLink Books - AutoHoldings
Springer Berlin Heidelberg, 2007

著者名:

ISBN:

9783540004288 [3540004289]
9783540688044 [3540688048]

書誌ID:

OB00493892

子書誌情報

フルテキスト

所蔵情報

書誌詳細

言語:

英語

目次情報:

Unifying Themes in Finite Model Theory / 1：

Definability Theory / 1.1：

Classification of Concepts in Terms of Definitional Complexity / 1.1.1：

What More Do We Know When We Know a Concept Is L-Definable? / 1.1.2：

Logics with Finitely Many Variables / 1.1.3：

Distinguishing Structures: L-Equivalence and Comparison Games / 1.1.4：

Random Graphs and 0-1 Laws / 1.1.5：

Constraint Satisfaction Problems / 1.1.6：

Descriptive Complexity / 1.2：

Satisfaction / 1.2.1：

What Is a Logic for PTIME? / 1.2.2：

Finite Model Theory and Infinite Structures / 1.3：

Tame Fragments and Tame Classes / 1.4：

References

On the Expressive Power of Logics on Finite Models / 2：

Introduction / 2.1：

Basic Concepts / 2.2：

Ehrenfeucht-Fraisse Games for First-Order Logic / 2.3：

Computational Complexity / 2.4：

Complexity Classes / 2.4.1：

The Complexity of Logic / 2.4.2：

Ehrenfeucht-Fraisse Games for Existential Second-Order Logic / 2.5：

Logics with Fixed-Point Operators / 2.6：

Operators and Fixed Points / 2.6.1：

Least Fixed-Point Logic / 2.6.2：

Datalog and Datalog([NotEqual]) / 2.6.3：

The Complementation Problem for LFP[subscript 1] and a Normal Form for LFP / 2.6.4：

Partial Fixed-Point Logic / 2.6.5：

Infinitary Logics with Finitely Many Variables / 2.7：

The Infinitary Logic L[Characters not reproducible] / 2.7.1：

Pebble Games and L[Characters not reproducible]-Definability / 2.7.2：

0-1 Laws for L[Characters not reproducible] / 2.7.3：

Definability and Complexity of L[Characters not reproducible]-Equivalence / 2.7.4：

Least Fixed-Point Logic vs. Partial Fixed-Point Logic on Finite Structures / 2.7.5：

Existential Infinitary Logics with Finitely Many Variables / 2.8：

The Infinitary Logics [Characters not reproducible] and [Characters not reproducible] ([NotEqual]) / 2.8.1：

Existential Pebble Games / 2.8.2：

Descriptive Complexity of Fixed Subgraph Homeomorphism Queries / 2.8.3：

Finite Model Theory and Descriptive Complexity / 3：

Definability and Complexity / 3.1：

Complexity Issues in Logic / 3.1.1：

Model Checking for First-Order Logic / 3.1.2：

The Strategy Problem for Finite Games / 3.1.3：

Complexity of First-Order Model Checking / 3.1.4：

Encoding Finite Structures by Words / 3.1.5：

Capturing Complexity Classes / 3.2：

Capturing NP: Fagin's Theorem / 3.2.1：

Logics That Capture Complexity Classes / 3.2.2：

Capturing Polynomial Time on Ordered Structures / 3.2.3：

Capturing Logarithmic Space Complexity / 3.2.4：

Transitive Closure Logics / 3.2.5：

Fixed-Point Logics / 3.3：

Some Fixed-Point Theory / 3.3.1：

The Modal [mu]-Calculus / 3.3.2：

Parity Games / 3.3.4：

Model-Checking Games for Least Fixed-Point Logic / 3.3.5：

Definability of Winning Regions in Parity Games / 3.3.6：

Simultaneous Fixed-Point Inductions / 3.3.7：

Inflationary Fixed-Point Logic / 3.3.8：

Datalog and Stratified Datalog / 3.3.9：

Logics with Counting / 3.4：

Logics with Counting Terms / 3.4.1：

Fixed-Point Logic with Counting / 3.4.2：

Datalog with Counting / 3.4.3：

Capturing PTIME via Canonization / 3.5：

Definable Linear Orders / 3.5.1：

Canonizations and Interpretations / 3.5.2：

Capturing PTIME up to Bisimulation / 3.5.3：

Is There a Logic for PTIME? / 3.5.4：

Algorithmic Model Theory / 3.6：

Beyond Finite Structures / 3.6.1：

Finitely Presentable Structures / 3.6.2：

Metafinite Structures / 3.6.3：

Metafinite Spectra / 3.6.4：

Descriptive Complexity over the Real Numbers / 3.6.5：

Appendix: Alternating Complexity Classes / 3.7：

Logic and Random Structures / 4：

An Instructive Example / 4.1：

Random Graphs / 4.2：

Extension Statements / 4.3：

Closure / 4.4：

The Almost Sure Theory / 4.5：

The Case p Constant / 4.6：

Countable Models / 4.7：

A Dynamic View / 4.8：

Infinite Spectra via Almost Sure Encoding / 4.9：

The Jump Condition / 4.10：

The Complexity Condition / 4.11：

Nonconvergence via Almost Sure Encoding / 4.12：

No Almost Sure Representation of Evenness / 4.13：

The Ehrenfeucht Game / 4.14：

About the References / 4.15：

Embedded Finite Models and Constraint Databases / 5：

Organization / 5.1：

Relational Databases and Embedded Finite Models / 5.2：

Constraint Databases / 5.3：

Collapse and Genericity: An Overview / 5.4：

Approaches to Proving Expressivity Bounds / 5.4.1：

Active-Generic Collapse / 5.5：

The Ramsey Property / 5.5.1：

Collapse Results / 5.5.2：

Natural-Active Collapse / 5.6：

Collapse: Failure and Success / 5.6.1：

Good Structures vs. Bad Structures: O-minimality / 5.6.2：

Collapse Theorem and Corollaries / 5.6.3：

Collapse Algorithm: the Linear Case / 5.6.4：

Collapse Algorithm: the General Case / 5.6.5：

Collapse Without O-minimality / 5.6.6：

Natural-Generic Collapse / 5.6.7：

Model Theory and Collapse Results / 5.7：

Pseudo-finite Homogeneity / 5.7.1：

Finite Cover Property and Collapse / 5.7.2：

Isolation and Collapse / 5.7.3：

The VC Dimension and Collapse Results / 5.8：

Random Graph and Collapse to MSO / 5.8.1：

Complexity Bounds for Generic Queries / 5.8.2：

Expressiveness of Constraint Query Languages / 5.9：

Reductions to the Finite Case / 5.9.1：

Topological Properties / 5.9.2：

Linear vs. Polynomial Constraints / 5.9.3：

Query Safety / 5.10：

Finite and Infinite Query Safety / 5.10.1：

Safe Translations / 5.10.2：

Finite Query Safety: Characterization / 5.10.3：

Infinite Query Safety: Reduction / 5.10.4：

Deciding Safety / 5.10.5：

Dichotomy Theorem for Embedded Finite Models / 5.10.6：

Database Considerations / 5.11：

Aggregate Operators / 5.11.1：

Higher-Order Features / 5.11.2：

Bibliographic Notes / 5.12：

A Logical Approach to Constraint Satisfaction / 6：

Preliminaries / 6.1：

The Computational Complexity of Constraint Satisfaction / 6.3：

Nonuniform Constraint Satisfaction / 6.4：

Monotone Monadic SNP and Nonuniform Constraint Satisfaction / 6.5：

Datalog and Nonuniform Constraint Satisfaction / 6.6：

Datalog, Games, and Constraint Satisfaction / 6.7：

Games and Consistency / 6.8：

Uniform Constraint Satisfaction and Bounded Treewidth / 6.9：

Local Variations on a Loose Theme: Modal Logic and Decidability / 7：

Modal Systems and Bisimulations / 7.1：

Basic Modal Logic / 7.3：

Notes / 7.3.1：

Some Variations / 7.4：

Neither Locality nor Looseness: Grid Logics / 7.4.1：

Universal Access: K / 7.4.2：

Generalizing Looseness: the Until Operator / 7.4.3：

Modal Complexity / 7.5：

NP and the Polysize Model Property / 7.5.1：

PSPACE and Polynomially Deep Paths / 7.5.2：

EXPTIME and Exponentially Deep Paths / 7.5.3：

NEXPTIME / 7.5.4：

Modal Logic and First-Order Logic / 7.5.5：

Guarded Fragments / 7.6.1：

Decidability and Complexity / 7.6.2：

Index / 7.6.3：

Unifying Themes in Finite Model Theory / 1：

Definability Theory / 1.1：

Classification of Concepts in Terms of Definitional Complexity / 1.1.1：

What More Do We Know When We Know a Concept Is L-Definable? / 1.1.2：

Logics with Finitely Many Variables / 1.1.3：

Distinguishing Structures: L-Equivalence and Comparison Games / 1.1.4：

続きを見る

東工大ブックレビュー

類似資料:

1 電子ブック Finite Model Theory and Its Applications Gr?del, Erich, Brauer, W., Hromkovic, J., Kolaitis, Phokion G., Libkin, Leonid, Marx, Maarten, Spencer, Joel, Vardi, … Springer eBooks Computer Science, Springer Berlin Heidelberg	7 図書 Modal logic and process algebra : a bisimulation perspective (: pbk) Ponse, A. (Alban), 1955-, Rijke, Maarten de, Venema, Yde, 1963- Center for the Study of Language and Information
2 図書 Elements of finite model theory (: pbk) Libkin, Leonid Springer	8 電子ブック Dissemination of Information in Communication Networks Brauer, Wilfried, Hromkovic, J., Rozenberg, Grzegorz, Klasing, R., Pelc, A., Ruzicka, P., Unger, W., Klasing, Ralf, … SpringerLink Books - AutoHoldings, Springer Berlin Heidelberg
3 電子ブック Design and Analysis of Randomized Algorithms Brauer, Wilfried, Hromkovic, J., Rozenberg, Grzegorz Springer eBooks Computer Science, Springer Berlin Heidelberg	9 電子ブック Abstract Computing Machines Kluge, W., Brauer, W., Rozenberg, G., Salomaa, A. Springer eBooks Computer Science, Springer Berlin Heidelberg
4 電子ブック Design and Analysis of Randomized Algorithms Brauer, Wilfried, Hromkovic, J., Rozenberg, Grzegorz, Zámecniková, I. SpringerLink Books - AutoHoldings, Springer Berlin Heidelberg	10 電子ブック Abstract Computing Machines Kluge, W., Brauer, W., Rozenberg, G., Salomaa, A. SpringerLink Books - AutoHoldings, Springer Berlin Heidelberg
5 電子ブック Dissemination of Information in Communication Networks Brauer, Wilfried, Hromkovic, J., Rozenberg, Grzegorz, Klasing, R., Pelc, A., Ruzicka, P., Unger, W. Springer eBooks Computer Science, Springer Berlin Heidelberg	11 電子ブック Decision Procedures Kroening, Daniel, Brauer, W., HromkoviÄ, J., Strichman, Ofer, Bryant, R. E., Rozenberg, G. SpringerLink Books - AutoHoldings, Springer Berlin Heidelberg
6 電子ブック Modelling Distributed Systems Fokkink, Wan, Brauer, Wilfried, Hromkovic, Juraj, Rozenberg, Grzegorz SpringerLink Books - AutoHoldings, Springer Berlin Heidelberg	12 電子ブック Modelling Distributed Systems Fokkink, Wan, Brauer, Wilfried, Hromkovic, Juraj Springer eBooks Computer Science, Springer Berlin Heidelberg