| Finite Model Theory: Second Edition Revised Edition Contributor(s): Ebbinghaus, Heinz-Dieter (Author), Flum, Jörg (Author) |
|
 |
ISBN: 3540287876 ISBN-13: 9783540287872 Publisher: Springer OUR PRICE: $189.99 Product Type: Hardcover - Other Formats Published: October 2005 Annotation: The book presents the main results of descriptive complexity theory, that is, the connections between axiomatizability of classes of finite structures and their complexity with respect to time and space bounds. The logics that are important in this context include fixed-point logics, transitive closure logics, and also certain infinitary languages; their model theory is studied in full detail. Other topics include DATALOG languages, quantifiers and oracles, 0-1 laws, and optimization and approximation problems. The book is written in such a way that the respective parts on model theory and descriptive complexity theory may be read independently. This second edition is a thoroughly revised and enlarged version of the original text. |
| Additional Information |
| BISAC Categories: - Mathematics | Logic |
| Dewey: 511.3 |
| LCCN: 99039853 |
| Series: Springer Monographs in Mathematics |
| Physical Information: 1.03" H x 6.5" W x 9.48" (1.47 lbs) 360 pages |
| Descriptions, Reviews, Etc. |
| Publisher Description: Finite model theory, the model theory of finite structures, has roots in clas- sical model theory; however, its systematic development was strongly influ- enced by research and questions of complexity theory and of database theory. Model theory or the theory of models, as it was first named by Tarski in 1954, may be considered as the part of the semantics of formalized languages that is concerned with the interplay between the syntactic structure of an axiom system on the one hand and (algebraic, settheoretic, . . . ) properties of its models on the other hand. As it turned out, first-order language (we mostly speak of first-order logic) became the most prominent language in this respect, the reason being that it obeys some fundamental principles such as the compactness theorem and the completeness theorem. These principles are valuable modeltheoretic tools and, at the same time, reflect the expressive weakness of first-order logic. This weakness is the breeding ground for the freedom which modeltheoretic methods rest upon. By compactness, any first-order axiom system either has only finite models of limited cardinality or has infinite models. The first case is trivial because finitely many finite structures can explicitly be described by a first-order sentence. As model theory usually considers all models of an axiom system, modeltheorists were thus led to the second case, that is, to infinite structures. In fact, classical model theory of first-order logic and its generalizations to stronger languages live in the realm of the infinite. |