The completeness problem for modal logic

DOI10.1007/978-3-319-72056-2_1MaRDI QIDQ1709685zbMATH OpenOpenAlexFDO

Authors Antonis Achilleos

Publication date 6 April 2018

Full work available at URL https://arxiv.org/abs/1605.01004

zbMATH Keywords

computational complexitycompletenessmodal logicbisimulation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70)

Abstract: We introduce the completeness problem for Modal Logic and examine its complexity. For a definition of completeness for formulas, given a formula of a modal logic, the completeness problem asks whether the formula is complete for that logic. We discover that completeness and validity have the same complexity --- with certain exceptions for which there are, in general, no complete formulas. To prove upper bounds, we present a non-deterministic polynomial-time procedure with an oracle from PSPACE that combines tableaux and a test for bisimulation, and determines whether a formula is complete.

Recommendations

• scientific article; zbMATH DE number 1499093
• scientific article; zbMATH DE number 6675100
• Effective completeness theorems for modal logic
• scientific article; zbMATH DE number 2149468
• An incompleteness theorem for modal relevant logics
• scientific article; zbMATH DE number 3916226
• scientific article; zbMATH DE number 7699443
• Completeness and incompleteness in first-order modal logic: an overview
• A note on assumption-completeness in modal logic
• Modal incompleteness revisited

Cited in

(16)

• scientific article; zbMATH DE number 6704247 (Why is no real title available?)
• The complexity of identifying characteristic formulae
• A new proof of completeness for a relative modal logic with composition and intersection
• Effective completeness theorems for modal logic
• scientific article; zbMATH DE number 2020142 (Why is no real title available?)
• scientific article; zbMATH DE number 7668097 (Why is no real title available?)
• On the Meaning of Logical Completeness
• scientific article; zbMATH DE number 6287581 (Why is no real title available?)
• An incomplete decidable modal logic
• Methods for proving completeness via logical reductions
• Proof-theoretic modal PA-completeness. III: The syntactic proof
• Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic
• Modal logic and the polynomial hierarchy: from QBFs to K and back
• Existence of an algorithm for recognition of the completeness with respect to expressibility in modal pre-tabular logic EM4
• Completeness and incompleteness for plausibility logic
• When are prime formulae characteristic?

This page was built for publication: The completeness problem for modal logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1709685)