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

Computing Sciences

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

7 Downloads (Pure)

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öwenheim-Skolem and Hanf numbers of these logics on words and obtain similar bounds for these as well.

Original language	English
Title of host publication	Revolutions and Revelations in Computability
Subtitle of host publication	18th Conference on Computability in Europe, CiE 2022, Swansea, UK, July 11–15, 2022, Proceedings
Editors	Ulrich Berger, Johanna N.Y. Franklin, Florin Manea, Arno Pauly
Publisher	Springer
Pages	125-138
Number of pages	14
ISBN (Electronic)	978-3-031-08740-0
DOIs	https://doi.org/10.1007/978-3-031-08740-0_11
Publication status	Published - 2022
Publication type	A4 Article in conference proceedings
Event	Conference on Computability in Europe - Duration: 11 Jul 2022 → 15 Jul 2022

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	13359
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

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

Publication forum classification

Publication forum level 1

Access to Document

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

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

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

Cite this

Hella, L., & Vilander, M. (2022). Defining Long Words Succinctly in FO and MSO. In U. Berger, J. N. Y. Franklin, F. Manea, & A. Pauly (Eds.), Revolutions and Revelations in Computability: 18th Conference on Computability in Europe, CiE 2022, Swansea, UK, July 11–15, 2022, Proceedings (pp. 125-138). (Lecture Notes in Computer Science; Vol. 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. editor / Ulrich Berger ; Johanna N.Y. Franklin ; Florin Manea ; Arno Pauly. Springer, 2022. pp. 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. in U Berger, JNY Franklin, F Manea & A Pauly (eds), 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, vol. 13359, Springer, pp. 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. ed. / Ulrich Berger; Johanna N.Y. Franklin; Florin Manea; Arno Pauly. Springer, 2022. p. 125-138 (Lecture Notes in Computer Science; Vol. 13359).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

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 -