  In the Intersection Non-Emptiness problem, we are given a list of finite
automata $A_1,A_2,\dots,A_m$ over a common alphabet $\Sigma$ as input, and the
goal is to determine whether some string $w\in \Sigma^*$ lies in the
intersection of the languages accepted by the automata in the list. We analyze
the complexity of the Intersection Non-Emptiness problem under the promise that
all input automata accept a language in some level of the dot-depth hierarchy,
or some level of the Straubing-Th\'{e}rien hierarchy. Automata accepting
languages from the lowest levels of these hierarchies arise naturally in the
context of model checking. We identify a dichotomy in the dot-depth hierarchy
by showing that the problem is already NP-complete when all input automata
accept languages of the levels zero or one half and already PSPACE-hard when
all automata accept a language from the level one. Conversely, we identify a
tetrachotomy in the Straubing-Th\'{e}rien hierarchy. More precisely, we show
that the problem is in AC$^0$ when restricted to level zero; complete for
LOGSPACE or NLOGSPACE, depending on the input representation, when restricted
to languages in the level one half; NP-complete when the input is given as DFAs
accepting a language in from level one or three half; and finally,
PSPACE-complete when the input automata accept languages in level two or
higher. Moreover, we show that the proof technique used to show containment in
NP for DFAs accepting languages in the Straubing-Th\'{e}rien hierarchy levels
one ore three half does not generalize to the context of NFAs. To prove this,
we identify a family of languages that provide an exponential separation
between the state complexity of general NFAs and that of partially ordered
NFAs. To the best of our knowledge, this is the first superpolynomial
separation between these two models of computation.
