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

DOI10.1007/S11225-005-3702-8MaRDI QIDQ817685zbMATH OpenOpenAlexFDO

Authors Tadeusz Litak, F. 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

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

Recommendations

• scientific article; zbMATH DE number 757645
• scientific article; zbMATH DE number 759442
• The complexity of the temporal logic with ``until over general linear time
• The complexity of propositional linear temporal logics
• Completeness and decidability of tense logics closely related to logics above K4

Cites work

• scientific article; zbMATH DE number 4033710 (Why is no real title available?)
• scientific article; zbMATH DE number 747023 (Why is no real title available?)
• scientific article; zbMATH DE number 1852920 (Why is no real title available?)
• scientific article; zbMATH DE number 757645 (Why is no real title available?)
• scientific article; zbMATH DE number 5046360 (Why is no real title available?)
• scientific article; zbMATH DE number 3271460 (Why is no real title available?)
• All Finitely Axiomatizable Normal Extensions of K4.3 are Decidable
• 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
• On the size of refutation Kripke models for some linear modal and tense logics
• Tense Logic Without Tense Operators
• The complexity of propositional linear temporal logics

Cited in

(4)

• 2007 European Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '07
• Rules admissible in transitive temporal logic \(\mathrm{T}_{\mathrm{S}4}\), sufficient condition
• scientific article; zbMATH DE number 759442 (Why is no real title available?)
• COMPLETE ADDITIVITY AND MODAL INCOMPLETENESS

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q817685)