Finite model theory /
Presents the main results of descriptive complexity theory - the connections between axiomatizability of classes of finite structures and their complexity with respect to time and space bounds. This book also looks at important logic in this context, which include fixed-point logic, transitive closu...
| Main Author: | |
|---|---|
| Corporate Author: | |
| Other Authors: | |
| Format: | eBook |
| Language: | English |
| Published: |
New York, NY :
Springer,
2005.
|
| Edition: | 2nd rev. and enl. ed. 1999. |
| Series: | Springer monographs in mathematics.
|
| Subjects: | |
| Online Access: | Connect to the full text of this electronic book |
Table of Contents:
- Preliminaries; The Ehrenfeucht-Fraïssé Method; More on Games; 0-1 Laws; Satisfiability in the Finite; Finite Automata and Logic: A Microcosm of Finite Model Theory; Descriptive Complexity Theory; Logics with Fixed-Point Operators; Logic Programs; Optimization Problems; Logics for PTIME; Quantifiers and Logical Reductions.