Visibly Linear Temporal Logic

Abstract

We introduce Visibly Linear Temporal Logic (VLTL), a linear-time temporal logic that captures the full class of Visibly Pushdown Languages over infinite words. The novel logic avoids fix points and instead provides natural temporal operators with simple and intuitive semantics. We prove that the complexities of the satisfiability and visibly pushdown model checking problems are the same as for other well known logics, like CARET and the nested word temporal logic NWTL, which in contrast are strictly more limited in expressive power than VLTL. Moreover, formulas of CARET and NWTL can be translated inductively and in linear-time into VLTL.