We show that every proper normal extension of the bi-modal system S5 2 has the poly-size model property. In fact, to every proper normal extension L of S5 2 corresponds a natural number b(L) - the bound of L. For every L, there exists a polynomial P(·) of degree b(L) + 1 such that every L-consistent formula is satisfiable on an L-frame whose universe is bounded by P(||), where || denotes the number of subformulas of . It is shown that (...) this bound is optimal. (shrink)

We show that every proper normal extension of the bi-modal system S52 has the poly-size model property. In fact, to every proper normal extension L of S52 corresponds a natural number b(L) - the bound of L. For every L, there exists a polynomial P(·) of degree b(L) + 1 such that every L-consistent formula ϕ is satisfiable on an L-frame whose universe is bounded by P(|ϕ|), where |ϕ| denotes the number of subformulas of ϕ. It is shown that this (...) bound is optimal. (shrink)

We prove that every normal extension of the bi-modal system S52 is finitely axiomatizable and that every proper normal extension has NP-complete satisfiability problem.

But Findlay's remark, like so much that has been written on the subject of time in the present century, was provoked in the first place by McTaggart's ...

We prove that every normal extension of the bi-modal system S52 is finitely axiomatizable and that every proper normal extension has NP-complete satisfiability problem.

We use the apparatus of the canonical formulas introduced by Zakharyaschev [10] to prove that all finitely axiomatizable normal modal logics containing K4.3 are decidable, though possibly not characterized by classes of finite frames. Our method is purely frame-theoretic. Roughly, given a normal logic L above K4.3, we enumerate effectively a class of frames with respect to which L is complete, show how to check effectively whether a frame in the class validates a given formula, and then apply a Harropstyle (...) argument to establish the decidability of L, provided of course that it has finitely many axioms. (shrink)

We shall describe the set of strongly meet irreducible logics in the lattice ϵLin.t of normal tense logics of weak orderings. Based on this description it is shown that all logics in ϵLin.t are independently axiomatizable. Then the description is used in order to investigate tense logics with respect to decidability, finite axiomatizability, axiomatization problems and completeness with respect to Kripke semantics. The main tool for the investigation is a translation of bimodal formulas into a language talking about partitions of (...) general frames into intervals so that relative to both Kripke frames and descriptive frames the expressive power of both languages coincides. (shrink)