All finitely axiomatizable tense logics of linear time flows are CoNP-complete
Studia Logica 81 (2):153 - 165 (2005)
| 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. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,631 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesDmitry Sustretov (2009). Hybrid Logics of Separation Axioms. Journal of Logic, Language and Information 18 (4).
Tadeusz Litak (2004). Modal Incompleteness Revisited. Studia Logica 76 (3):329 - 342.
Ryo Kashima (1994). Cut-Free Sequent Calculi for Some Tense Logics. Studia Logica 53 (1):119 - 135.
Nobu-Yuki Suzuki (1993). Some Results on the Kripke Sheaf Semantics for Super-Intuitionistic Predicate Logics. Studia Logica 52 (1):73 - 94.
Camillo Fiorentini (2000). All Intermediate Logics with Extra Axioms in One Variable, Except Eight, Are Not Strongly Ω-Complete. Journal of Symbolic Logic 65 (4):1576-1604.
Frank Wolter (1995). The Finite Model Property in Tense Logic. Journal of Symbolic Logic 60 (3):757-774.
Linh Anh Nguyen & Andrzej Szałas (2011). ExpTime Tableau Decision Procedures for Regular Grammar Logics with Converse. Studia Logica 98 (3):387-428.
Marcus Kracht & Frank Wolter (1997). Simulation and Transfer Results in Modal Logic – a Survey. Studia Logica 59 (2):149-177.
Frank Wolter (1997). Completeness and Decidability of Tense Logics Closely Related to Logics Above K. Journal of Symbolic Logic 62 (1):131-158.
David Gabelaia, Agi Kurucz, Frank Wolter & Michael Zakharyaschev (2005). Products of 'Transitive' Modal Logics. Journal of Symbolic Logic 70 (3):993 - 1021.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
