On the size of refutation Kripke models for some linear modal and tense logics

DOI10.1007/BF00713542zbMath0466.03008OpenAlexW1981561399MaRDI QIDQ1155046

S. H. Smith

Publication date: 1980

Published in: Studia Logica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00713542

zbMATH Keywords

satisfiability problemfinite model property

Mathematics Subject Classification ID

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

Related Items

The computational complexity of the satisfiability of modal Horn clauses for modal propositional logics, Conditional logics of normality: A modal approach, A Cookbook for Temporal Conceptual Data Modelling with Description Logics, The complexity of the temporal logic with ``until over general linear time, Complexity of hybrid logics over transitive frames, Backdoors for linear temporal logic, Canonical formulas for K4. Part II: Cofinal subframe logics, First-order rewritability of ontology-mediated queries in linear temporal logic, Unnamed Item, The complexity of propositional linear temporal logics in simple cases, Undecidability of Multi-modal Hybrid Logics, All finitely axiomatizable tense logics of linear time flows are coNP-complete

Cites Work

• Unnamed Item
• Unnamed Item
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The complexity of theorem-proving procedures