  The problem of model checking procedural programs has fostered much research
towards the definition of temporal logics for reasoning on context-free
structures. The most notable of such results are temporal logics on Nested
Words, such as CaRet and NWTL. Recently, the logic OPTL was introduced, based
on the class of Operator Precedence Languages (OPL), more powerful than Nested
Words. We define the new OPL-based logic POTL, prove its FO-completeness, and
provide a model checking procedure for it. POTL improves on NWTL by enabling
the formulation of requirements involving pre/post-conditions, stack
inspection, and others in the presence of exception-like constructs. It
improves on OPTL by being FO-complete, and by expressing more easily stack
inspection and function-local properties.
