The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic

DOI10.1016/0004-3702(95)00018-AzbMath1014.03508OpenAlexW2160811334MaRDI QIDQ1855229

Joseph Y. Halpern

Publication date: 4 February 2003

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

Full work available at URL: https://doi.org/10.1016/0004-3702(95)00018-a

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (36)

Parametrised Complexity of Satisfiability in Temporal Logic ⋮ Modal Logics with Hard Diamond-Free Fragments ⋮ Logic and social cognition. The facts matter, and so do computational models ⋮ Undecidability of QLTL and QCTL with two variables and one monadic predicate letter ⋮ Complexity of finite-variable fragments of propositional temporal and modal logics of computation ⋮ In all but finitely many possible worlds: model-theoretic investigations on `\textit{overwhelming majority}' default conditionals ⋮ Reasoning about common knowledge with infinitely many agents ⋮ Boolean logics with relations ⋮ Boolean Logics with Relations ⋮ Computational complexity of the word problem in modal and Heyting algebras with a small number of generators ⋮ On the complexity of input/output logic ⋮ Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино? ⋮ A logic of ``black box classifier systems ⋮ A polynomial space construction of tree-like models for logics with local chains of modal connectives ⋮ Two-Variable Separation Logic and Its Inner Circle ⋮ An NP-complete fragment of fibring logic ⋮ Deciding the word problem in pure double Boolean algebras ⋮ The expressibility of fragments of hybrid graph logic on finite digraphs ⋮ Quirky Quantifiers: Optimal Models and Complexity of Computation Tree Logic ⋮ A note on the complexity of S4.2 ⋮ A simple tableau system for the logic of elsewhere ⋮ The complexity of identifying characteristic formulae ⋮ Minimal refinements of specifications in modal and temporal logics ⋮ Parameterized modal satisfiability ⋮ Minimal refinements of specifications in modal and temporal logics ⋮ TRANSITIVE PRIMAL INFON LOGIC ⋮ Epistemic closure and epistemic logic. I: Relevant alternatives and subjunctivism ⋮ Generalized modal satisfiability ⋮ SAT vs. Translation Based decision procedures for modal logics: a comparative evaluation ⋮ Complexity of intuitionistic propositional logic and its fragments ⋮ Adding clauses to poor man's logic (without increasing the complexity) ⋮ A new method for testing decision procedures in modal logics ⋮ Reasoning about knowledge of unawareness ⋮ Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter ⋮ The semijoin algebra and the guarded fragment ⋮ The complexity of propositional linear temporal logics in simple cases

Cites Work

• A guide to completeness and complexity for modal logics of knowledge and belief
• A theory of knowledge and ignorance for many agents
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic