Lecture Notes in Logic, 9

Bounded Variable Logics and Counting: A Study in Finite Models

Martin Otto

Year: 2017
ISBN: 9781107167940
Buy now

In this volume, the ninth publication in the Lecture Notes in Logic series, Martin Otto gives an introduction to finite model theory that indicates the main ideas and lines of inquiry that motivate research in this area. Particular attention is paid to bounded variable infinitary logics, with and without counting quantifiers, related fixed-point logics, and the corresponding fragments of Ptime. The relations with Ptime exhibit the fruitful exchange between ideas from logic and from complexity theory that is characteristic of finite model theory.

Table of Contents

  • Preface
  • Introduction
  1. Definitions and preliminaries
  2. The games and their analysis
  3. The invariants
  4. Fixed-point logic with counting
  5. Related Lindström extensions
  6. Canonization problems
  7. Canonization for two variables
  • Bibliography
  • Index