# A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes
## 4 An Algorithmic Metatheorem for Log-Depth Circuits and Its Applications
### Applications: Visibly Pushdown Languages  
One of the first things one learns in theoretical computer science is that \"context-free languages are accepted by pushdown automata\", which more or less settles the complexity of context-free languages from a theoretical point of view. From a practical point of view, however, the fact that these automata can be nondeterministic makes it hard to actually implement them, while at the same time, the full power of context-free grammars is only rarely needed to describe typical parsing problems. For this reason, many different restrictions of context-free grammars and pushdown automata have been studied in the literature, one of which will be of interest to us: the class VPL of _visibly pushdown languages_, which are the languages accepted by _visibly pushdown automata_. The visibly pushdown automata are the same as \"normal\" pushdown automata, except for one crucial difference: whether such an automaton modifies its stack via a push or a pop or not at all in any given step depends _only on the current input symbol, not on the internal state_. As an example, consider a pushdown automaton that checks whether in an input string two different kinds of parentheses (like round and square ones) are correctly balanced, see Figure 4 for an example. Such an automaton does a _push_ on all opening parentheses and a _pop_ on all closing parentheses (and does not modify the stack on other symbols). This is exactly the behavior that a visibly pushdown automaton must have. Compare such an automaton to the one for the problem of deciding whether in a bitstring the number of 0-bits and 1-bits is the same, see also Figure 4b: Here, we can use a stack to keep track of the \"excess symbols\" that we have seen. Whether we need to push or pop the next symbol now  
Figure 4: Two examples of the stack contents of two different pushdown automata as they parse the input words “([())[]]” and “0010111100”. In (**Left**), for each opening parenthesis, a push-operation is performed, and, for each closing parenthesis, a pop-operation. In particular, whether or not a push or a pop operation is performed does _not_ depend on the state of the automaton and, hence, the automaton in a visibly pushdown automaton. In contrast, in (**Right**), each operation depends not only on the symbol read (0 or 1), but also on the internal state of the automaton. Indeed, the language accepted by the automaton (decide whether the number of 0 and 1 symbols is equal) cannot be accepted by a visibly pushdown automaton. Figure 3: The parse tree corresponding to the propositional formula \((p\land\
eg p)\lor(q\lor p)\) and the assignment \(\beta(p)=0\) and \(\beta(q)=1\). Note that this tree as well as a tree decomposition for it can be computed easily from the formula (“easily” meaning “in TC\({}^{0}\)” to be precise). depends on whether 0- or 1-bits are currently on the stack and the resulting pushdown automaton is _not_ a visibly pushdown automaton. The acceptance problem for visibly pushdown automata (for a fixed automaton \(A\), decide on input \(w\) whether \(A\) accepts \(w\)) may seem quite unrelated to the topic of this section or, for that matter, of this whole paper: this is not even a graph problem! The trick is, of course, that we can construct a graph _internally_ in an algorithm for deciding this acceptance problem, which leads to an elegant proof the following theorem:  
**Theorem 11**. : \(\mathit{VPL}\subseteq\mathit{NC}^{1}\)_._  
Proof Ideas. : The first key observation is that for a fixed automaton \(A\) and some input word \(w\), the _height_ of the stack reached for any given prefix \(u\) of \(w\) can be computed very easily: it is the number of symbols of \(u\) causing a push minus the number of symbols causing a pop.