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

DOI10.1007/S11225-005-3702-8zbMATH Open1096.03014OpenAlexW1996365374MaRDI QIDQ817685FDOQ817685

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)