Game-based notions of locality over finite models

DOI10.1016/J.APAL.2007.11.012MaRDI QIDQ2478544zbMATH OpenOpenAlexFDO

Authors Marcelo Arenas, Pablo Barceló, Leonid Libkin

Publication date 28 March 2008

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

Full work available at URL https://doi.org/10.1016/j.apal.2007.11.012

zbMATH Keywords

finite model theoryGaifman localitygamesHanf locality

Mathematics Subject Classification ID

Basic properties of first-order languages and structures (03C07) Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Applications of model theory (03C98)

Recommendations

• Computer Science Logic
• Notions of locality and their logical characterizations over finite models
• Locality and modular Ehrenfeucht-Fraïssé games
• scientific article; zbMATH DE number 1136084
• scientific article; zbMATH DE number 1375591

Cites work

• A local normal form theorem for infinitary logic with unary quantifiers
• Algorithmic uses of the Feferman-Vaught theorem
• An existential locality theorem
• Counting modulo quantifiers on finite structures
• Counting quantifiers, successor relations, and logarithmic space
• Data exchange: semantics and query answering
• Fixed-parameter tractability, definability, and model-checking
• Generalized quantifiers and pebble games on finite structures
• scientific article; zbMATH DE number 1059242 (Why is no real title available?)
• scientific article; zbMATH DE number 1136084 (Why is no real title available?)
• scientific article; zbMATH DE number 969067 (Why is no real title available?)
• scientific article; zbMATH DE number 3266604 (Why is no real title available?)
• scientific article; zbMATH DE number 3333278 (Why is no real title available?)
• Logical hierarchies in PTIME
• Logics with aggregate operators
• Logics with counting and local properties
• Lower bounds for invariant queries in logics with counting.
• Notions of locality and their logical characterizations over finite models
• On monadic NP vs monadic co-NP
• On winning strategies with unary quantifiers
• Shrinking games and local formulas
• Unary quantifiers on finite models
• Verifiable properties of database transactions

Cited in

(5)

• scientific article; zbMATH DE number 1375591 (Why is no real title available?)
• scientific article; zbMATH DE number 1136084 (Why is no real title available?)
• Notions of locality and their logical characterizations over finite models
• Computer Science Logic
• Differential games, locality, and model checking for FO logic of graphs

This page was built for publication: Game-based notions of locality over finite models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2478544)