Defining Long Words Succinctly in FO and MSO

Lauri Hella; Miikka Vilander

doi:10.1007/978-3-031-08740-0_11

Defining Long Words Succinctly in FO and MSO

Lauri Hella, Miikka Vilander

Tietotekniikka

Tutkimustuotos: Konferenssiartikkeli › Tieteellinen › vertaisarvioitu

7 Lataukset (Pure)

Abstrakti

We consider the length of the longest word definable in FO and MSO via a formula of size n. For both logics we obtain as an upper bound for this number an exponential tower of height linear in n. We prove this by counting types with respect to a fixed quantifier rank. As lower bounds we obtain for both FO and MSO an exponential tower of height in the order of a rational power of n. We show these lower bounds by giving concrete formulas defining word representations of levels of the cumulative hierarchy of sets. In addition, we consider the Löwenheim-Skolem and Hanf numbers of these logics on words and obtain similar bounds for these as well.

Alkuperäiskieli	Englanti
Otsikko	Revolutions and Revelations in Computability
Alaotsikko	18th Conference on Computability in Europe, CiE 2022, Swansea, UK, July 11–15, 2022, Proceedings
Toimittajat	Ulrich Berger, Johanna N.Y. Franklin, Florin Manea, Arno Pauly
Kustantaja	Springer
Sivut	125-138
Sivumäärä	14
ISBN (elektroninen)	978-3-031-08740-0
DOI - pysyväislinkit	https://doi.org/10.1007/978-3-031-08740-0_11
Tila	Julkaistu - 2022
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisussa
Tapahtuma	Conference on Computability in Europe - Kesto: 11 heinäk. 2022 → 15 heinäk. 2022

Julkaisusarja

Nimi	Lecture Notes in Computer Science
Kustantaja	Springer
Vuosikerta	13359
ISSN (painettu)	0302-9743
ISSN (elektroninen)	1611-3349

Conference

Conference	Conference on Computability in Europe
Ajanjakso	11/07/22 → 15/07/22

Julkaisufoorumi-taso

Jufo-taso 1

Pääsy asiakirjaan

10.1007/978-3-031-08740-0_11Lisenssi: CC BY

978-3-031-08740-0_11Final published version, 326 KBLisenssi: CC BY

https://urn.fi/URN:NBN:fi:tuni-202208086269Lisenssi: CC BY

Siteeraa tätä

Hella, L., & Vilander, M. (2022). Defining Long Words Succinctly in FO and MSO. teoksessa U. Berger, J. N. Y. Franklin, F. Manea, & A. Pauly (Toimittajat), Revolutions and Revelations in Computability: 18th Conference on Computability in Europe, CiE 2022, Swansea, UK, July 11–15, 2022, Proceedings (Sivut 125-138). (Lecture Notes in Computer Science; Vuosikerta 13359). Springer. https://doi.org/10.1007/978-3-031-08740-0_11

Hella, Lauri ; Vilander, Miikka. / Defining Long Words Succinctly in FO and MSO. Revolutions and Revelations in Computability: 18th Conference on Computability in Europe, CiE 2022, Swansea, UK, July 11–15, 2022, Proceedings. Toimittaja / Ulrich Berger ; Johanna N.Y. Franklin ; Florin Manea ; Arno Pauly. Springer, 2022. Sivut 125-138 (Lecture Notes in Computer Science).

@inproceedings{86b2b0a0ccad49c8ba145515bff8a8ec,

title = "Defining Long Words Succinctly in FO and MSO",

abstract = "We consider the length of the longest word definable in FO and MSO via a formula of size n. For both logics we obtain as an upper bound for this number an exponential tower of height linear in n. We prove this by counting types with respect to a fixed quantifier rank. As lower bounds we obtain for both FO and MSO an exponential tower of height in the order of a rational power of n. We show these lower bounds by giving concrete formulas defining word representations of levels of the cumulative hierarchy of sets. In addition, we consider the L{\"o}wenheim-Skolem and Hanf numbers of these logics on words and obtain similar bounds for these as well.",

author = "Lauri Hella and Miikka Vilander",

note = "JUFOID=62555; Conference on Computability in Europe ; Conference date: 11-07-2022 Through 15-07-2022",

year = "2022",

doi = "10.1007/978-3-031-08740-0_11",

language = "English",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "125--138",

editor = "Ulrich Berger and Franklin, {Johanna N.Y.} and Florin Manea and Arno Pauly",

booktitle = "Revolutions and Revelations in Computability",

}

