# Directed Regular and Context-Free Languages

arXiv: https://arxiv.org/abs/2401.07106 · HTML: https://mlsanity.com/paper/2401.07106/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 72 references that are in the map.
- First posted on arXiv 13 Jan 2024.

## Builds on (most cited first, 23 of 23)

- [Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping](https://mlsanity.com/paper/1502.01063/) (2015)
- [Multivariate Fine-Grained Complexity of Longest Common Subsequence](https://mlsanity.com/paper/1803.00938/) (2018)
- [Demystifying Reachability in Vector Addition Systems](https://mlsanity.com/paper/1503.00745/) (2015)
- [The height of piecewise-testable languages and the complexity of the logic of subwords](https://mlsanity.com/paper/1511.01807/) (2015)
- [The Edit Distance to k-Subsequence Universality](https://mlsanity.com/paper/2007.09192/) (2020)
- [Efficiently Testing Simon's Congruence](https://mlsanity.com/paper/2005.01112/) (2020)
- [Decidability, Complexity, and Expressiveness of First-Order Logic Over the Subword Ordering](https://mlsanity.com/paper/1701.07470/) (2017)
- [Languages ordered by the subword order](https://mlsanity.com/paper/1901.02194/) (2019)
- [Decidability in the logic of subsequences and supersequences](https://mlsanity.com/paper/1510.03994/) (2015)
- [Complexity of regular abstractions of one-counter languages](https://mlsanity.com/paper/1602.03419/) (2016)
- [The Diagonal Problem for Higher-Order Recursion Schemes is Decidable](https://mlsanity.com/paper/1605.00371/) (2016)
- [Well Behaved Transition Systems](https://mlsanity.com/paper/1608.02636/) (2016)
- [Forward Analysis for WSTS, Part III: Karp-Miller Trees](https://mlsanity.com/paper/1710.07258/) (2017)
- [The Ideal Approach to Computing Closed Subsets in Well-Quasi-Ordering](https://mlsanity.com/paper/1904.10703/) (2019)
- [The complexity of bounded context switching with dynamic thread creation](https://mlsanity.com/paper/2011.05825/) (2020)
- [General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond](https://mlsanity.com/paper/2101.08611/) (2021)
- [Universal Horn Sentences and the Joint Embedding Property](https://mlsanity.com/paper/2104.11123/) (2021)
- [Context-Bounded Verification of Thread Pools](https://mlsanity.com/paper/2111.09022/) (2021)
- [Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems](https://mlsanity.com/paper/2206.13896/) (2022)
- [Combinatorial Algorithms for Subsequence Matching: A Survey](https://mlsanity.com/paper/2208.14722/) (2022)
- [Existential Definability over the Subword Ordering](https://mlsanity.com/paper/2210.15642/) (2022)
- [Longest Common Subsequence with Gap Constraints](https://mlsanity.com/paper/2304.05270/) (2023)
- [Matching Patterns with Variables Under Simon's Congruence](https://mlsanity.com/paper/2308.08374/) (2023)

## Abstract (arXiv)

We study the problem of deciding whether a given language is directed. A language L is 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 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 AC1, 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.