2026-07-30T02:17:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19746 2024-03-11T06:37:04Z ddc:004 open_access

Directed Regular and Context-Free Languages Ganardi, Moses Sağlam, Irmak Zetzsche, Georg Subword ideal language regular context-free equivalence downward closure compression 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 AC¹, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moses Ganardi and Irmak Sağlam and Georg Zetzsche 2024 Is Part Of LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2024.36 urn:nbn:de:0030-drops-197465 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.36 eng https://creativecommons.org/licenses/by/4.0/legalcode