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

  • $\begingroup$ What's the best lower bound you've found so far? the best upper bound? $\endgroup$ – D.W. Apr 20 '17 at 15:56
  • $\begingroup$ O(n^3) from PDA emptiness checking, as given by Alur. I found no other mention anywhere. $\endgroup$ – Devendra Bhave Apr 23 '17 at 9:51
  • $\begingroup$ Also, it is P-complete: sciencedirect.com/science/article/pii/S0020019010004114 $\endgroup$ – Michaël Jul 26 '19 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.