Satisfiability and Model Checking for MSO-definable Temporal Logics are in PSPACE.

Paul Gastin, Dietrich Kuske

Browse the full CONCUR paper archive.