Directed Regular and Context-Free Languages
This addresses a theoretical problem in formal language theory, with implications for computational complexity and algorithm design, but it is incremental as it builds on known concepts like directedness and downward closures.
The paper tackles the problem of deciding whether a given language is directed, which is fundamental for ideal decompositions of downward closed sets and has applications in comparing downward closures efficiently. It shows that for regular languages, the directedness problem is in AC^1 (polynomial time) and NL-complete for fixed alphabets, while for context-free languages, it is PSPACE-complete.
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.