Skip to main content
SpringerLink
Log in

Finite Model Theory

Second Edition

  • Book
  • © 1995

Overview

Authors:
  1. Heinz-Dieter Ebbinghaus

    1. Mathematisches Institut Abteilung für Mathematische Logik, Universität Freiburg, Freiburg, Germany

    View author publications

    You can also search for this author in PubMed   Google Scholar

  2. Jörg Flum

    1. Mathematisches Institut Abteilung für Mathematische Logik, Universität Freiburg, Freiburg, Germany

    View author publications

    You can also search for this author in PubMed   Google Scholar

  • 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

Part of the book series: Springer Monographs in Mathematics (SMM)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 149.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book USD 199.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (12 chapters)

  1. Front Matter

    Pages I-XI
    Download chapter PDF

  2. Preliminaries

    • Heinz-Dieter Ebbinghaus, Jörg Flum
    Pages 1-12

  3. The Ehrenfeucht-Fraïssé Method

    • Heinz-Dieter Ebbinghaus, Jörg Flum
    Pages 13-35

  4. More on Games

    • Heinz-Dieter Ebbinghaus, Jörg Flum
    Pages 37-69

  5. 0-1 Laws

    • Heinz-Dieter Ebbinghaus, Jörg Flum
    Pages 71-93

  6. Satisfiability in the Finite

    • Heinz-Dieter Ebbinghaus, Jörg Flum
    Pages 95-103

  7. Finite Automata and Logic: A Microcosm of Finite Model Theory

    • Heinz-Dieter Ebbinghaus, Jörg Flum
    Pages 105-117

  8. Descriptive Complexity Theory

    • Heinz-Dieter Ebbinghaus, Jörg Flum
    Pages 119-164

  9. Logics with Fixed-Point Operators

    • Heinz-Dieter Ebbinghaus, Jörg Flum
    Pages 165-238

  10. Logic Programs

    • Heinz-Dieter Ebbinghaus, Jörg Flum
    Pages 239-273

  11. Optimization Problems

    • Heinz-Dieter Ebbinghaus, Jörg Flum
    Pages 275-285

  12. Logics for PTIME

    • Heinz-Dieter Ebbinghaus, Jörg Flum
    Pages 287-306

  13. Quantifiers and Logical Reductions

    • Heinz-Dieter Ebbinghaus, Jörg Flum
    Pages 307-338

  14. Back Matter

    Pages 339-360
    Download chapter PDF
Back to top

Keywords

About this book

Finite model theory, the model theory of finite structures, has roots in clas­ sical model theory; however, its systematic development was strongly influ­ enced by research and questions of complexity theory and of database theory. Model theory or the theory of models, as it was first named by Tarski in 1954, may be considered as the part of the semantics of formalized languages that is concerned with the interplay between the syntactic structure of an axiom system on the one hand and (algebraic, settheoretic, . . . ) properties of its models on the other hand. As it turned out, first-order language (we mostly speak of first-order logic) became the most prominent language in this respect, the reason being that it obeys some fundamental principles such as the compactness theorem and the completeness theorem. These principles are valuable modeltheoretic tools and, at the same time, reflect the expressive weakness of first-order logic. This weakness is the breeding ground for the freedomwhich modeltheoretic methods rest upon. By compactness, any first-order axiom system either has only finite models of limited cardinality or has infinite models. The first case is trivial because finitely many finite structures can explicitly be described by a first-order sentence. As model theory usually considers all models of an axiom system, modeltheorists were thus led to the second case, that is, to infinite structures. In fact, classical model theory of first-order logic and its generalizations to stronger languages live in the realm of the infinite.

Authors and Affiliations

  • Mathematisches Institut Abteilung für Mathematische Logik, Universität Freiburg, Freiburg, Germany

    Heinz-Dieter Ebbinghaus, Jörg Flum

Bibliographic Information

  • Book Title: Finite Model Theory

  • Book Subtitle: Second Edition

  • Authors: Heinz-Dieter Ebbinghaus, Jörg Flum

  • Series Title: Springer Monographs in Mathematics

  • DOI: https://doi.org/10.1007/3-540-28788-4

  • Publisher: Springer Berlin, Heidelberg

  • eBook Packages: Springer Book Archive

  • Copyright Information: Springer-Verlag Berlin Heidelberg 1995

  • Hardcover ISBN: 978-3-540-28787-2Published: 06 October 2005

  • eBook ISBN: 978-3-540-28788-9Published: 29 December 2005

  • Series ISSN: 1439-7382

  • Series E-ISSN: 2196-9922

  • Edition Number: 2

  • Number of Pages: XI, 360

  • Additional Information: Originally published in the series: Perspectives in Mathematical Logic

  • Topics: Mathematical Logic and Foundations, Mathematical Logic and Formal Languages

Publish with us

Policies and ethics

Back to top

Search

Navigation