The Complexity of Deciding Directedness

Irmak Sağlam ( Max Planck Institute for Software Systems )

In this work we focus on the following problem: Given a downward closed language L, what is the complexity of deciding L’s (upward) directedness?

A language is called directed (under subword ordering) if for any two elements a and b in the language, there is an element c in the language that embeds both a and b. Directedness is a downward closure invariant property, i.e. a language is directed iff its downward closure is directed. Therefore, given a regular or a context-free language L, one can decide whether L is directed, by checking whether the downward closure of L is directed. By extending the known techniques, one obtains and NL lower bound and NP upper bound for deciding the directedness of a regular language; and a PTIME lower bound and NEXP upper bound for that of a context-free language.

Based on our paper [1], I will show some new complexity results, that is, a. deciding the directedness of a regular language is NL-complete, if the alphabet is a part of the input, and is in AC1 (which is in PTIME) if the alphabet is not a part of the input. b. deciding the directedness of a context-free language is PSPACE-complete.

Also, our results imply that checking whether two languages have equivalent downward closures (known as the downward closure equivalence (DCE) problem) is substantially easier if we know in advance the languages are directed. DCE is known to be, - coNP-complete for regular languages given via arbitrary NFAs, and - coNEXP-complete for context-free languages.

It follows as a byproduct of our results that DCE a. for regular languages, is NL-complete if the alphabet is a part of the input, and is in AC1 if it is not, b. for context-free languages, is PTIME-complete.

[1] https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.36