Visibly pushdown automata  are pushdown automata in which input symbol determines whether push or pop operation happens in the stack. Does anyone aware of tight lower bound for their emptiness checking complexity?
 Rajeev Alur and P. Madhusudan. 2004. Visibly pushdown languages. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (STOC '04). ACM, New York, NY, USA, 202-211. DOI: http://dx.doi.org/10.1145/1007352.1007390