Hybrid Modal Operators for Definite Descriptions
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910648967888896 |
|---|---|
| author | Wałęga, Przemysław Andrzej Zawidzki, Michał |
| author_facet | Wałęga, Przemysław Andrzej Zawidzki, Michał |
| contents | In this paper, we study computational complexity and expressive power of modal operators for definite descriptions, which correspond to statements `the modal world which satisfies formula \(varphi\)'. We show that adding such operators to the basic (propositional) modal language has a price of increasing complexity of the satisfiability problem from PSpace to ExpTime. However, if formulas corresponding to descriptions are Boolean only, there is no increase of complexity. Furthermore, we compare definite descriptions with the related operators from hybrid and counting logics. We prove that the operators for definite descriptions are strictly more expressive than hybrid operators, but strictly less expressive than counting operators. We show that over linear structures the same expressive power results hold as in the general case; in contrast, if the linear structures are isomorphic to integers, definite descriptions become as expressive as counting operators. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_10439 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hybrid Modal Operators for Definite Descriptions Wałęga, Przemysław Andrzej Zawidzki, Michał Logic in Computer Science In this paper, we study computational complexity and expressive power of modal operators for definite descriptions, which correspond to statements `the modal world which satisfies formula \(varphi\)'. We show that adding such operators to the basic (propositional) modal language has a price of increasing complexity of the satisfiability problem from PSpace to ExpTime. However, if formulas corresponding to descriptions are Boolean only, there is no increase of complexity. Furthermore, we compare definite descriptions with the related operators from hybrid and counting logics. We prove that the operators for definite descriptions are strictly more expressive than hybrid operators, but strictly less expressive than counting operators. We show that over linear structures the same expressive power results hold as in the general case; in contrast, if the linear structures are isomorphic to integers, definite descriptions become as expressive as counting operators. |
| title | Hybrid Modal Operators for Definite Descriptions |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2410.10439 |