Fragments of Monadic Second-Order Logics Over Word Structures | Zendy

Yassine Hachaı̈chi | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Fragments of Monadic Second-Order Logics Over Word Structures

Author(s) -

Yassine Hachaı̈chi

Publication year - 2005

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2004.05.014

Subject(s) - monadic predicate calculus , fragment (logic) , hierarchy , cardinality (data modeling) , mathematics , closure (psychology) , existentialism , order (exchange) , expressive power , word (group theory) , discrete mathematics , computer science , algorithm , theoretical computer science , description logic , philosophy , geometry , epistemology , higher order logic , finance , economics , market economy , data mining

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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research