A characterization of definability of second-order generalized quantifiers with applications to non-definability
| Authors |
|
|---|---|
| Publication date | 09-2014 |
| Journal | Journal of Computer and System Sciences |
| Volume | Issue number | 80 | 6 |
| Pages (from-to) | 1152-1162 |
| Organisations |
|
| Abstract | We study definability of second-order generalized quantifiers. We show that the question whether a second-order generalized quantifier Q1 is definable in terms of another quantifier Q2, the base logic being monadic second-order logic, reduces to the question if a quantifier Q1⋆ is definable in FO(Q2⋆,<,+,×) for certain first-order quantifiers Q1⋆ and Q2⋆. We use our characterization to show new definability and non-definability results for second-order generalized quantifiers. We also show that the monadic second-order majority quantifier Most1 is not definable in second-order logic. |
| Document type | Article |
| Note | In special issue: 18th Workshop on Logic, Language, Information and Computation (WoLLIC 2011) |
| Language | English |
| Published at |
https://doi.org/10.1016/j.jcss.2014.04.007
(Final published version)
|
| Permalink to this page | |
