mlsanityData to 14 Oct 2026

Directed Regular and Context-Free Languages

arXiv 2401.07106 ↗First posted 13 Jan 2024cs.FL cs.CLcited by 0

Not on the map. Why?

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.

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

23 of 72 references.

References · 23

  1. 2015Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warpingcited by 6
  2. 2018Multivariate Fine-Grained Complexity of Longest Common Subsequencecited by 5
  3. 2015Demystifying Reachability in Vector Addition Systemscited by 4
  4. 2015The height of piecewise-testable languages and the complexity of the logic of subwordscited by 4
  5. 2020The Edit Distance to k-Subsequence Universalitycited by 4
  6. 2020Efficiently Testing Simon's Congruencecited by 3
  7. 2017Decidability, Complexity, and Expressiveness of First-Order Logic Over the Subword Orderingcited by 2
  8. 2019Languages ordered by the subword ordercited by 2
  9. 2015Decidability in the logic of subsequences and supersequencescited by 1
  10. 2016Complexity of regular abstractions of one-counter languagescited by 1
  11. 2016The Diagonal Problem for Higher-Order Recursion Schemes is Decidablecited by 1
  12. 2016Well Behaved Transition Systemscited by 1
11 more
  1. 2017Forward Analysis for WSTS, Part III: Karp-Miller Treescited by 1
  2. 2019The Ideal Approach to Computing Closed Subsets in Well-Quasi-Orderingcited by 1
  3. 2020The complexity of bounded context switching with dynamic thread creationcited by 1
  4. 2021General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyondcited by 1
  5. 2021Universal Horn Sentences and the Joint Embedding Propertycited by 1
  6. 2021Context-Bounded Verification of Thread Poolscited by 1
  7. 2022Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problemscited by 1
  8. 2022Combinatorial Algorithms for Subsequence Matching: A Surveycited by 1
  9. 2022Existential Definability over the Subword Orderingcited by 1
  10. 2023Longest Common Subsequence with Gap Constraintscited by 1
  11. 2023Matching Patterns with Variables Under Simon's Congruencecited by 1

Built on by

Not cited yet.