| Authors |
|
| Publication date |
09-2014
|
| Journal |
Journal of Computer and System Sciences
|
| Volume | Issue number |
80 | 6
|
| Pages (from-to) |
1152-1162
|
| Organisations |
-
Faculty of Humanities (FGw)
-
Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
|
| 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
|
|
Permalink to this page
|
