## Paper: On Counting Logics and Local Properties (at LICS 1998)

**Leonid Libkin**

### Abstract

The expressive power of first-order logic over finite structures
is limited in two ways: it lacks a recursion mechanism, and it cannot
count. Overcoming the first limitation has been a subject of extensive
study. A number of fixpoint logics have been introduced, and shown to be
subsumed by an infinitary logic L_{∞ω}^{ω
}. This logic is easier to analyze than fixpoint logics, and it
still lacks counting power, as it has a 0-1 law. On the counting side,
there is no analog of L_{∞ω}^{ω}.
There are a number of logics with counting power, usually introduced via
generalized quantifiers. Most known expressivity bounds are based on the
fact that counting extensions of first-order logic preserve the locality
properties. This paper has three main goals. First, we introduce a new
logic L_{∞ω}*(C) that plays the same role for
counting as L_{∞ω}^{ω} does for
recursion-it subsumes a number of extensions of first-order logic with
counting, and has nice properties that make it easy to study. Second, we
give a simple direct proof that L_{∞ω}*(C) expresses
only local properties: those that depend on the properties of small
neighborhoods, but cannot grasp a structure as a whole. This is a
general way of saying that a logic lacks a recursion mechanism. Third,
we consider a finer analysis of locality of counting logics. In
particular, we address the question of how local a logic is, that is,
how big are those neighborhoods that local properties depend on. We get
a uniform answer for a variety of logics between first-order and
L_{∞ω}*(C). This is done by introducing a new form
of locality that captures the tightest condition that the duplicator
needs to maintain in order to win a game. We use this technique to give
bounds on outputs of L_{∞ω}*(C)-definable queries.
We also specialize some of the results for structures of small degree

### BibTeX

@InProceedings{Libkin-OnCountingLogicsand, author = {Leonid Libkin}, title = {On Counting Logics and Local Properties}, booktitle = {Proceedings of the Thirteenth Annual IEEE Symposium on Logic in Computer Science (LICS 1998)}, year = {1998}, month = {June}, pages = {501--512}, location = {Indianapolis, IN, USA}, publisher = {IEEE Computer Society Press} }