Directed Regular and Context-Free Languages
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Recognizing Reduplicated Forms: Finite-State Buffered Machines
Total reduplication is common in natural language phonology and morphology. However, formally as copying on reduplicants of unbounded size, unrestricted total reduplication requires computational power beyond context-fre…
Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing
We present a simple encoding for unlabeled noncrossing graphs and show how its latent counterpart helps us to represent several families of directed and undirected graphs used in syntactic and semantic parsing of natural…
Dependency ParsingSemantic ParsingGeneric Axiomatization of Families of Noncrossing Graphs in Dependency Parsing
We present a simple encoding for unlabeled noncrossing graphs and show how its latent counterpart helps us to represent several families of directed and undirected graphs used in syntactic and semantic parsing of natural…
Dependency ParsingSemantic ParsingNILE: Formalizing Natural-Language Descriptions of Formal Languages
This paper explores how natural-language descriptions of formal languages can be compared to their formal representations and how semantic differences can be explained. This is motivated from educational scenarios where …
Evaluating Transformer's Ability to Learn Mildly Context-Sensitive Languages
Despite the fact that Transformers perform well in NLP tasks, recent studies suggest that self-attention is theoretically limited in learning even some regular and context-free languages. These findings motivated us to t…