E-raamat: Finite Model Theory and Its Applications

Unifying Themes in Finite Model Theory		1	(26)
Definability Theory		2	(10)
Classification of Concepts in Terms of Definitional Complexity		2	(2)
What More Do We Know When We Know a Concept Is L-Definable?		4	(3)
Logics with Finitely Many Variables		7	(1)
Distinguishing Structures: L-Equivalence and Comparison Games		8	(2)
Random Graphs and 0--1 Laws		10	(1)
Constraint Satisfaction Problems		11	(1)
Descriptive Complexity		12	(6)
Satisfaction		13	(3)
What Is a Logic for PTIME?		16	(2)
Finite Model Theory and Infinite Structures		18	(2)
Tame Fragments and Tame Classes		20	(7)
References		22	(5)
On the Expressive Power of Logics on Finite Models		27	(98)
Introduction		27	(1)
Basic Concepts		28	(6)
Ehrenfeucht--Fraisse Games for First-Order Logic		34	(16)
Computational Complexity		50	(4)
Complexity Classes		50	(1)
The Complexity of Logic		51	(3)
Ehrenfeucht--Fraisse Games for Existential Second-Order Logic		54	(5)
Logics with Fixed-Point Operators		59	(27)
Operators and Fixed Points		60	(4)
Least Fixed-Point Logic		64	(10)
Datalog and Datalog(≠)		74	(5)
The Complementation Problem for LFP1 and a Normal Form for LFP		79	(3)
Partial Fixed-Point Logic		82	(4)
Infinitary Logics with Finitely Many Variables		86	(20)
The Infinitary Logic L		87	(2)
Pebble Games and L -Definability		89	(8)
0--1 Laws for L		97	(2)
Definability and Complexity of L -Equivalence		99	(5)
Least Fixed-Point Logic vs. Partial Fixed-Point Logic on Finite Structures		104	(2)
Existential Infinitary Logics with Finitely Many Variables		106	(19)
The Infinitary Logics L and L		107	(2)
Existential Pebble Games		109	(7)
Descriptive Complexity of Fixed Subgraph Homeomorphism Queries		116	(3)
References		119	(6)
Finite Model Theory and Descriptive Complexity		125	(106)
Definability and Complexity		125	(13)
Complexity Issues in Logic		126	(2)
Model Checking for First-Order Logic		128	(1)
The Strategy Problem for Finite Games		129	(3)
Complexity of First-Order Model Checking		132	(3)
Encoding Finite Structures by Words		135	(3)
Capturing Complexity Classes		138	(14)
Capturing NP: Fagin's Theorem		138	(6)
Logics That Capture Complexity Classes		144	(1)
Capturing Polynomial Time on Ordered Structures		145	(4)
Capturing Logarithmic Space Complexity		149	(2)
Transitive Closure Logics		151	(1)
Fixed-Point Logics		152	(34)
Some Fixed-Point Theory		153	(2)
Least Fixed-Point Logic		155	(2)
The Modal μ-Calculus		157	(3)
Parity Games		160	(5)
Model-Checking Games for Least Fixed-Point Logic		165	(4)
Definability of Winning Regions in Parity Games		169	(1)
Simultaneous Fixed-Point Inductions		170	(4)
Inflationary Fixed-Point Logic		174	(3)
Partial Fixed-Point Logic		177	(3)
Datalog and Stratified Datalog		180	(6)
Logics with Counting		186	(7)
Logics with Counting Terms		187	(1)
Fixed-Point Logic with Counting		188	(2)
Datalog with Counting		190	(3)
Capturing PTIME via Canonization		193	(12)
Definable Linear Orders		193	(1)
Canonizations and Interpretations		194	(4)
Capturing PTIME up to Bisimulation		198	(5)
Is There a Logic for PTIME?		203	(2)
Algorithmic Model Theory		205	(17)
Beyond Finite Structures		205	(1)
Finitely Presentable Structures		206	(4)
Metafinite Structures		210	(3)
Metafinite Spectra		213	(3)
Descriptive Complexity over the Real Numbers		216	(6)
Appendix: Alternating Complexity Classes		222	(9)
References		225	(6)
Logic and Random Structures		231	(26)
An Instructive Example		231	(3)
Random Graphs		234	(1)
Extension Statements		235	(2)
Closure		237	(2)
The Almost Sure Theory		239	(2)
The Case p Constant		241	(1)
Countable Models		242	(1)
A Dynamic View		243	(1)
Infinite Spectra via Almost Sure Encoding		244	(2)
The Jump Condition		246	(1)
The Complexity Condition		247	(2)
Nonconvergence via Almost Sure Encoding		249	(2)
No Almost Sure Representation of Evenness		251	(2)
The Ehrenfeucht Game		253	(1)
About the References		254	(3)
References		255	(2)
Embedded Finite Models and Constraint Databases		257	(82)
Introduction		257	(1)
Organization		258	(1)
Relational Databases and Embedded Finite Models		258	(4)
Constraint Databases		262	(4)
Collapse and Genericity: An Overview		266	(3)
Approaches to Proving Expressivity Bounds		267	(2)
Active-Generic Collapse		269	(4)
The Ramsey Property		269	(3)
Collapse Results		272	(1)
Natural-Active Collapse		273	(15)
Collapse: Failure and Success		274	(2)
Good Structures vs. Bad Structures: O-minimality		276	(1)
Collapse Theorem and Corollaries		277	(1)
Collapse Algorithm: the Linear Case		278	(2)
Collapse Algorithm: the General Case		280	(5)
Collapse Without O-minimality		285	(2)
Natural-Generic Collapse		287	(1)
Model Theory and Collapse Results		288	(7)
Pseudo-finite Homogeneity		289	(1)
Finite Cover Property and Collapse		290	(2)
Isolation and Collapse		292	(3)
The VC Dimension and Collapse Results		295	(6)
Random Graph and Collapse to MSO		298	(1)
Complexity Bounds for Generic Queries		299	(2)
Expressiveness of Constraint Query Languages		301	(6)
Reductions to the Finite Case		301	(2)
Topological Properties		303	(2)
Linear vs. Polynomial Constraints		305	(2)
Query Safety		307	(15)
Finite and Infinite Query Safety		308	(1)
Safe Translations		309	(2)
Finite Query Safety: Characterization		311	(5)
Infinite Query Safety: Reduction		316	(3)
Deciding Safety		319	(2)
Dichotomy Theorem for Embedded Finite Models		321	(1)
Database Considerations		322	(8)
Aggregate Operators		323	(3)
Higher-Order Features		326	(4)
Bibliographic Notes		330	(9)
References		334	(5)
A Logical Approach to Constraint Satisfaction		339	(32)
Introduction		339	(1)
Preliminaries		340	(4)
The Computational Complexity of Constraint Satisfaction		344	(3)
Nonuniform Constraint Satisfaction		347	(3)
Monotone Monadic SNP and Nonuniform Constraint Satisfaction		350	(2)
Datalog and Nonuniform Constraint Satisfaction		352	(3)
Datalog, Games, and Constraint Satisfaction		355	(2)
Games and Consistency		357	(5)
Uniform Constraint Satisfaction and Bounded Treewidth		362	(9)
References		367	(4)
Local Variations on a Loose Theme: Modal Logic and Decidability		371	(60)
Introduction		371	(2)
Modal Systems and Bisimulations		373	(5)
Basic Modal Logic		378	(11)
Notes		388	(1)
Some Variations		389	(15)
Neither Locality nor Looseness: Grid Logics		390	(5)
Universal Access: K*		395	(2)
Generalizing Looseness: the Until Operator		397	(7)
Modal Complexity		404	(9)
NP and the Polysize Model Property		405	(1)
PSPACE and Polynomially Deep Paths		406	(2)
EXPTIME and Exponentially Deep Paths		408	(2)
NEXPTIME		410	(2)
Notes		412	(1)
Modal Logic and First-Order Logic		413	(18)
Guarded Fragments		413	(5)
Decidability and Complexity		418	(7)
Notes		425	(1)
References		426	(5)
Index		431

