Notions of locality and their logical characterizations over finite models

DOI10.2307/2586810zbMath0946.03012OpenAlexW1976218595MaRDI QIDQ4948541

Juha Nurmonen, Lauri Hella, Leonid O. Libkin

Publication date: 7 June 2000

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2586810

zbMATH Keywords

finite structureslocal propertiesunary quantifierslocality of queriesinfinitary extensions of first-order logiclocality on structures of small degree

Mathematics Subject Classification ID

Classical first-order logic (03B10) Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Other infinitary logic (03C75)

Related Items (12)

A logical approach to locality in pictures languages ⋮ An existential locality theorem ⋮ Property Testing for Bounded Degree Databases ⋮ Solutions and query rewriting in data exchange ⋮ Analysis and application of adaptive sampling ⋮ Expressive power of SQL. ⋮ Incremental recomputation in local languages. ⋮ Unnamed Item ⋮ On the locality of arb-invariant first-order formulas with modulo counting quantifiers ⋮ Game-based notions of locality over finite models ⋮ Local properties of query languages ⋮ Lower bounds for invariant queries in logics with counting.

Cites Work

• Unnamed Item
• Unnamed Item
• Proceedings of the Herbrand Symposium. Logic Colloquium '81, held in Marseille, France, July 1981
• Counting quantifiers, successor relations, and logarithmic space
• Query languages for bags and aggregate functions
• Logical hierarchies in PTIME
• Generalized quantifiers and pebble games on finite structures
• On monadic NP vs monadic co-NP
• On winning Ehrenfeucht games and monadic NP
• On uniformity within \(NC^ 1\)
• On winning strategies with unary quantifiers

This page was built for publication: Notions of locality and their logical characterizations over finite models