Modal logics and local quantifiers: A zoo in the elementary hierarchy
We study a family of modal logics interpreted on tree-like structures, and featuring local quantifiers ∃kp that bind the proposition p to worlds that are accessible from the current one in at most k steps. We consider a first-order and a second-order semantics for the quantifiers, which enables us t...
Main Authors: | , |
---|---|
Format: | Conference item |
Language: | English |
Published: |
Springer
2022
|
_version_ | 1797106720890159104 |
---|---|
author | Fervari, R Mansutti, A |
author_facet | Fervari, R Mansutti, A |
author_sort | Fervari, R |
collection | OXFORD |
description | We study a family of modal logics interpreted on tree-like structures, and featuring local quantifiers ∃kp that bind the proposition p to worlds that are accessible from the current one in at most k steps. We consider a first-order and a second-order semantics for the quantifiers, which enables us to relate several well-known formalisms, such as hybrid logics, S5Q and graded modal logic. To better stress these connections, we explore fragments of our logics, called herein round-bounded fragments. Depending on whether first or second-order semantics is considered, these fragments populate the hierarchy 2NEXP⊂3NEXP⊂⋯ or the hierarchy 2AEXPpol⊂3AEXPpol⊂⋯, respectively. For formulae up-to modal depth k, the complexity improves by one exponential. |
first_indexed | 2024-03-07T07:05:05Z |
format | Conference item |
id | oxford-uuid:a56b0681-61cd-4a13-8f0c-1759ed214753 |
institution | University of Oxford |
language | English |
last_indexed | 2024-03-07T07:05:05Z |
publishDate | 2022 |
publisher | Springer |
record_format | dspace |
spelling | oxford-uuid:a56b0681-61cd-4a13-8f0c-1759ed2147532022-04-28T10:26:57ZModal logics and local quantifiers: A zoo in the elementary hierarchyConference itemhttp://purl.org/coar/resource_type/c_5794uuid:a56b0681-61cd-4a13-8f0c-1759ed214753EnglishSymplectic ElementsSpringer2022Fervari, RMansutti, AWe study a family of modal logics interpreted on tree-like structures, and featuring local quantifiers ∃kp that bind the proposition p to worlds that are accessible from the current one in at most k steps. We consider a first-order and a second-order semantics for the quantifiers, which enables us to relate several well-known formalisms, such as hybrid logics, S5Q and graded modal logic. To better stress these connections, we explore fragments of our logics, called herein round-bounded fragments. Depending on whether first or second-order semantics is considered, these fragments populate the hierarchy 2NEXP⊂3NEXP⊂⋯ or the hierarchy 2AEXPpol⊂3AEXPpol⊂⋯, respectively. For formulae up-to modal depth k, the complexity improves by one exponential. |
spellingShingle | Fervari, R Mansutti, A Modal logics and local quantifiers: A zoo in the elementary hierarchy |
title | Modal logics and local quantifiers: A zoo in the elementary hierarchy |
title_full | Modal logics and local quantifiers: A zoo in the elementary hierarchy |
title_fullStr | Modal logics and local quantifiers: A zoo in the elementary hierarchy |
title_full_unstemmed | Modal logics and local quantifiers: A zoo in the elementary hierarchy |
title_short | Modal logics and local quantifiers: A zoo in the elementary hierarchy |
title_sort | modal logics and local quantifiers a zoo in the elementary hierarchy |
work_keys_str_mv | AT fervarir modallogicsandlocalquantifiersazoointheelementaryhierarchy AT mansuttia modallogicsandlocalquantifiersazoointheelementaryhierarchy |