The completeness problem for modal logic

DOI10.1007/978-3-319-72056-2_1zbMATH Open1443.03017arXiv1605.01004OpenAlexW2963942981MaRDI QIDQ1709685FDOQ1709685

Authors: Antonis Achilleos 

Publication date: 6 April 2018

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.

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

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

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)

Cited In (16)

• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Meaning of Logical Completeness
• Title not available (Why is that?)
• An incomplete decidable modal logic
• Methods for proving completeness via logical reductions
• Proof-theoretic modal PA-completeness. III: The syntactic proof
• Modal logic and the polynomial hierarchy: from QBFs to K and back
• Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic
• 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?
• Title not available (Why is that?)

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)