Visibly pushdown automata [1] 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?[1] 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
Complexity of emptiness checking for visibly pushdown automata?
context free;time complexity;pushdown automata;space complexity