Lower bounds for invariant queries in logics with counting

We study the expressive power of counting logics in the presence of auxiliary rela-tions such as orders and preorders. The simplest such logic is the rst-order logic with counting. This logic captures the complexity class TC 0 over ordered struc-tures. We also consider rst-order logic with arbitrary unary quantiers and with in nitary extensions. We start by giving a simple direct proof that rst-order logic with counting, in the presence of pre-orders that are almost-everywhere linear orders, cannot express the transitive closure of a binary relation. The proof is based on locality of formulae. We then show that the technique cannot be extended to linear orders. We further show that this result does not say anything about the power of invariant queries in rst-order logic with counting vs. the class TC 0, in the presence of these preorders. In the second part of the paper, we prove a separation result showing that, for all the counting logics above, a linear order is more powerful than a preorder that is a linear order almost everywhere. In fact, we prove that the expressive power of invariant queries in the presence of such preorders can be characterized by a property normally associated with rst-order denability over unordered structures. We do this by using locality techniques from nite-model theory. However, as some standard notions of locality fail in this setting, we have to modify them to prove the main result. Corresponding author