Paper Info
Title
Logics with Rank Operators
Abstract
We introduce extensions of first-order logic (FO) and fixed-point logic (FP) with operators that compute the rank of a definable matrix. These operators are generalizations of the counting operations in FP+C (i.e. fixed-point logic with counting) that allow us to count the dimension of a definable vector space, rather than just count the cardinality of a definable set. The logics we define have data complexity contained in polynomial time and all known examples of polynomial time queries that are not definable in FP+C are definable in FP+rk, the extension of FP with rank operators. For each prime number p and each positive integer n, we have rank operators rk_p for determining the rank of a matrix over the finite field GF_p defined by a formula over n-tuples. We compare the expressive power of the logics obtained by varying the values p and n can take. In particular, we show that increasing the arity of the operators yields an infinite hierarchy of expressive power. The rank operators are surprisingly expressive, even in the absence of fixed-point operators. We show that FO+rk_p can define deterministic and symmetric transitive closure. This allows us to show that, on ordered structures, FO+rk_p captures the complexity class MOD_pL, for all prime values of p.
Year
DOI
Venue
2009
10.1109/LICS.2009.24
LICS
Keywords
Field
DocType
polynomials,formal logic,polynomial time,data mining,prime number,expressive power,finite field,vector space,first order logic,turing machines,linear systems,transitive closure,fixed point,complexity class
Rank (linear algebra),Prime (order theory),Complexity class,Discrete mathematics,Combinatorics,Finite field,Arity,Operator (computer programming),Transitive closure,Definable set,Mathematics
Conference
ISSN
Citations 
PageRank 
1043-6871
11
0.65
References 
Authors
17
4
Name
Order
Citations
PageRank
anuj dawar188377.18
Martin Grohe22280127.40
Bjarki Holm3262.61
Bastian Laubner4312.14