Hella, L & Vilander, M 2022, Defining Long Words Succinctly in FO and MSO. julkaisussa U Berger, JNY Franklin, F Manea & A Pauly (toim), Revolutions and Revelations in Computability: 18th Conference on Computability in Europe, CiE 2022, Swansea, UK, July 11–15, 2022, Proceedings. Lecture Notes in Computer Science, Vuosikerta 13359, Springer, Sivut 125-138, Conference on Computability in Europe, 11/07/22. https://doi.org/10.1007/978-3-031-08740-0_11

Defining Long Words Succinctly in FO and MSO. / Hella, Lauri ; Vilander, Miikka.
Revolutions and Revelations in Computability: 18th Conference on Computability in Europe, CiE 2022, Swansea, UK, July 11–15, 2022, Proceedings. toim. / Ulrich Berger; Johanna N.Y. Franklin; Florin Manea; Arno Pauly. Springer, 2022. s. 125-138 (Lecture Notes in Computer Science; Vuosikerta 13359).

Tutkimustuotos: Konferenssiartikkeli › Tieteellinen › vertaisarvioitu

TY - GEN

T1 - Defining Long Words Succinctly in FO and MSO

AU - Hella, Lauri

AU - Vilander, Miikka

N1 - JUFOID=62555

PY - 2022

Y1 - 2022

N2 - We consider the length of the longest word definable in FO and MSO via a formula of size n. For both logics we obtain as an upper bound for this number an exponential tower of height linear in n. We prove this by counting types with respect to a fixed quantifier rank. As lower bounds we obtain for both FO and MSO an exponential tower of height in the order of a rational power of n. We show these lower bounds by giving concrete formulas defining word representations of levels of the cumulative hierarchy of sets. In addition, we consider the Löwenheim-Skolem and Hanf numbers of these logics on words and obtain similar bounds for these as well.

AB - We consider the length of the longest word definable in FO and MSO via a formula of size n. For both logics we obtain as an upper bound for this number an exponential tower of height linear in n. We prove this by counting types with respect to a fixed quantifier rank. As lower bounds we obtain for both FO and MSO an exponential tower of height in the order of a rational power of n. We show these lower bounds by giving concrete formulas defining word representations of levels of the cumulative hierarchy of sets. In addition, we consider the Löwenheim-Skolem and Hanf numbers of these logics on words and obtain similar bounds for these as well.

U2 - 10.1007/978-3-031-08740-0_11

DO - 10.1007/978-3-031-08740-0_11

M3 - Conference contribution

T3 - Lecture Notes in Computer Science

SP - 125

EP - 138

BT - Revolutions and Revelations in Computability

A2 - Berger, Ulrich

A2 - Franklin, Johanna N.Y.

A2 - Manea, Florin

A2 - Pauly, Arno

PB - Springer

T2 - Conference on Computability in Europe

Y2 - 11 July 2022 through 15 July 2022

ER -

Hella L , Vilander M. Defining Long Words Succinctly in FO and MSO. julkaisussa Berger U, Franklin JNY, Manea F, Pauly A, toimittajat, Revolutions and Revelations in Computability: 18th Conference on Computability in Europe, CiE 2022, Swansea, UK, July 11–15, 2022, Proceedings. Springer. 2022. s. 125-138. (Lecture Notes in Computer Science). doi: 10.1007/978-3-031-08740-0_11