Decidability of order-based modal logics
Decidability of the validity problem is established for a family of many-valued modal logics, notably Gödel modal logics, where propositional connectives are evaluated according to the order of values in a complete sublattice of the real unit interval [0,1], and box and diamond modalities are evalua...
Guardado en:
| Publicado: |
2017
|
|---|---|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v88_n_p53_Caicedo http://hdl.handle.net/20.500.12110/paper_00220000_v88_n_p53_Caicedo |
| Aporte de: |
| id |
paper:paper_00220000_v88_n_p53_Caicedo |
|---|---|
| record_format |
dspace |
| spelling |
paper:paper_00220000_v88_n_p53_Caicedo2023-06-08T14:45:03Z Decidability of order-based modal logics Complexity Decidability Finite model property Gödel logics Many-valued logics Modal logics One-variable fragments Computability and decidability Computer circuits Formal logic Semantics Complexity Finite model property Modal logic Np-completeness Pspace completeness Regularity condition Unit intervals Variable fragment Many valued logics Decidability of the validity problem is established for a family of many-valued modal logics, notably Gödel modal logics, where propositional connectives are evaluated according to the order of values in a complete sublattice of the real unit interval [0,1], and box and diamond modalities are evaluated as infima and suprema over (many-valued) Kripke frames. If the sublattice is infinite and the language is sufficiently expressive, then the standard semantics for such a logic lacks the finite model property. It is shown here, however, that, given certain regularity conditions, the finite model property holds for a new semantics for the logic, providing a basis for establishing decidability and PSPACE-completeness. Similar results are also established for S5 logics that coincide with one-variable fragments of first-order many-valued logics. In particular, a first proof is given of the decidability and co-NP-completeness of validity in the one-variable fragment of first-order Gödel logic. © 2017 Elsevier Inc. 2017 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v88_n_p53_Caicedo http://hdl.handle.net/20.500.12110/paper_00220000_v88_n_p53_Caicedo |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Complexity Decidability Finite model property Gödel logics Many-valued logics Modal logics One-variable fragments Computability and decidability Computer circuits Formal logic Semantics Complexity Finite model property Modal logic Np-completeness Pspace completeness Regularity condition Unit intervals Variable fragment Many valued logics |
| spellingShingle |
Complexity Decidability Finite model property Gödel logics Many-valued logics Modal logics One-variable fragments Computability and decidability Computer circuits Formal logic Semantics Complexity Finite model property Modal logic Np-completeness Pspace completeness Regularity condition Unit intervals Variable fragment Many valued logics Decidability of order-based modal logics |
| topic_facet |
Complexity Decidability Finite model property Gödel logics Many-valued logics Modal logics One-variable fragments Computability and decidability Computer circuits Formal logic Semantics Complexity Finite model property Modal logic Np-completeness Pspace completeness Regularity condition Unit intervals Variable fragment Many valued logics |
| description |
Decidability of the validity problem is established for a family of many-valued modal logics, notably Gödel modal logics, where propositional connectives are evaluated according to the order of values in a complete sublattice of the real unit interval [0,1], and box and diamond modalities are evaluated as infima and suprema over (many-valued) Kripke frames. If the sublattice is infinite and the language is sufficiently expressive, then the standard semantics for such a logic lacks the finite model property. It is shown here, however, that, given certain regularity conditions, the finite model property holds for a new semantics for the logic, providing a basis for establishing decidability and PSPACE-completeness. Similar results are also established for S5 logics that coincide with one-variable fragments of first-order many-valued logics. In particular, a first proof is given of the decidability and co-NP-completeness of validity in the one-variable fragment of first-order Gödel logic. © 2017 Elsevier Inc. |
| title |
Decidability of order-based modal logics |
| title_short |
Decidability of order-based modal logics |
| title_full |
Decidability of order-based modal logics |
| title_fullStr |
Decidability of order-based modal logics |
| title_full_unstemmed |
Decidability of order-based modal logics |
| title_sort |
decidability of order-based modal logics |
| publishDate |
2017 |
| url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00220000_v88_n_p53_Caicedo http://hdl.handle.net/20.500.12110/paper_00220000_v88_n_p53_Caicedo |
| _version_ |
1768542971890761728 |