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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Caicedo, X., Metcalfe, G., Rodríguez, R., Rogger, J.
Formato: JOUR
Materias:
Complexity
Decidability
Finite model property
Gödel logics
Many-valued logics
Modal logics
One-variable fragments
Computability and decidability
Computer circuits
Formal logic
Semantics
Modal logic
Np-completeness
Pspace completeness
Regularity condition
Unit intervals
Variable fragment
Many valued logics
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_00220000_v88_n_p53_Caicedo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_00220000_v88_n_p53_Caicedo
record_format dspace
spelling todo:paper_00220000_v88_n_p53_Caicedo2023-10-03T14:25:23Z Decidability of order-based modal logics Caicedo, X. Metcalfe, G. Rodríguez, R. Rogger, J. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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
Caicedo, X.
Metcalfe, G.
Rodríguez, R.
Rogger, J.
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.
format JOUR
author Caicedo, X.
Metcalfe, G.
Rodríguez, R.
Rogger, J.
author_facet Caicedo, X.
Metcalfe, G.
Rodríguez, R.
Rogger, J.
author_sort Caicedo, X.
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
url http://hdl.handle.net/20.500.12110/paper_00220000_v88_n_p53_Caicedo
work_keys_str_mv AT caicedox decidabilityoforderbasedmodallogics
AT metcalfeg decidabilityoforderbasedmodallogics
AT rodriguezr decidabilityoforderbasedmodallogics
AT roggerj decidabilityoforderbasedmodallogics
_version_ 1782024343499309056

Ejemplares similares