Erich Graedel is a Professor of Mathematical Foundations of Computer Science at the University of Technology Aachen.  His research interests include algorithms, complexity, and logic in computer science.



Phokion G. Kolaitis is a professor of computer science at the University of California, Santa Cruz. His current research interests include logic in computer science, computational complexity, and database theory. He earned a Diploma in Mathematics from the University of Athens, Greece in 1973, and a Ph.D. in Mathematics from the University of California, Los Angeles in 1978. Before joining UC Santa Cruz in 1988, he served as an L.E. Dickson Instructor of Mathematics at the University of Chicago, a faculty member at Occidental College, a visiting faculty member at Stanford University, and a visiting scientist at the IBM Almaden Research Center. Kolaitis was awarded a Guggenheim Fellowship during 1993-94. In 1995, he received an Excellence in Teaching Award by the graduating computer science and computer engineering students at UC Santa Cruz.



Leonid Libkin received his PhD from the University of Pennsylvania and is currently Professor of Computer Science at the University of Toronto. His main research interests include databases and applications of logic in computer science.



Maarten Marx is an associate professor at the Vrije Universiteit Amsterdam. His research interests are in modal and algebraic logic.



Joel Spencer is a Professor of Mathematics and Computer Scienceat the Courant Institute, New York University. His research interests lie in interface between Discrete Mathematics and Theoretical Computer Science, most particularly with the Probabilistic Method as developed by Paul Erdos.



Moshe Y. Vardi is a Noah Harding Professor of Computer Science and Chair of Computer Science at Rice University. Prior to joining Rice in 1993, he was at the IBM Almaden Research Center, where he managed the Mathematics and Related Computer Science Department. His research interests include database systems, computational-complexity theory, multi-agent systems, and design specification and verification. Vardi received his Ph.D. from the Hebrew University of Jerusalem in 1981. He is the author and co-author of over 120 technical papers, as well as a book titled "Reasoning about Knowledge". Vardi is the recipient of 3 IBM Outstanding Innovation Awards. He is an editor of several international journals and is a Fellow of the Association of Computing Machinery.



Yde Venema studied mathematics; in 1992, he received a PhD in Logic with the dissertation `Many-Dimensional Modal Logic'. He is currently a Research Fellow of the Royal Netherlands Academy of Arts and Sciences and an assistant professor at the Institute for Logic, Language and Computation of the University of Amsterdam. His research interests include modal and temporal logic, algebraic logic, and applications of logic in linguistics and computer science.



Scott Weinstein is Professor of Computer Science, Mathematics, and Philosophy at the University of Pennsylvania. His research interests include logic in computer science and the philosphy of mathematics.