Subject Area: CS Basics (Logics, Discrete Mathematics)
in CIDEC Library.

### FINITE MODEL THEORY

Heinz-Dieter **EBBINGHAUS**, 1939- , University of Freiburg, Germany ;

Jörg **FLUM** , University of Freiburg, Germany
Series: Perspectives in Mathematical Logic.

Eds.: S. Feferman; W.A. Hodges; A.J. Macintyre; M. Magidor; Y.N. Moschovakis.

**Publisher : **
Springer-Verlag - Berlin ; New York

**Bibliographic : **

- Hardcover
- ISBN: 3-540-60149-X
- © 1995
- xv, 327 p. : ill. ; 24 cm.
- Dewey No.: 511.3 20

- Model theory
- endliche Modelltheorie; deskriptive Komplexitätstheorie; Fixpunktlogiken; 0-1-Gesetze
- M13100 Logic,Foundations,Set Theory
- M99501 Computer Applications
- I16005 Theory of Computation
- I16021 Algorithm Analysis and Problem Complexity
- I16048 Mathematical Logic and Formal Languages

**DESCRIPTION: **
Finite model theory has its origin in classical model theory, but owes its systematic development to research
from complexity 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, and optimization and approximation problems.
The book is written in such a way that the resp. parts on model theory and descriptive complexity theory
may be read independently.

**CONTENTS: **

Includes bibliographical references (p. [313]-317) and index.

**BOOK CATEGORY: **Monograph

Changed 04/11/1996. Comments: monika@cs.ioc.ee