Swap logic
Fil: Areces, Carlos Eduardo. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física; Argentina.
| Main Authors: | , , |
|---|---|
| Format: | submittedVersion |
| Language: | eng |
| Published: |
2021
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/11086/20427 https://doi.org/10.1093/jigpal/jzt030 |
| _version_ | 1801216224523190272 |
|---|---|
| author | Areces, Carlos Eduardo Fervari, Raúl Alberto Hoffmann, Guillaume Emmanuel |
| author_facet | Areces, Carlos Eduardo Fervari, Raúl Alberto Hoffmann, Guillaume Emmanuel |
| author_sort | Areces, Carlos Eduardo |
| collection | Repositorio Digital Universitario |
| description | Fil: Areces, Carlos Eduardo. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física; Argentina. |
| format | submittedVersion |
| id | rdu-unc.20427 |
| institution | Universidad Nacional de Cordoba |
| language | eng |
| publishDate | 2021 |
| record_format | dspace |
| spelling | rdu-unc.204272022-10-13T11:06:23Z Swap logic Areces, Carlos Eduardo Fervari, Raúl Alberto Hoffmann, Guillaume Emmanuel Modal logic Dynamic logics Expressivity Complexity submittedVersion Fil: Areces, Carlos Eduardo. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física; Argentina. Fil: Areces, Carlos Eduardo. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Fil: Fervari, Raúl Alberto. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física; Argentina. Fil: Hoffmann, Guillaume Emmanuel. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física; Argentina. We investigate dynamic modal operators that can change the model during evaluation. We define the logic SL by extending the basic modal language with the ♦ modality, which is a diamond operator that in addition has the ability to invert pairs of related elements in the domain while traversing an edge of the accessibility relation. SL is very expressive: it fails to have the finite and the tree model property. We show that SL is equivalent to a fragment of first-order logic by providing a satisfiability preserving translation. In addition, we provide an equivalence preserving translation from SL to the hybrid logic H(:, ↓). We also define a suitable notion of bisimulation for SL and investigate its expressive power, showing that it lies strictly between the basic modal logic and H(:, ↓). We finally show that its model checking problem is PSpace-complete and its satisfiability problem is undecidable. http://dx.doi.org/10.1093/jigpal/jzt030 submittedVersion Fil: Areces, Carlos Eduardo. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física; Argentina. Fil: Areces, Carlos Eduardo. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Fil: Fervari, Raúl Alberto. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física; Argentina. Fil: Hoffmann, Guillaume Emmanuel. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física; Argentina. Ciencias de la Computación 2021-09-22T20:15:32Z 2021-09-22T20:15:32Z 2014 article Areces, C. E., Fervari, R. A. y Hoffmann, G. E. (2014). Swap logic. Logic Journal of the Interest Group in Pure and Applied Logic, 22 (2), 309-332. http://dx.doi.org/10.1093/jigpal/jzt030 http://hdl.handle.net/11086/20427 https://doi.org/10.1093/jigpal/jzt030 eng Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/ Impreso; Electrónico y/o Digital ISSN 1367-0751 |
| spellingShingle | Modal logic Dynamic logics Expressivity Complexity Areces, Carlos Eduardo Fervari, Raúl Alberto Hoffmann, Guillaume Emmanuel Swap logic |
| title | Swap logic |
| title_full | Swap logic |
| title_fullStr | Swap logic |
| title_full_unstemmed | Swap logic |
| title_short | Swap logic |
| title_sort | swap logic |
| topic | Modal logic Dynamic logics Expressivity Complexity |
| url | http://hdl.handle.net/11086/20427 https://doi.org/10.1093/jigpal/jzt030 |
| work_keys_str_mv | AT arecescarloseduardo swaplogic AT fervariraulalberto swaplogic AT hoffmannguillaumeemmanuel swaplogic |