1
$\begingroup$

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

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

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.