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 |