Defining Long Words Succinctly in FO and MSO

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


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 languageEnglish
Title of host publicationRevolutions and Revelations in Computability
Subtitle of host publication18th Conference on Computability in Europe, CiE 2022, Swansea, UK, July 11–15, 2022, Proceedings
EditorsUlrich Berger, Johanna N.Y. Franklin, Florin Manea, Arno Pauly
Number of pages14
ISBN (Electronic)978-3-031-08740-0
Publication statusPublished - 2022
Publication typeA4 Article in conference proceedings
EventConference on Computability in Europe -
Duration: 11 Jul 202215 Jul 2022

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceConference on Computability in Europe

Publication forum classification

  • Publication forum level 1


Dive into the research topics of 'Defining Long Words Succinctly in FO and MSO'. Together they form a unique fingerprint.

Cite this