DocumentCode :
1959782
Title :
On counting logics and local properties
Author :
Libkin, Leonid
Author_Institution :
Bell Labs., Murray Hill, NJ, USA
fYear :
1998
fDate :
21-24 Jun 1998
Firstpage :
501
Lastpage :
512
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
Keywords :
formal logic; 0-1 law; expressive power; finite structures; first-order logic; fixpoint logics; generalized quantifiers; infinitary logic; locality properties; recursion mechanism; Aggregates; Collaboration; Computational modeling; Counting circuits; Database languages; Logic;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Logic in Computer Science, 1998. Proceedings. Thirteenth Annual IEEE Symposium on
Conference_Location :
Indianapolis, IN
ISSN :
1043-6871
Print_ISBN :
0-8186-8506-9
Type :
conf
DOI :
10.1109/LICS.1998.705683
Filename :
705683
Link To Document :
بازگشت