# IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

# Logic in Computer Science (LICS 2004)

## Paper: The Succinctness of First-Order Logic on Linear Orders (at LICS 2004)

Authors: Martin Grohe Nicole Schweikardt

### Abstract

Succinctness is a natural measure for comparing the strength of different logics. Intuitively, a logic L₁ is more succinct than another logic L₂ if all properties that can be expressed in L₂ can be expressed in L₁ by formulas of (approximately) the same size, but some properties can be expressed in L₁ by (significantly) smaller formulas. We study the succinctness of logics on linear orders that have the same expressive power as first-order logic. Our first theorem is concerned with the finite variable fragments of first-order logic. We prove that: (i) Up to a polynomial factor, the 2- and the 3-variable fragments of first-order logic on linear orders have the same succinctness. (ii) The 4-variable fragment is exponentially more succinct than the 3-variable fragment. Our second main result compares the succinctness of first-order logic on linear orders with that of monadic second-order logic. We prove that the fragment of monadic second-order logic that has the same expressiveness as first-order logic on linear orders is non-elementarily more succinct than first-order logic.

### BibTeX

```  @InProceedings{GroheSchweikardt-TheSuccinctnessofFi,
author = 	 {Martin Grohe and Nicole Schweikardt},
title = 	 {The Succinctness of First-Order Logic on Linear Orders},
booktitle =  {Proceedings of the Nineteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2004)},
year =	 {2004},
month =	 {July},
pages =      {438--447},
location =   {Turku, Finland},
publisher =	 {IEEE Computer Society Press}
}
```