Bounded variable logics and counting : a study in finite models

• Autore: Otto Martin
• Pubblicazione: [Place of publication not identified], : Springer, 1997
• Edizione: 1st ed.
• Descrizione fisica: 1 online resource (190 pages)
• Disciplina: 511.3/3
• Soggetto topico: Model theory; Computational complexity; Mathematics; Physical Sciences & Mathematics; Mathematical Theory
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di contenuto: Lecture Notes in Logic 9 Bounded Variable Logics and Counting A Study in Finite Models -- Bounded Variable Logics and Counting -- Copyright -- Preface -- Table of Contents -- 0. 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.
• Sommario/riassunto: Viewed as a branch of model theory, finite model theory is concerned with finite structures and their properties under logical, combinatorial, algorithmic and complexity theoretic aspects. The connection of classical concerns of logic and model theory with issues in complexity theory has contributed very much to the development of finite model theory into a field with its own specific flavour. I like to think of this monograph as a study which - with a partic­ ular theme of its own - exemplifies and reflects some central ideas and lines of research in finite model theory. The particular theme is that of bounded variable infinitary logics, with and without counting quantifiers, related fixed-point logics, and corresponding fragments of PTIME. The re­ lations with PTIME exhibit that fruitful exchange between ideas from logic and from complexity theory that is characteristic of finite model theory and, more specifically, of the research programme of descriptive complexity. Among the main particular topics and techniques I would emphasize: - the importance of games as a fundamental tool from classical logic; their use in the analysis of finite structures also with respect to algorithmic and complexity theoretic concerns is amply illustrated. - the role of cardinality phenomena, which clearly are amongst the most fundamental guidelines in the analysis of finite structures.
• Titolo abbreviato (Periodici): BOUNDED VARIABLE LOGICS AND COUNTING
• Titolo autorizzato: Bounded variable logics and counting : a study in finite models
• ISBN: 3-662-21676-0
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910482885703321
• Lo trovi qui: Univ. Federico II
• Serie: Lecture Notes in Logic