All finitely axiomatizable tense logics of linear time flows are coNP-complete

DOI10.1007/s11225-005-3702-8zbMath1096.03014OpenAlexW1996365374MaRDI QIDQ817685

Tadeusz Litak, Frank Wolter

Publication date: 17 March 2006

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

Full work available at URL: https://doi.org/10.1007/s11225-005-3702-8

zbMATH Keywords

computational complexityNP-completenesstense logictemporal logicframe incompleteness

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Temporal logic (03B44)

Related Items (3)

Rules admissible in transitive temporal logic \(\mathrm{T}_{\mathrm{S}4}\), sufficient condition ⋮ 2007 European Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '07 ⋮ COMPLETE ADDITIVITY AND MODAL INCOMPLETENESS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the size of refutation Kripke models for some linear modal and tense logics
• All normal extensions of S5-squared are finitely axiomatizable
• All proper normal extensions of S5-square have the polynomial size model property
• First-order logic with two variables and unary temporal logic
• The complexity of propositional linear temporal logics
• All Finitely Axiomatizable Normal Extensions of K4.3 are Decidable
• Tense Logic Without Tense Operators

This page was built for publication: All finitely axiomatizable tense logics of linear time flows are coNP-complete