Logic in Computer Science (LICS 1999)

Paper: Logics with Counting, Auxiliary Relations, and Lower Bounds for Invariant Queries (at LICS 1999)

Authors: Leonid Libkin

Abstract

We study the expressive power of counting logics in the presence of auxiliary relations such as orders and preorders. The simplest such logic, first-order with counting, captures the complexity class TC0 over ordered structures. We also consider first-order logic with arbitrary unary quantifiers, and infinitary extensions.The main result of the paper is that all the counting logics above, in the presence of pre-orders that are almost-everywhere linear orders, exhibit a very tame behavior normally associated with first-order properties of unordered structures. This is in sharp contrast with the expressiveness of these logics in the presence of linear orders: such a tame behavior is not the case even for first-order logic with counting, and the most powerful logic we consider can express {every} property of ordered structures. The results attest to the difficulty of proving separation results for the ordered case, in particular, to proving the separation of TC0 from NP. To prove the main results, we use locality techniques from finite-model theory, modifying the main notions of locality along the way.

BibTeX

  @InProceedings{Libkin-LogicswithCountingA,
    author = 	 {Leonid Libkin},
    title = 	 {Logics with Counting, Auxiliary Relations, and Lower Bounds for Invariant Queries},
    booktitle =  {Proceedings of the Fourteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1999},
    year =	 1999,
    editor =	 {Giuseppe Longo},
    month =	 {July}, 
    pages =      {316--325},
    location =   {Trento, Italy}, 
    publisher =	 {IEEE Computer Society Press}
  }