Temporal logics over linear time domains are in PSPACE

We investigate the complexity of the satisfiability problem of temporal logics with a finite set of modalities definable in the existential fragment of monadic second-order logic. We show that the problem is in pspace over the class of all linear orders. The same techniques show that the problem is in pspace over many interesting classes of linear orders.