{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T19:47:28Z","timestamp":1762458448469,"version":"3.41.2"},"reference-count":18,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2005,6,29]],"date-time":"2005-06-29T00:00:00Z","timestamp":1120003200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/assumed-1991-2003"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Succinctness is a natural measure for comparing the strength of different\nlogics. Intuitively, a logic L_1 is more succinct than another logic L_2 if all\nproperties that can be expressed in L_2 can be expressed in L_1 by formulas of\n(approximately) the same size, but some properties can be expressed in L_1 by\n(significantly) smaller formulas.\n  We study the succinctness of logics on linear orders. Our first theorem is\nconcerned with the finite variable fragments of first-order logic. We prove\nthat:\n  (i) Up to a polynomial factor, the 2- and the 3-variable fragments of\nfirst-order logic on linear orders have the same succinctness. (ii) The\n4-variable fragment is exponentially more succinct than the 3-variable\nfragment. Our second main result compares the succinctness of first-order logic\non linear orders with that of monadic second-order logic. We prove that the\nfragment of monadic second-order logic that has the same expressiveness as\nfirst-order logic on linear orders is non-elementarily more succinct than\nfirst-order logic.<\/jats:p>","DOI":"10.2168\/lmcs-1(1:6)2005","type":"journal-article","created":{"date-parts":[[2005,7,13]],"date-time":"2005-07-13T12:15:47Z","timestamp":1121256947000},"source":"Crossref","is-referenced-by-count":20,"title":["The succinctness of first-order logic on linear orders"],"prefix":"10.46298","volume":"Volume 1, Issue 1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0292-9142","authenticated-orcid":false,"given":"Martin","family":"Grohe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicole","family":"Schweikardt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2005,6,29]]},"reference":[{"key":"10.2168\/LMCS-1(1:6)2005_adlimm01","doi-asserted-by":"publisher","DOI":"10.1145\/772062.772064"},{"key":"10.2168\/LMCS-1(1:6)2005_aleimm00","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/8.3.325"},{"year":"1999","author":"Ebbinghaus","key":"10.2168\/LMCS-1(1:6)2005_EbbinghausFlum"},{"key":"10.2168\/LMCS-1(1:6)2005_etevarwil02","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.2953"},{"key":"10.2168\/LMCS-1(1:6)2005_FrickGrohe_JournalVersionOfLICS02","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2004.01.007"},{"key":"10.2168\/LMCS-1(1:6)2005_frigrokoc03","doi-asserted-by":"crossref","unstructured":"M. Frick, M. Grohe, and C. Koch. Query evaluation on compressed trees. InProceedings of the 18th IEEE Symposium on Logic in Computer Science (LICS'03), pages 188-197, 2003.","DOI":"10.1109\/LICS.2003.1210058"},{"key":"10.2168\/LMCS-1(1:6)2005_gotkoc04","doi-asserted-by":"publisher","DOI":"10.1145\/962446.962450"},{"key":"10.2168\/LMCS-1(1:6)2005_GroheSchweikardt_CSL03","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2004017"},{"key":"10.2168\/LMCS-1(1:6)2005_GS_LICS04","doi-asserted-by":"crossref","unstructured":"M. Grohe and N. Schweikardt. The succinctness of first-order logic on linear orders. InProceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS'04), pages 438-447, 2004.","DOI":"10.1109\/LICS.2004.1319638"},{"year":"1999","author":"Immerman","key":"10.2168\/LMCS-1(1:6)2005_Immerman"},{"key":"10.2168\/LMCS-1(1:6)2005_kam68","unstructured":"H. Kamp.Tense Logic and the theory of linear order. PhD thesis, University of California, Los Angeles, 1968."},{"year":"2004","author":"Libkin","key":"10.2168\/LMCS-1(1:6)2005_Libkin_FMT-textbook"},{"key":"10.2168\/LMCS-1(1:6)2005_nev99","unstructured":"F. Neven.Design and Analysis of Query Languages for Structured Documents - A Formal and Logical Approach. PhD thesis, Limburgs Universitair Centrum, 1999."},{"key":"10.2168\/LMCS-1(1:6)2005_nevschwe99","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00301-2"},{"key":"10.2168\/LMCS-1(1:6)2005_sto74","unstructured":"L. J. Stockmeyer.The Complexity of Decision Problems in Automata Theory. PhD thesis, Department of Electrical Engineering, MIT, 1974."},{"key":"10.2168\/LMCS-1(1:6)2005_StockmeyerMeyer","doi-asserted-by":"crossref","unstructured":"L. J. Stockmeyer and A. R. Meyer.Word problems requiring exponential time. InProceedings of the 5th ACM Symposium on Theory of Computing (STOC'73), pages 1-9, 1973.","DOI":"10.1145\/800125.804029"},{"key":"10.2168\/LMCS-1(1:6)2005_var82","doi-asserted-by":"crossref","unstructured":"M. Y. Vardi. The complexity of relational query languages. InProceedings of the 14th ACM Symposium on Theory of Computing (STOC'82), pages 137-146, 1982.","DOI":"10.1145\/800070.802186"},{"key":"10.2168\/LMCS-1(1:6)2005_wil99","doi-asserted-by":"crossref","unstructured":"T. Wilke. CTL+is exponentially more succinct than CTL. InProceedings of the 19th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'99), volume 1738 ofLecture Notes in Computer Science, pages 110-121. Springer, 1999.","DOI":"10.1007\/3-540-46691-6_9"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/2276\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/2276\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:11:29Z","timestamp":1681243889000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/2276"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6,29]]},"references-count":18,"URL":"https:\/\/doi.org\/10.2168\/lmcs-1(1:6)2005","relation":{"references":[{"id-type":"doi","id":"10.1051\/ita:2004017","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"cs\/0502047","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.cs\/0502047","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2005,6,29]]},"article-number":"2276"}}