The succinctness of first-order logic on linear orders

Martin Grohe; Nicole Schweikardt

doi:10.2168/LMCS-1(1:6)2005

Martin Grohe ; Nicole Schweikardt - The succinctness of first-order logic on linear orders

lmcs:2276 - Logical Methods in Computer Science, June 29, 2005, Volume 1, Issue 1 - https://doi.org/10.2168/LMCS-1(1:6)2005

The succinctness of first-order logic on linear ordersArticle

Authors: 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 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.

https://doi.org/10.2168/LMCS-1(1:6)2005

Source: arXiv.org:cs/0502047

Volume: Volume 1, Issue 1

Published on: June 29, 2005

Submitted on: November 4, 2004

Keywords: Computer Science - Logic in Computer Science,F.4.1

Licence: arXiv.org - Assumed non-exclusive license to distribute

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Bibliographic References

21 Documents citing this article

Petar Iliev, 2022, On semantically labelled syntax trees and the non-existence of certain Sahlqvist formulae, Logic Journal of IGPL, 31, 3, pp. 483-509, 10.1093/jigpal/jzac044.

Yoshiki Nakamura, 2022, Expressive power and succinctness of the positive calculus of binary relations, Journal of Logical and Algebraic Methods in Programming, 127, pp. 100760, 10.1016/j.jlamp.2022.100760, https://doi.org/10.1016/j.jlamp.2022.100760.

Ronald Fagin;Jonathan Lenchner;Kenneth W. Regan;Nikhil Vyas, arXiv (Cornell University), Multi-Structural Games and Number of Quantifiers, 2021, Rome, Italy, 10.1109/lics52264.2021.9470756, https://arxiv.org/abs/2104.14709.

Yoshiki Nakamura, Lecture notes in computer science, Expressive Power and Succinctness of the Positive Calculus of Relations, pp. 204-220, 2020, 10.1007/978-3-030-43520-2_13.

Christoph Berkholz;Hubie Chen, Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Compiling Existential Positive Queries to Bounded-Variable Fragments, 2019, Amsterdam Netherlands, 10.1145/3294052.3319693.

Lauri T Hella;Miikka S Vilander, 2019, Formula size games for modal logic and μ-calculus, arXiv (Cornell University), 29, 8, pp. 1311-1344, 10.1093/logcom/exz025, https://arxiv.org/abs/1912.08715.

Oleg Verbitsky;Maksim Zhukovskii, 2019, Tight Bounds on the Asymptotic Descriptive Complexity of Subgraph Isomorphism, arXiv (Cornell University), 20, 2, pp. 1-18, 10.1145/3303881, http://arxiv.org/abs/1802.02143.

German Regis;Renzo Degiovanni;Nicolas D'Ippolito;Nazareno Aguirre, 2015 IEEE/ACM 37th IEEE International Conference on Software Engineering, Specifying Event-Based Systems with a Counting Fluent Temporal Logic, 2015, Florence, Italy, 10.1109/icse.2015.86.

H. van Ditmarsch;P. Iliev, 2015, The succinctness of the cover modality, Journal of Applied Non-Classical Logics, 25, 4, pp. 373-405, 10.1080/11663081.2016.1144016.

Timos Antonopoulos;Paul Hunter;Shahab Raza;James Worrell, Lecture notes in computer science, Three Variables Suffice for Real-Time Logic, pp. 361-374, 2015, 10.1007/978-3-662-46678-0_23, https://doi.org/10.1007/978-3-662-46678-0_23.

Hubie Chen, 2014, On the complexity of existential positive queries, BIROn (Birkbeck, University of London), 15, 1, pp. 1-20, 10.1145/2559946, https://eprints.bbk.ac.uk/id/eprint/21941/1/1206.3902.pdf.

Tim French;Wiebe van der Hoek;Petar Iliev;Barteld Kooi, 2013, On the succinctness of some modal logics, Artificial Intelligence, 197, pp. 56-85, 10.1016/j.artint.2013.02.003, https://doi.org/10.1016/j.artint.2013.02.003.

Wouter Gelade;Frank Neven, 2012, Succinctness of the Complement and Intersection of Regular Expressions, 13, 1, pp. 1-19, 10.1145/2071368.2071372, https://hal.archives-ouvertes.fr/hal-00226864.

Oleg Pikhurko;Oleg Verbitsky, 2011, Logical complexity of graphs: A survey, Contemporary mathematics - American Mathematical Society, pp. 129-179, 10.1090/conm/558/11050, https://doi.org/10.1090/conm/558/11050.

Ahmet Kara;Volker Weber;Martin Lange;Thomas Schwentick, arXiv (Cornell University), On the Hybrid Extension of CTL and CTL +, pp. 427-438, 2009, 10.1007/978-3-642-03816-7_37, https://arxiv.org/abs/0906.2541.

Anthony Widjaja To, Lecture notes in computer science, Model Checking FO(R) over One-Counter Processes and beyond, pp. 485-499, 2009, 10.1007/978-3-642-04027-6_35.

Maarten Marx, Lecture notes in computer science, Logical Foundations of XML and XQuery, pp. 111-157, 2009, 10.1007/978-3-642-03754-2_3.

Manfred Kufleitner;Pascal Weil, On FO 2 Quantifier Alternation over Words, pp. 513-524, 2009, 10.1007/978-3-642-03816-7_44, https://hal.archives-ouvertes.fr/hal-00376640.

Philipp Weis;Neil Immerman, 2009, Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words, Logical Methods in Computer Science, Volume 5, Issue 3, 10.2168/lmcs-5(3:4)2009, https://doi.org/10.2168/lmcs-5(3:4)2009.

Balder ten Cate;Maarten Marx, 2007, Navigational XPath, ACM SIGMOD Record, 36, 2, pp. 19-26, 10.1145/1328854.1328858.

P. Weis;N. Immerman, ScholarWorks@UMassAmherst (University of Massachusetts Amherst), Structure Theorem and Strict Alternation Hierarchy for FO2 on Words, pp. 343-357, 2007, 10.1007/978-3-540-74915-8_27, https://works.bepress.com/cgi/viewcontent.cgi?article=1008&context=neil_immerman.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 1793 times.

This article's PDF has been downloaded 531 times.