LEADER 03699oam 2200613zu 450 001 9910482885703321 005 20240724212510.0 010 $a3-662-21676-0 035 $a(CKB)1000000000751035 035 $a(SSID)ssj0000508723 035 $a(PQKBManifestationID)12183167 035 $a(PQKBTitleCode)TC0000508723 035 $a(PQKBWorkID)10562778 035 $a(PQKB)11207601 035 $a(MiAaPQ)EBC3099502 035 $a(Au-PeEL)EBL3099502 035 $a(CaPaEBR)ebr10974403 035 $a(OCoLC)934997347 035 $a(BIP)47313338 035 $a(EXLCZ)991000000000751035 100 $a20160829d1997 uy 101 0 $aeng 135 $aurcnu|||||||| 181 $ctxt 182 $cc 183 $acr 200 10$aBounded variable logics and counting : a study in finite models 205 $a1st ed. 210 31$a[Place of publication not identified]$cSpringer$d1997 215 $a1 online resource (190 pages) 225 0 $aLecture notes in logic Bounded variable logics and counting 300 $aBibliographic Level Mode of Issuance: Monograph 311 08$a3-540-62037-0 327 $aLecture 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 Lindstro?m Extensions -- 6. Canonization Problems -- 7. Canonization for Two Variables -- Bibliography -- Index. 330 $aViewed 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. 410 0$aLecture Notes in Logic 531 $aBOUNDED VARIABLE LOGICS AND COUNTING 606 $aModel theory 606 $aComputational complexity 606 $aMathematics$2HILCC 606 $aPhysical Sciences & Mathematics$2HILCC 606 $aMathematical Theory$2HILCC 615 0$aModel theory. 615 0$aComputational complexity. 615 7$aMathematics 615 7$aPhysical Sciences & Mathematics 615 7$aMathematical Theory 676 $a511.3/3 700 $aOtto$b Martin$01225992 801 0$bPQKB 906 $aBOOK 912 $a9910482885703321 996 $aBounded variable logics and counting : a study in finite models$92846465 997 $aUNINA