Generalized quantifiers and pebble games on finite structures
type: Item
instance of: scholarly article
title: Generalized quantifiers and pebble games on finite structures
zbMATH Open document ID: 0826.03017
DOI: 10.1016/0168-0072(94)00025-X
author: Phokion G. Kolaitis
author: Jouko Väänänen
published in: Annals of Pure and Applied Logic
publication date: 1995-07-03T00:00:00Z
review text: \(L^k_{\infty \omega}\), \(k \geq 1\), is an infinitary logic that allows infinite cojunctions and disjunctions, but has only a total of \(k\) distinct variables. The authors study the family of infinitary logics \(L^k_{\infty \omega} (Q)\), where \(Q = \{Q_i : i \in I\}\) is a collection of simple unary generalized quantifiers on finite structures. This paper investigates the model-theoretic properties and the expressive powers of these infinitary logics on finite structures. For example, the authors show that by using appropriate pebble games one can tell whether or not two finite structures satisfy the same sentences of \(L^k_{\infty \omega} (Q)\) (a game-theoretic characterization of equivalence). Pebble games are applied to obtain a structural characterization of counting quantifiers. The main technical result is that there are natural polynomial-time properties on finite structures that are expressible by sentences of \(L^2_{\infty \omega} (C)\), where \(C\) denotes the counting quantifiers, which are not expressible by sentences of \(L^k_{\infty \omega} (Q)\), where \(Q\) is a finite sequence of arbitrary simple unary generalized quantifiers and \(k\) is a positive integer. The proof requires sophisticated combinatorial tools. The paper ends with a section on abstract finite model theory.
Mathematics Subject Classification ID: 03C75
Mathematics Subject Classification ID: 03C80
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 03C95
zbMATH DE Number: 768747
zbMATH Keywords: infinitary logic
zbMATH Keywords: generalized quantifiers on finite structures
zbMATH Keywords: pebble games
zbMATH Keywords: counting quantifiers
zbMATH Keywords: abstract finite model theory
reviewed by: J. M. Plotkin
MaRDI profile type: Publication
cites work: Reachability is harder for directed than for undirected finite graphs
cites work: Monotone versus positive
cites work: On Moschovakis closure ordinals
cites work: Q3714043
cites work: Q3872438
cites work: Structure and complexity of relational queries
cites work: An observation on time-storage trade off
cites work: Q4058132
cites work: Monadic generalized spectra
cites work: Q3666827
cites work: Q4268486
cites work: Q3903002
cites work: Q3758820
cites work: Fixed-point extensions of first-order logic
cites work: Q4166743
cites work: Logical hierarchies in PTIME
cites work: The Härtig quantifier: a survey
cites work: Upper and lower bounds for first order expressibility
cites work: Relational queries computable in polynomial time
cites work: Definability with bounded number of bound variables
cites work: Q3745829
cites work: Logic with the quantifier “there exist uncountably many”
cites work: Model theory for infinitary logic. Logic with countable conjunctions and finite quantifiers
cites work: Q3747761
cites work: Q4105652
cites work: Inductive definitions over finite structures
cites work: Q3113046
cites work: On Extensions of Elementary Logic
cites work: Isomorphism of graphs of bounded valence can be tested in polynomial time
cites work: Elementary induction on abstract structures
cites work: On a generalization of quantifiers
cites work: Questions about quantifiers
cites work: Generalized Ehrenfeucht games
cites work: Q4342068
Recommended article: Q4362728
Recommended article: Games in finite model theory
Recommended article: On Some Applications of Games for Härtig Quantifier
Recommended article: Q4945237
Recommended article: Logic and games on automatic structures. Playing with quantifiers and decompositions
Recommended article: GAMES AND CARDINALITIES IN INQUISITIVE FIRST-ORDER LOGIC
Recommended article: Game semantics, quantifiers and logical omniscience
Recommended article: Q4395557
Recommended article: Pebble games and subroutines in least fixed point logic
Recommended article: Q3509079
description: scientific article; zbMATH DE number 768747