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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2005-06-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/2276/pdf |
| _version_ | 1797269964442304512 |
|---|---|
| author | Martin Grohe Nicole Schweikardt |
| author_facet | Martin Grohe Nicole Schweikardt |
| author_sort | Martin Grohe |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:56:44Z |
| format | Article |
| id | doaj.art-c62bf8d87e9542699d35395c412995d3 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:56:44Z |
| publishDate | 2005-06-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-c62bf8d87e9542699d35395c412995d32024-03-07T17:10:13ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742005-06-01Volume 1, Issue 110.2168/LMCS-1(1:6)20052276The succinctness of first-order logic on linear ordersMartin Grohehttps://orcid.org/0000-0002-0292-9142Nicole SchweikardtSuccinctness 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://lmcs.episciences.org/2276/pdfcomputer science - logic in computer sciencef.4.1 |
| spellingShingle | Martin Grohe Nicole Schweikardt The succinctness of first-order logic on linear orders Logical Methods in Computer Science computer science - logic in computer science f.4.1 |
| title | The succinctness of first-order logic on linear orders |
| title_full | The succinctness of first-order logic on linear orders |
| title_fullStr | The succinctness of first-order logic on linear orders |
| title_full_unstemmed | The succinctness of first-order logic on linear orders |
| title_short | The succinctness of first-order logic on linear orders |
| title_sort | succinctness of first order logic on linear orders |
| topic | computer science - logic in computer science f.4.1 |
| url | https://lmcs.episciences.org/2276/pdf |
| work_keys_str_mv | AT martingrohe thesuccinctnessoffirstorderlogiconlinearorders AT nicoleschweikardt thesuccinctnessoffirstorderlogiconlinearorders AT martingrohe succinctnessoffirstorderlogiconlinearorders AT nicoleschweikardt succinctnessoffirstorderlogiconlinearorders |