episciences.org_2276_1653105066
1653105066
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Logical Methods in Computer Science
18605974
06
29
2005
Volume 1, Issue 1
The succinctness of firstorder logic on linear orders
Martin
Grohe
Nicole
Schweikardt
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.
06
29
2005
2276
arXiv:cs/0502047
10.48550/arXiv.cs/0502047
10.2168/LMCS1(1:6)2005
https://lmcs.episciences.org/2276

https://lmcs.episciences.org/2276/pdf