Generalized quantifiers and pebble games on finite structures

DOI10.1016/0168-0072(94)00025-XzbMath0826.03017MaRDI QIDQ1892941

Jouko Väänänen, Phokion G. Kolaitis

Publication date: 3 July 1995

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

infinitary logiccounting quantifierspebble gamesabstract finite model theorygeneralized quantifiers on finite structures

Mathematics Subject Classification ID

Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Other infinitary logic (03C75) Abstract model theory (03C95)

Related Items (20)

GAMES AND CARDINALITIES IN INQUISITIVE FIRST-ORDER LOGIC ⋮ Dependence logic with generalized quantifiers: axiomatizations ⋮ Semantic Restrictions over Second-Order Logic ⋮ An Extension of the Ehrenfeucht-Fraïssé Game for First Order Logics Augmented with Lindström Quantifiers ⋮ Games and Lindström theorems ⋮ On vectorizations of unary generalized quantifiers ⋮ The hierarchy theorem for generalized quantifiers ⋮ Relativized logspace and generalized quantifiers over finite ordered structures ⋮ Syllogistic Logic with Cardinality Comparisons ⋮ On the expressive power of counting ⋮ On probabilistic elimination of generalized quantifiers ⋮ Game-based notions of locality over finite models ⋮ Notions of locality and their logical characterizations over finite models ⋮ Sameness ⋮ On the complexities of consistency checking for restricted UML class diagrams ⋮ Almost Everywhere Equivalence of Logics in Finite Model Theory ⋮ Lower bounds for invariant queries in logics with counting. ⋮ Counting modulo quantifiers on finite structures ⋮ Adding for-loops to first-order logic ⋮ On the expressive power of monotone natural language quantifiers over finite models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Definability with bounded number of bound variables
• Fixed-point extensions of first-order logic
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Upper and lower bounds for first order expressibility
• An observation on time-storage trade off
• Elementary induction on abstract structures
• Logical hierarchies in PTIME
• Structure and complexity of relational queries
• Model theory for infinitary logic. Logic with countable conjunctions and finite quantifiers
• Inductive definitions over finite structures
• On a generalization of quantifiers
• Reachability is harder for directed than for undirected finite graphs
• Questions about quantifiers
• Relational queries computable in polynomial time
• Monotone versus positive
• The Härtig quantifier: a survey
• Monadic generalized spectra
• On Moschovakis closure ordinals
• Generalized Ehrenfeucht games
• On Extensions of Elementary Logic
• Logic with the quantifier “there exist uncountably many”

This page was built for publication: Generalized quantifiers and pebble games on finite structures