Extensions of MSO and the monadic counting hierarchy
| Autor: | Juha Kontinen, Hannu Niemistö |
|---|---|
| Rok vydání: | 2011 |
| Předmět: |
Discrete mathematics
Unary operation Hierarchy (mathematics) 010102 general mathematics Counting hierarchy 0102 computer and information sciences Extension (predicate logic) 16. Peace & justice 01 natural sciences Monadic predicate calculus Computer Science Applications Theoretical Computer Science First-order logic Quantifier (logic) Computational Theory and Mathematics Fragment (logic) 010201 computation theory & mathematics Second-order generalized quantifier Majority quantifier Monadic second-order logic 0101 mathematics Presburger arithmetic Information Systems Mathematics |
| Zdroj: | Information and Computation. 209:1-19 |
| ISSN: | 0890-5401 |
| DOI: | 10.1016/j.ic.2010.09.002 |
| Popis: | In this paper, we study the expressive power of the extension of first-order logic by the unary second-order majority quantifier Most1. In 1 it was shown that the extension of FO by second-order majority quantifiers of all arities describes exactly the problems in the counting hierarchy. We consider first certain sublogics of FO(Most1) over unary vocabularies. We show that over unary vocabularies the logic MSO(R), where MSO is monadic second-order logic and R is the first-order Rescher quantifier, can be characterized by Presburger arithmetic, whereas the logic MSO(Rn)n∈Z+, where Rn is the nth vectorization of R, corresponds to the Δ0-fragment of arithmetic. Then we show that FO(Most1)⩾MSO(Rn)n∈Z+ and that, on unary vocabularies, FO(Most1) collapses to uniform-TC0. Using this collapse, we show that first-order logic with the binary second-order majority quantifier is strictly more expressive than FO(Most1) over the empty vocabulary. On the other hand, over strings, FO(Most1) is shown to capture the linear fragment of the counting hierarchy. Finally we show that, over non-unary vocabularies, FO(Most1) can express problems complete via first-order reductions for each level of the counting hierarchy. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect