Finite Model Theory (eBook)

eBook Download: PDF

2006 | 2. Auflage
XI, 360 Seiten
Springer-Verlag
978-3-540-28788-9 (ISBN)

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.

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.

Erscheint lt. Verlag	1.1.2006
Reihe/Serie	Springer Monographs in Mathematics
Sprache	englisch
Themenwelt	Geisteswissenschaften ► Philosophie ► Logik
	Mathematik / Informatik ► Mathematik ► Allgemeines / Lexika
	Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
Schlagworte	0-1-laws • Complexity • Complexity theory • descriptive complexity theory • Finite model theory • fixed-point logics • model Theory
ISBN-10	3-540-28788-4 / 3540287884
ISBN-13	978-3-540-28788-9 / 9783540287889

Haben Sie eine Frage zum Produkt?

PDF (Wasserzeichen)
Größe: 47,4 MB

DRM: Digitales Wasserzeichen
Dieses eBook enthält ein digitales Wasserzeichen und ist damit für Sie personalisiert. Bei einer missbräuchlichen Weitergabe des eBooks an Dritte ist eine Rückverfolgung an die Quelle möglich.

Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.

Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen dafür einen PDF-Viewer - z.B. den Adobe Reader oder Adobe Digital Editions.
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen dafür einen PDF-Viewer - z.B. die kostenlose Adobe Digital Editions-App.

Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.

Print-Ausgabe

Buch | Hardcover

192,59 €