| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 9655952 | Electronic Notes in Theoretical Computer Science | 2005 | 13 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yassine Hachaïchi,