A guide to completeness and complexity for modal logics of knowledge and belief

DOI10.1016/0004-3702(92)90049-4zbMath0762.68029OpenAlexW2076073997MaRDI QIDQ1193476

Publication date: 27 September 1992

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(92)90049-4

zbMATH Keywords

possible-worlds semantics PSPACE-complete decision procedures reasoning about knowledge and belief distributed knowledge \(NP\)-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45) Knowledge representation (68T30)

Related Items (only showing first 100 items - show all)

Modal Logics with Hard Diamond-Free Fragments ⋮ Complexity of interpolation and related problems in positive calculi ⋮ Common knowledge logic and game logic ⋮ Probabilistic Common Knowledge Among Infinite Number of Agents ⋮ A Modal-Layered Resolution Calculus for K ⋮ A Poor Man’s Epistemic Logic Based on Propositional Assignment and Higher-Order Observation ⋮ CONDITIONAL BELIEFS: FROM NEIGHBOURHOOD SEMANTICS TO SEQUENT CALCULUS ⋮ Intentions and potential intentions revisited ⋮ Modal logics for reasoning about infinite unions and intersections of binary relations ⋮ Decomposability helps for deciding logics of knowledge and belief ⋮ Definability in the class of all -frames – computability and complexity ⋮ Group Belief ⋮ Tableaux for the Logic of Strategically Knowing How ⋮ Depth-bounded Epistemic Logic ⋮ Unnamed Item ⋮ On the Decision Problem for Two-Variable First-Order Logic ⋮ Tableaux methods for access control in distributed systems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ From KLM-style conditionals to defeasible modalities, and back ⋮ Unnamed Item ⋮ Knowledge-based programs ⋮ Terminating Tableaux for Hybrid Logic with the Difference Modality and Converse ⋮ A resolution-based proof method for temporal logics of knowledge and belief ⋮ Unnamed Item ⋮ A note on the complexity of S4.2 ⋮ A simple tableau system for the logic of elsewhere ⋮ Doxastic logic: a new approach ⋮ Building decision procedures for modal logics from propositional decision procedures — The case study of modal K ⋮ Tableaux and algorithms for Propositional Dynamic Logic with Converse ⋮ Structures of Oppositions in Public Announcement Logic ⋮ Multimodal Separation Logic for Reasoning About Operational Semantics ⋮ INTRANSITIVITY AND VAGUENESS ⋮ Probability logic for type spaces ⋮ Unnamed Item ⋮ Formal Modelling of Emotions in BDI Agents ⋮ Proof Theory for Distributed Knowledge ⋮ Analytic Cut-Free Tableaux for Regular Modal Logics of Agent Beliefs ⋮ Tableau-Based Procedure for Deciding Satisfiability in the Full Coalitional Multiagent Epistemic Logic ⋮ A nonstandard approach to the logical omniscience problem ⋮ A nonstandard approach to the logical omniscience problem ⋮ Common Knowledge and the Knowledge Account of Assertion ⋮ SAT vs. Translation Based decision procedures for modal logics: a comparative evaluation ⋮ Query Answering in Description Logics: The Knots Approach ⋮ First-Order Linear-Time Epistemic Logic with Group Knowledge: An Axiomatisation of the Monodic Fragment ⋮ Seeing, Knowledge and Common Knowledge ⋮ An Epistemic Logic with Hypotheses ⋮ Public Announcement Logic with Distributed Knowledge ⋮ Embedding Linear-Time Temporal Logic into Infinitary Logic: Application to Cut-Elimination for Multi-agent Infinitary Epistemic Linear-Time Temporal Logic ⋮ Complexity of intuitionistic propositional logic and its fragments ⋮ Tableaux for logics of time and knowledge with interactions relating to synchrony ⋮ Adding clauses to poor man's logic (without increasing the complexity) ⋮ BDD-based decision procedures for the modal logic K ★ ⋮ A logical characterisation of qualitative coalitional games ⋮ A new method for testing decision procedures in modal logics ⋮ A uniform tableaux method for nonmonotonic modal logics ⋮ Taming the Complexity of Temporal Epistemic Reasoning ⋮ Super-Strict Implications ⋮ A Tableau-Based Proof Method for Temporal Logics of Knowledge and Belief ⋮ Justification Logics with Probability Operators ⋮ On the logic of common belief and common knowledge ⋮ A note on constructive interpolation for the multi-modal logic \(K_m\) ⋮ Propositional belief base merging or how to merge beliefs/goals coming from several sources and some links with social choice theory ⋮ Announcements to attentive agents ⋮ Possible world semantics and autoepistemic reasoning ⋮ Sequent calculi for branching time temporal logics of knowledge and beliefwith awareness: completeness and decidability ⋮ Common knowledge: Relating anti-founded situation semantics to modal logic neighbourhood semantics ⋮ Intention is choice with commitment ⋮ Building an Epistemic Logic for Argumentation ⋮ Multi-modal nonmonotonic logics of minimal knowledge ⋮ Mechanizing common knowledge logic using COQ ⋮ The complexity of concept languages ⋮ Reasoning about common knowledge with infinitely many agents ⋮ Integration of weighted knowledge bases ⋮ Limited reasoning in first-order knowledge bases with full introspection ⋮ Belief closure: A semantics of common knowledge for modal propositional logic ⋮ Formalizing common belief with no underlying assumption on individual beliefs ⋮ Finitary S5-Theories ⋮ Common knowledge and update in finite environments ⋮ Relevance from an epistemic perspective ⋮ On the relationship between fuzzy autoepistemic logic and fuzzy modal logics of belief ⋮ Open answer set programming for the semantic web ⋮ A class of decidable information logics ⋮ Logical omniscience as infeasibility ⋮ Positive provability logic for uniform reflection principles ⋮ Modeling belief in dynamic systems. I: Foundations ⋮ ALX, an action logic for agents with bounded rationality ⋮ Permission to speak: a logic for access control and conformance ⋮ Possibilistic reasoning -- a mini-survey and uniform semantics ⋮ A semantics for reasoning consistently in the presence of inconsistency ⋮ A polynomial space construction of tree-like models for logics with local chains of modal connectives ⋮ A fully abstract model for the exchange of information in multi-agent systems. ⋮ Complexity of some problems in positive and related calculi ⋮ Relativized common knowledge for dynamic epistemic logic ⋮ An NP-complete fragment of fibring logic ⋮ A new combination procedure for the word problem that generalizes fusion decidability results in modal logics ⋮ Tableau-based decision procedure for logic of knowing-how via simple plans ⋮ Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic ⋮ Mathematical modal logic: A view of its evolution

Cites Work

This page was built for publication: A guide to completeness and complexity for modal logics of knowledge and belief