
VOLUME 1, ISSUE 1, PAPER 6
The succinctness of firstorder logic on linear orders

©Martin Grohe, HumboldtUniversität zu Berlin ©Nicole Schweikardt, HumboldtUniversität zu Berlin 
Abstract
Succinctness is a natural measure for comparing the strength of different
logics. Intuitively, a logic L_1 is more succinct than another logic L_2 if all
properties that can be expressed in L_2 can be expressed in L_1 by formulas of
(approximately) the same size, but some properties can be expressed in L_1 by
(significantly) smaller formulas.
We study the succinctness of logics on linear orders. Our first theorem is
concerned with the finite variable fragments of firstorder logic. We prove
that:
(i) Up to a polynomial factor, the 2 and the 3variable fragments of
firstorder logic on linear orders have the same succinctness. (ii) The
4variable fragment is exponentially more succinct than the 3variable
fragment. Our second main result compares the succinctness of firstorder logic
on linear orders with that of monadic secondorder logic. We prove that the
fragment of monadic secondorder logic that has the same expressiveness as
firstorder logic on linear orders is nonelementarily more succinct than
firstorder logic.

Publication date: June 29, 2005
Full Text: PDF  PostScript DOI: 10.2168/LMCS1(1:6)2005
Hit Counts: 20767 
Creative Commons  