TY  - JOUR
A1  - Grohe, Martin
A1  - Schweikardt, Nicole
T1  - The succinctness of first-order logic on linear orders
T2  - Logical methods in computer science
N2  - 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.
KW  - finite model theory
KW  - first-order logic
KW  - succinctness
KW  - Computer science
KW  - Logic in computer science
KW  - F.4.1
Y1  - 2011
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/12553
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-125535
SN  - 1860-5974
N1  - This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/2.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.
VL  - 1
IS  - 1, Art. 6
SP  - 1
EP  - 25
PB  - Department of Theoretical Computer Science, Technical University of Braunschweig
CY  - Braunschweig
ER  -