Finite Model Theory: Second Edition (Springer Monographs in Mathematics)
Second Edition
Gebundene Ausgabe
Sofort lieferbar | Lieferzeit: Sofort lieferbar I
Unbenutzt wie neu als Remittende gekennzeichnet
34,98 €*
Alle Preise inkl. MwSt.|Versandkostenfrei
ISBN-13:
9783540287872
Veröffentl:
2005
Einband:
Gebundene Ausgabe
Seiten:
371
Autor:
Heinz-Dieter Ebbinghaus, Jörg Flum
Gewicht:
733 g
SKU:
INF1000081785
Sprache:
Englisch
Beschreibung:
This is a thoroughly revised and enlarged second edition that 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. The book is written in such a way that the respective parts on model theory and descriptive complexity theory may be read independently.
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.
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.
Finite model theory has roots in classical model theory, but owes its systematic development to research from complexity theory and database theory. 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, optimization and approximation problems.
Kunden Rezensionen
Mehr zum Thema
Folgen Sie uns auf:
