Fragments of Monadic Second-Order Logics Over Word Structures
Yassine Hachaı̈chi · Electronic Notes in Theoretical Computer Science · 2005
In this paper, we explore the expressive power of fragments of monadic second-order logic enhanced with some generalized quantifiers of comparison of cardinality over finite 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.