The price of universality

DOI10.1305/ndjfl/1040046086zbMath0865.03032OpenAlexW2018462672MaRDI QIDQ1815426

Edith Hemaspaandra

Publication date: 1 July 1997

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1305/ndjfl/1040046086

zbMATH Keywords

complexitypropositional modal logicssatisfiabilitymulti-modal logic

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

On the Decidability of Elementary Modal Logics, Axiomatization and completeness of lexicographic products of modal logics, From self-regarding to other-regarding agents in strategic games: a logical analysis, Pure extensions, proof rules, and hybrid axiomatics, A description logic based situation calculus, Modal Inclusion Logic: Being Lax is Simpler than Being Strict, Separation logics and modalities: a survey, A Qualitative Theory of Cognitive Attitudes and their Change, A logic of argumentation for specification and verification of abstract argumentation frameworks, A polynomial space construction of tree-like models for logics with local chains of modal connectives, A simple logic of concepts, Unnamed Item, Logical approaches to deontic reasoning: From basic questions to dynamic solutions, Generalized modal satisfiability, Rethinking epistemic logic with belief bases, Complexity of intuitionistic propositional logic and its fragments, HTab: a Terminating Tableaux System for Hybrid Logic, Axiomatization and Completeness of Lexicographic Products of Modal Logics, Dynamic Epistemic Logics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Propositional dynamic logic of nonregular programs
• The complexity of reasoning about knowledge and time. I: Lower bounds
• A guide to completeness and complexity for modal logics of knowledge and belief
• A comparison of polynomial time reducibilities
• Propositional dynamic logic of regular programs
• A modal perspective on the computational complexity of attribute value grammar
• Deterministic propositional dynamic logic: finite models, complexity, and completeness
• Decision procedures and expressiveness in the temporal logic of branching time
• Undecidability and nonperiodicity for tilings of the plane
• The complexity of propositional linear temporal logics
• Properties of independently axiomatizable bimodal logics
• Using the Universal Modality: Gains and Questions
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The undecidability of the domino problem