Abstract
In this paper, we examine the computational complexity of various natural one-variable fragments of first-order modal logics with the addition of arbitrary counting quantifiers. The addition of counting quantifiers provides us a rich language with which to succinctly express statements about the quantity of objects satisfying a given property, using only a single variable. We provide optimal upper bounds on the complexity of the decision problem for several one-variable fragments, by establishing the finite model property.
In particular, we show that the decision (validity) problem for the one-variable fragment of the minimal first-order modal logic QK with counting quantifiers is coNExpTime-complete. In the propositional setting, these results also provide optimal upper bounds for many two-dimensional modal logics in which one component is von Wright’s logic of ‘elsewhere’.
In particular, we show that the decision (validity) problem for the one-variable fragment of the minimal first-order modal logic QK with counting quantifiers is coNExpTime-complete. In the propositional setting, these results also provide optimal upper bounds for many two-dimensional modal logics in which one component is von Wright’s logic of ‘elsewhere’.
Original language | English |
---|---|
Title of host publication | Advances in Modal Logic |
Number of pages | 19 |
Volume | 11 |
Publication status | Published - 18 May 2016 |
Event | Advances in Modal Logic 2016 - Budapest, Hungary Duration: 29 Aug 2016 → 2 Sept 2016 http://phil.elte.hu/aiml2016/ |
Conference
Conference | Advances in Modal Logic 2016 |
---|---|
Abbreviated title | AiML 2016 |
Country/Territory | Hungary |
City | Budapest |
Period | 29/08/2016 → 2/09/2016 |
Internet address |