Decidability in Order-Based Modal Logics

Caicedo, Xavier; Metcalfe, George; Rodriguez, Ricardo; Rogger, Jonas (2017). Decidability in Order-Based Modal Logics. Journal of computer and system sciences, 88, pp. 53-74. Elsevier 10.1016/j.jcss.2017.03.012

[img]
Preview
Text
CMRR_JCSS2016.pdf - Accepted Version
Available under License Creative Commons: Attribution-Noncommercial-No Derivative Works (CC-BY-NC-ND).

Download (388kB) | Preview
[img] Text
1-s2.0-S0022000017300417-main.pdf - Published Version
Restricted to registered users only
Available under License Publisher holds Copyright.

Download (653kB)

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.

Item Type:

Journal Article (Original Article)

Division/Institute:

08 Faculty of Science > Department of Mathematics and Statistics > Institute of Mathematics

UniBE Contributor:

Metcalfe, George, Rogger, Jonas

Subjects:

500 Science > 510 Mathematics

ISSN:

0022-0000

Publisher:

Elsevier

Language:

English

Submitter:

George Metcalfe

Date Deposited:

18 Aug 2017 08:54

Last Modified:

05 Dec 2022 15:06

Publisher DOI:

10.1016/j.jcss.2017.03.012

BORIS DOI:

10.7892/boris.102027

URI:

https://boris.unibe.ch/id/eprint/102027

Actions (login required)

Edit item Edit item
Provide Feedback