<p>Is there anything known about the problem of <em>incremental</em> emptiness testing for a pushdown automata? </p>

<p>Suppose you have a PDA with (up to) <span class="math-container">$n$</span> states and transitions, but instead of being given the transition table up front, you are given transition edges one at a time and asked whether their insertion would cause the PDA to accept a nonempty language. Also suppose that each transition can either push a single symbol, pop a single symbol, or leave the stack unchanged, and that the PDA has a designated start and end state, and is defined to accept a word if it results in reaching the end state with an empty stack.</p>

<p>So far, the best algorithm I've been able to come up with is <span class="math-container">$O(n^3)$</span>, based on reducing this to the incremental directed reachability problem, and then applying <a href="https://core.ac.uk/download/pdf/82234237.pdf" rel="nofollow noreferrer">the classic <span class="math-container">$O(n^3)$</span> algorithm</a>. The basic idea is to maintain a directed graph with a vertex for each PDA state, with the invariant that <code>b</code> is reachable from <code>a</code> in that graph if and only if you can go from <code>a</code> to <code>b</code> in the PDA starting and ending with an empty stack. The <span class="math-container">$n^3$</span> reachability algorithm maintains a bit matrix (well actually a table of pointers) for the reachability of each node pair, and hence can determine when <code>b</code> becomes reachable from <code>a</code> for the first time. Whenever the source of a pop edge becomes reachable from the sink of a corresponding push edge, insert an edge into the directed graph from the source of the push edge to the sink of the pop edge (the push and pop edges themselves are obviously not included in the directed graph).</p>

<p>Note that incremental reachability can be done in <span class="math-container">$O(nm)$</span> time, where <span class="math-container">$m$</span> is the number of edges. In the case of the PDA, I specified a linear number of edges <span class="math-container">$n$</span> in the input. However, the extra edges added to level the stack transitions can result in up to <span class="math-container">$m = O(n^2)$</span> edges in the directed graph, and thus overall <span class="math-container">$O(n^3)$</span> time.</p>

<p>I've spent quite a bit of time thinking about this problem, but I haven't been able to improve on the <span class="math-container">$O(n^3)$</span> algorithm at all and am beginning to suspect that it is impossible. Does anyone know of any way to improve this or show that it can't be done?</p>

CC BY-SA 4.0
2020-04-08T03:26:13.777Z
This is a great question!  Note that your cubic time algorithm does not involve constructing the corresponding context-free grammar for the PDA.  I described what seems to be the same (or a similar) approach here: https://cstheory.stackexchange.com/q/32053/14207
Michael Wehar
CC BY-SA 4.0
2020-04-08T04:13:24.093Z
Also, PDA (non-)emptiness checking is P-complete (i.e. polynomial time complete under logspace reductions).  There are multiple known approaches to showing that it is P-complete.  Here is a reference that lists CFG (non-)emptiness as P-complete (and therefore PDA (non-)emptiness): https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.2644
Michael Wehar
CC BY-SA 4.0
2020-04-08T04:14:30.390Z
It being P-complete means that solving it is equivalent to simulating polynomial time bounded Turing machines.  Tightening this equivalence could lead to a time complexity lower bound by the time-hierarchy theorem.  However, tightening it seems to be a difficult task because the existing reductions probably reduce linear-time bounded Turing machine acceptance to PDA non-emptiness.  We would need to reduce $O(n^3)$-time bounded Turing machine acceptance to PDA non-emptiness where the resulting PDA has a linear number of states.
Michael Wehar
CC BY-SA 4.0
2020-04-08T04:21:34.443Z
It being P-complete also means that it will be difficult for us to find a space efficient algorithm.  For example, if we could solve PDA (non-)emptiness in $O(\log^{2}(n))$ space, then we would get that $P \subseteq SPACE(\log^2(n))$ which would be a breakthrough on the many open problems relating time and space complexity classes.
Michael Wehar
<graph-algorithms><automata-theory><online-algorithms>
Incremental PDA emptiness testing?
Antimony
# Incremental PDA emptiness testing?

(Asked by: username_0 on 2020-04-07)

Is there anything known about the problem of *incremental* emptiness testing for a pushdown automata?

Suppose you have a PDA with (up to) $n$ states and transitions, but instead of being given the transition table up front, you are given transition edges one at a time and asked whether their insertion would cause the PDA to accept a nonempty language. Also suppose that each transition can either push a single symbol, pop a single symbol, or leave the stack unchanged, and that the PDA has a designated start and end state, and is defined to accept a word if it results in reaching the end state with an empty stack.

So far, the best algorithm I've been able to come up with is $O(n^3)$, based on reducing this to the incremental directed reachability problem, and then applying [the classic $O(n^3)$ algorithm](https://core.ac.uk/download/pdf/82234237.pdf). The basic idea is to maintain a directed graph with a vertex for each PDA state, with the invariant that `b` is reachable from `a` in that graph if and only if you can go from `a` to `b` in the PDA starting and ending with an empty stack. The $n^3$ reachability algorithm maintains a bit matrix (well actually a table of pointers) for the reachability of each node pair, and hence can determine when `b` becomes reachable from `a` for the first time. Whenever the source of a pop edge becomes reachable from the sink of a corresponding push edge, insert an edge into the directed graph from the source of the push edge to the sink of the pop edge (the push and pop edges themselves are obviously not included in the directed graph).

Note that incremental reachability can be done in $O(nm)$ time, where $m$ is the number of edges. In the case of the PDA, I specified a linear number of edges $n$ in the input. However, the extra edges added to level the stack transitions can result in up to $m = O(n^2)$ edges in the directed graph, and thus overall $O(n^3)$ time.

I've spent quite a bit of time thinking about this problem, but I haven't been able to improve on the $O(n^3)$ algorithm at all and am beginning to suspect that it is impossible. Does anyone know of any way to improve this or show that it can't be done?

**Tags:** graph-algorithms, automata-theory, online-algorithms

> **Comments:**
> **username_1**: This is a great question!  Note that your cubic time algorithm does not involve constructing the corresponding context-free grammar for the PDA.  I described what seems to be the same (or a similar) approach here: https://cstheory.stackexchange.com/q/32053/14207  
> **username_1**: Also, PDA (non-)emptiness checking is P-complete (i.e. polynomial time complete under logspace reductions).  There are multiple known approaches to showing that it is P-complete.  Here is a reference that lists CFG (non-)emptiness as P-complete (and therefore PDA (non-)emptiness): https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.2644  
> **username_1**: It being P-complete means that solving it is equivalent to simulating polynomial time bounded Turing machines.  Tightening this equivalence could lead to a time complexity lower bound by the time-hierarchy theorem.  However, tightening it seems to be a difficult task because the existing reductions probably reduce linear-time bounded Turing machine acceptance to PDA non-emptiness.  We would need to reduce $O(n^3)$-time bounded Turing machine acceptance to PDA non-emptiness where the resulting PDA has a linear number of states.  
> **username_1**: It being P-complete also means that it will be difficult for us to find a space efficient algorithm.  For example, if we could solve PDA (non-)emptiness in $O(\log^{2}(n))$ space, then we would get that $P \subseteq SPACE(\log^2(n))$ which would be a breakthrough on the many open problems relating time and space complexity classes.  

---

## 0 answers

