Fragments of Monadic Second-Order Logics Over Word Structures

The full monadic second-order fragment of the logics that we study correspond to the famous linear hierarchy, see [Y. Hachaïchi, A descriptive complexity approach to the linear hierarchy, Theoretical Computer Science 304 (2003) 421-429], and their existential fragments characterize some sequential recognizers. We prove that the first-order closure of the existential fragments of these logics is strictly beyond the existential fragments.