Directed Regular and Context-Free Languages

• URL: http://arxiv.org/abs/2401.07106v2
• Date: Thu, 18 Jan 2024 20:19:54 GMT
• Title: Directed Regular and Context-Free Languages
• Authors: Moses Ganardi, Irmak Saglam, Georg Zetzsche
• Abstract summary: A language $L$ is emphdirected if every pair of words in $L$ have a common (scattered) superword in $L$. For context-free languages, the directedness problem is known to be coNEXP-complete. We show that for context-free languages, the directedness problem is PSPACE-complete.
• Score: 0.6906005491572399
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Understanding and Mitigating Language Confusion in LLMs [76.96033035093204]
  We evaluate 15 typologically diverse languages with existing and newly-created English and multilingual prompts. We find that Llama Instruct and Mistral models exhibit high degrees of language confusion. We find that language confusion can be partially mitigated via few-shot prompting, multilingual SFT and preference tuning.
  arXiv  Detail & Related papers  (2024-06-28T17:03:51Z)
• Question Answering as Programming for Solving Time-Sensitive Questions [84.07553016489769]
  Question answering plays a pivotal role in human daily life because it involves our acquisition of knowledge about the world. Recently, Large Language Models (LLMs) have shown remarkable intelligence in question answering. This can be attributed to the LLMs' inability to perform rigorous reasoning based on surface-level text semantics. We propose a novel approach where we reframe the $textbfQ$uestion $textbfA$rogrogering task.
  arXiv  Detail & Related papers  (2023-05-23T16:35:16Z)
• CLSE: Corpus of Linguistically Significant Entities [58.29901964387952]
  We release a Corpus of Linguistically Significant Entities (CLSE) annotated by experts. CLSE covers 74 different semantic types to support various applications from airline ticketing to video games. We create a linguistically representative NLG evaluation benchmark in three languages: French, Marathi, and Russian.
  arXiv  Detail & Related papers  (2022-11-04T12:56:12Z)
• Complexity assessments for decidable fragments of Set Theory. III: A quadratic reduction of constraints over nested sets to Boolean formulae [0.0]
  A translation is proposed of conjunctions of literals of the forms $x=ysetminus z$, $x neq ysetminus z$, and $z =x$. The formulae in the target language involve variables ranging over a Boolean ring of sets, along with a difference operator and relators designating equality, non-disjointness and inclusion. The proposed translation has quadratic algorithmic time-complexity, and bridges two languages both of which are known to have an NP-complete satisfiability problem.
  arXiv  Detail & Related papers  (2021-12-09T09:36:39Z)
• Safety Synthesis Sans Specification [5.874782446136914]
  We argue that this is a natural question in many situations in hardware and software verification. We devise a learning algorithm for this problem and show that its time and query complexity is with respect to the rank of the target language, its incompatibility measure, and the maximal length of a given counterexample.
  arXiv  Detail & Related papers  (2020-11-15T21:13:17Z)
• Learning Languages with Decidable Hypotheses [1.2728819383164875]
  In language learning in the limit, the most common type of hypothesis is to give an enumerator for a language. This so-called $W$-index allows for naming arbitrary computably enumerable languages. We use a different system which allows for naming arbitrary decidable languages, namely programs for characteristic functions (called $C$-indices)
  arXiv  Detail & Related papers  (2020-10-15T09:27:47Z)
• RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
  We show that RNNs can efficiently generate bounded hierarchical languages that reflect the scaffolding of natural language syntax. We introduce Dyck-($k$,$m$), the language of well-nested brackets (of $k$ types) and $m$-bounded nesting depth. We prove that an RNN with $O(m log k)$ hidden units suffices, an exponential reduction in memory, by an explicit construction.
  arXiv  Detail & Related papers  (2020-10-15T04:42:29Z)
• Ambiguity Hierarchy of Regular Infinite Tree Languages [77.34726150561087]
  A language is k-ambiguous (respectively, boundedly, finitely, ambiguous) if it is accepted by a k-ambiguous automaton. An automaton is boundedly ambiguous if it is k-ambiguous for some $k in mathbbN$.
  arXiv  Detail & Related papers  (2020-09-07T10:08:24Z)
• Inducing Language-Agnostic Multilingual Representations [61.97381112847459]
  Cross-lingual representations have the potential to make NLP techniques available to the vast majority of languages in the world. We examine three approaches for this: (i) re-aligning the vector spaces of target languages to a pivot source language; (ii) removing language-specific means and variances, which yields better discriminativeness of embeddings as a by-product; and (iii) increasing input similarity across languages by removing morphological contractions and sentence reordering.
  arXiv  Detail & Related papers  (2020-08-20T17:58:56Z)
• Decidability of cutpoint isolation for probabilistic finite automata on letter-bounded inputs [0.1269104766024433]
  We show the surprising result that the cutpoint isolation problem is decidable for Probabilistic Finite Automata (PFA) We provide a constructive nondeterministic algorithm to solve the cutpoint isolation problem, which holds even when the PFA is exponentially ambiguous.
  arXiv  Detail & Related papers  (2020-02-18T15:47:14Z)
• VC-dimensions of nondeterministic finite automata for words of equal length [2.099922236065961]
  Let $NFA_b(q)$ denote the set of languages accepted by nondeterministic finite automata with $q$ states over an alphabet with $b$ letters. Let $B_n$ denote the set of words of length $n$.
  arXiv  Detail & Related papers  (2020-01-07T22:49:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.