All Finitely Axiomatizable Tense Logics of Linear Time Flows Are CoNP-complete

Studia Logica 81 (2):153-165 (2005)
  Copy   BIBTEX

Abstract

We prove that all finitely axiomatizable tense logics with temporal operators for ‘always in the future’ and ‘always in the past’ and determined by linear fows time are coNP-complete. It follows, for example, that all tense logics containing a density axiom of the form ■n+1F p → nF p, for some n ≥ 0, are coNP-complete. Additionally, we prove coNP-completeness of all ∩-irreducible tense logics. As these classes of tense logics contain many Kripke incomplete bimodal logics, we obtain many natural examples of Kripke incomplete normal bimodal logics which are nevertheless coNP-complete.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,139

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Properties of Tense Logics.Frank Wolter - 1996 - Mathematical Logic Quarterly 42 (1):481-500.
Complexity of monodic guarded fragments over linear and real time.Ian Hodkinson - 2006 - Annals of Pure and Applied Logic 138 (1):94-125.
The Fraenkel‐Carnap question for Dedekind algebras.George Weaver & Benjamin George - 2003 - Mathematical Logic Quarterly 49 (1):92-96.
Tense Logic Without Tense Operators.Frank Wolter - 1996 - Mathematical Logic Quarterly 42 (1):145-171.
Decidable fragments of first-order temporal logics.Ian Hodkinson, Frank Wolter & Michael Zakharyaschev - 2000 - Annals of Pure and Applied Logic 106 (1-3):85-134.
More on d-Logics of Subspaces of the Rational Numbers.Guram Bezhanishvili & Joel Lucero-Bryan - 2012 - Notre Dame Journal of Formal Logic 53 (3):319-345.

Analytics

Added to PP
2009-01-28

Downloads
30 (#499,791)

6 months
6 (#403,662)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

References found in this work

Past, present and future.Arthur N. Prior - 1967 - Oxford,: Clarendon P..
Past, present, and future.Arthur Prior - 1967 - Revue Philosophique de la France Et de l'Etranger 157:476-476.
Tense Logic Without Tense Operators.Frank Wolter - 1996 - Mathematical Logic Quarterly 42 (1):145-171.

View all 11 references / Add more references