10.2168/LMCS-1(1:6)2005
https://lmcs.episciences.org/2276
Grohe, Martin
Martin
Grohe
Schweikardt, Nicole
Nicole
Schweikardt
The succinctness of first-order logic on linear orders
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 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.
episciences.org
Computer Science - Logic in Computer Science
F.4.1
2022-05-21
2005-06-29
2005-06-29
eng
journal article
arXiv:cs/0502047
10.48550/arXiv.cs/0502047
1860-5974
https://lmcs.episciences.org/2276/pdf
VoR
application/pdf
Logical Methods in Computer Science
Volume 1, Issue 1
Researchers
Students