{"docId":2276,"paperId":2276,"url":"https:\/\/lmcs.episciences.org\/2276","doi":"10.2168\/LMCS-1(1:6)2005","journalName":"Logical Methods in Computer Science","issn":"","eissn":"1860-5974","volume":[{"vid":106,"name":"Volume 1, Issue 1"}],"section":[],"repositoryName":"arXiv","repositoryIdentifier":"cs\/0502047","repositoryVersion":3,"repositoryLink":"https:\/\/arxiv.org\/abs\/cs\/0502047v3","dateSubmitted":"2004-11-04 00:00:00","dateAccepted":null,"datePublished":"2005-06-29 00:00:00","titles":["The succinctness of first-order logic on linear orders"],"authors":["Grohe, Martin","Schweikardt, Nicole"],"abstracts":["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."],"keywords":["Computer Science - Logic in Computer Science","F.4.1"]}