# Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
## 3 Myhill-Nerode Families  
In this section, we introduce the basic machinery to formalize the notion of dynamic programming algorithms and how we prove lower bounds based on this notion. First of all, we need to establish what we mean by _dynamic programming_ (_DP_). DP algorithms on graph decompositions work by visiting the bags/nodes of the decomposition in a bottom-up fashion (a post-order depth-first traversal), maintaining tables to compute a solution. For decision problems, these algorithms only need to keep at most \(\log n\) tables in memory at any given moment (achieved in the case of treewidth by always descending first into the part of the tree decomposition with the greatest number of leaves). We propose a machine model with a read-only tape for the input that can only be traversed once, which only accepts as input decompositions presented in a valid order. This model suffices to capture known dynamic programming algorithms on path, tree and treedepth decompositions. More specifically, given a decision problem on graphs \(\Pi\) and some well-formed instance \((G,\xi)\) of \(\Pi\) (where \(\xi\) encodes the non-graph part of the input), let \(T\) be a tree, path or treedepth decomposition of \(G\) of width/depth \(d\). We fix an encoding \(\hat{T}\) of \(T\) that lists the separators provided by the decomposition in the order they are normally visited in a dynamic programming algorithm (post-order depth-first traversal of the bag/nodes of a tree/path/treedepth decomposition) and additionally encodes the edges of \(G\) contained in a separator using \(O(d\log d)\) bits per bag or path. Then \((d,\hat{T},\xi)\) is a well-formed instance of the _DP decision problem_\(\Pi_{DP}\). Pairing DP decision problems with the following machine model provides us with a way to model DP computation over graph decompositions. **Definition 2** (Dynamic programming TM). : _A DPTM \(M\) is a Turing machine with an input read-only tape, whose head moves only in one direction and a separate working tape. It accepts as inputs only well-formed instances of some DP decision problem._  
Any single-pass dynamic programming algorithm that solves a DP decision problem on tree, path or treedepth decompositions of width/depth \(d\) using tables of size \(f(d)\) that does not re-arrange the decomposition can be translated into a DPTM with a working tape of size \(O(f(d)\cdot\log n)\). This model does not suffice to rule out algebraic techniques, since this technique, like branching, requires to visit every part of the decomposition many times [17]; or algorithms that preprocess the decomposition first to find a suitable traversal strategy. The theorem of Myhill and Nerode is best known from formal language theory where it is used to show that a language is not regular, but is more general in its original form. For example, if we look at the language \(L\) consisting of all words \(a^{n}ba^{n}\) we define the equivalence relation \(\equiv\) by defining \(u\equiv v\) if \(uw\in L\) iff \(vw\in L\) for all \(w\in\{a,b\}^{*}\). Then \(a^{n}\
ot\equiv a^{m}\) if \(n\
eq m\). This means that \(\equiv\) has infinitely many equivalence classes which shows that \(L\) is not regular. To show that an automaton would need infinitely many states is only the first step and we can furthermore investigate how much space we need when reading a word of length \(n\). In the case of \(L\) you would need \(\Theta(n)\) states which translates in about \(\log n\) bits of space. This is a typical use of the Myhill-Nerode theorem to show a space lower bound, but our goal is different: Let us assume we have a path decomposition of a graph which is read from left to right by dynamic programming. This is very similar to reading a word where the bags play the role of the characters. We want to show a lower bound in term of the size of the bags. Roughly, the size of a bag is related to the logarithm of the alphabet size because there are exponentially many graphs in the number of vertices.