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 |