  We study the problem of deciding whether a given language is directed. A
language $L$ is \emph{directed} if every pair of words in $L$ have a common
(scattered) superword in $L$. Deciding directedness is a fundamental problem in
connection with ideal decompositions of downward closed sets. Another
motivation is that deciding whether two \emph{directed} context-free languages
have the same downward closures can be decided in polynomial time, whereas for
general context-free languages, this problem is known to be coNEXP-complete.
  We show that the directedness problem for regular languages, given as NFAs,
belongs to $AC^1$, and thus polynomial time. Moreover, it is NL-complete for
fixed alphabet sizes. Furthermore, we show that for context-free languages, the
directedness problem is PSPACE-complete.
