Finite Model Theory

2. Auflage 1999. 2. printing 2005
ISBN: 978-3-540-28787-2
Verlag: Springer-Verlag GmbH

Buch, Englisch, 360 Seiten, Book, Format (B × H): 165 mm x 245 mm, Gewicht: 1550 g

Reihe: Springer Monographs in Mathematics

This volume 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. Important logics in this context include fixed-point logics, transitive closure logics, and also certain infinitary languages. 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.

Zielgruppe

Research

Autoren/Hrsg.

Ebbinghaus, Heinz-Dieter

Flum, Jörg

Fachgebiete

• Mathematik | Informatik Mathematik Mathematik Allgemein Grundlagen der Mathematik
• Mathematik | Informatik EDV | Informatik Informatik Logik, formale Sprachen, Automaten
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Numerische Mathematik

Inhaltsverzeichnis

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.