Before revision:  Our main contributions are the following: (i) we show that the hierarchy is strict and does not collapse, (ii) we provide (exponential  ) upper and lower bounds relating the minimum widths of equivalent NFAs and DFAs , and (iii) we characterize DFAs of minimum p for a given \mathcal L via a co-lexicographic variant of the Myhill-Nerode theorem. Our findings imply that in polynomial time  we can build an index breaking the worst-case conditional lower bound of \Omega( \pi m), whenever the input NFA's width is at most \epsilon \log_2 m, for any constant 0 \leq \epsilon < 1/2.
After revision:  Our main contributions are the following: (i) we show that the hierarchy is strict and does not collapse, (ii) we provide (exponential ) upper and lower bounds relating the minimum widths of equivalent NFAs and DFAs . Our bounds indicate the importance of being able to index NFAs, as they enable indexing regular languages with much faster and smaller indexes. Our second contribution solves precisely this problem, optimally: we devise a polynomial-time algorithm that indexes any NFA with the optimal value p for its width, without explicitly computing p (NP-hard to find). In particular, this implies that we can index in polynomial time we can build an index breaking the worst-case conditional lower bound of \Omega( \pi m), whenever the input NFA's width is at most \epsilon \log_2 m, for any constant 0 \leq \epsilon < 1/2.