Finite Model Theory
Second Edition
Buch in deiner Nähe kaufen
Beschreibung
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.
Explores connections between axiomatizability of classes of finite structures and their complexity with respect to time and space bounds Includes important logics: fixed-point logics, transitive closure logics, and also certain infinitary languages Additional topics include DATALOG languages, quantifiers and oracles, 0-1 laws, and optimization and approximation problems The new Second Edition is thoroughly revised and enlarged Includes supplementary material: sn.pub/extras
Autor*in
Heinz-Dieter Ebbinghaus
Themen in »Finite Model Theory«
0-1-laws Finite model theory complexity complexity theory descriptive complexity theory fixed-point logics model theory