Decidable first-order modal logics with counting quantifiers

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

6 Citations (Scopus)
63 Downloads (Pure)

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’.
Original languageEnglish
Title of host publicationAdvances in Modal Logic
Number of pages19
Volume11
Publication statusPublished - 18 May 2016
EventAdvances in Modal Logic 2016 - Budapest, Hungary
Duration: 29 Aug 20162 Sept 2016
http://phil.elte.hu/aiml2016/

Conference

ConferenceAdvances in Modal Logic 2016
Abbreviated titleAiML 2016
Country/TerritoryHungary
CityBudapest
Period29/08/20162/09/2016
Internet address

Fingerprint

Dive into the research topics of 'Decidable first-order modal logics with counting quantifiers'. Together they form a unique fingerprint.

Cite this