Undecidability of Partial Order Logics

In this paper, we prove the undecidability of certain temporal logics over partial orders. Our proof is generic and can be applied to characterize various temporal operators that cannot be used for automatic verification (model checking).