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

Preview	Text CMRR_JCSS2016.pdf - Accepted Version Available under License Creative Commons: Attribution-Noncommercial-No Derivative Works (CC-BY-NC-ND). Download (388kB) | Preview
	Text 1-s2.0-S0022000017300417-main.pdf - Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (653kB) | Request a copy

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.

Interest & Impact

Downloads

210 since deposited on 18 Aug 2017
52 in the past 12 months

Citations

5 Citations in Web of Science ®
6 Citations in Scopus

Search

in Google Scholar™

Services

Actions (login required)

Edit item

Actions (login required)

Edit item