The Complexity of Poor Man's Logic

DOI10.1093/logcom/11.4.609zbMath1006.03017arXivcs/9911014OpenAlexW2007671683MaRDI QIDQ2761753

Edith Hemaspaandra

Publication date: 7 January 2002

Published in: Journal of Logic and Computation (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitymodal logicdescription logicmodal satisfiability

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Modal Logics with Hard Diamond-Free Fragments, Complexity of Model Checking for Modal Dependence Logic, The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I, Complexity of modal logics with Presburger constraints, The complexity of satisfiability for fragments of hybrid logic. I., Complexity results for modal dependence logic, The decision problem of provability logic with only one atom, Generalized modal satisfiability, Expressivity and Complexity of Dependence Logic, KRIPKE COMPLETENESS OF STRICTLY POSITIVE MODAL LOGICS OVER MEET-SEMILATTICES WITH OPERATORS, Weak Kripke Structures and LTL, Adding clauses to poor man's logic (without increasing the complexity)