Fugu-MT 論文翻訳(概要): Directed Regular and Context-Free Languages

論文の概要: Directed Regular and Context-Free Languages

arxiv url: http://arxiv.org/abs/2401.07106v2
Date: Thu, 18 Jan 2024 20:19:54 GMT
ステータス: 処理完了
システム内更新日: 2024-01-22 18:03:38.018240
Title: Directed Regular and Context-Free Languages
Title（参考訳）: 有向正規言語と文脈自由言語
Authors: Moses Ganardi, Irmak Saglam, Georg Zetzsche
Abstract要約: 言語$L$は、$L$のすべての単語が$L$の共通の(散在した)スーパーワードを持っている場合、emphdirectedされる。文脈自由言語では、有向性問題はcoNEXP完全であることが知られている。文脈自由言語では、有向性問題はPSPACE完全であることを示す。
参考スコア（独自算出の注目度）: 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.
Abstract（参考訳）: 我々は、ある言語が指示されているかどうかを決定する問題について研究する。言語 $L$ が \emph{directed} であるとき、$L$ のすべての単語が$L$ の共通(散在)スーパーワードを持つ。有向性の決定は、下向き閉集合の理想的な分解に関する根本的な問題である。もう一つの動機は、2つの \emph{directed} 文脈自由言語が同じ下向き閉包を持つかどうかを多項式時間で決定できることである。 nfas として与えられる正規言語の有向性問題は$ac^1$ であり、したがって多項式時間である。さらに、固定されたアルファベットサイズに対してNL完全である。さらに、文脈自由言語では、有向性問題はPSPACE完全であることを示す。

関連論文リスト

Understanding and Mitigating Language Confusion in LLMs [76.96033035093204]
我々は,既存の英語および多言語プロンプトを用いた15の型的多様言語の評価を行った。 Llama Instruct と Mistral のモデルでは,言語的混乱の度合いが高いことがわかった。言語混乱は,数発のプロンプト,多言語SFT,選好調整によって部分的に緩和できることがわかった。
論文参考訳（メタデータ） (2024-06-28T17:03:51Z)
Question Answering as Programming for Solving Time-Sensitive Questions [84.07553016489769]
質問応答は、世界に関する知識の獲得に関わるため、人間の日常生活において重要な役割を担っている。近年,Large Language Models (LLMs) は疑問に答える上で顕著な知性を示している。これはLLMが表面レベルのテキストセマンティクスに基づいて厳密な推論を行うことができないためである。我々は、$textbfQ$uestion $textbfA$rogrogeringタスクを再設定する新しいアプローチを提案する。
論文参考訳（メタデータ） (2023-05-23T16:35:16Z)
CLSE: Corpus of Linguistically Significant Entities [58.29901964387952]
専門家が注釈を付けた言語学的に重要なエンティティ(CLSE)のコーパスをリリースする。 CLSEは74種類のセマンティックタイプをカバーし、航空券売機からビデオゲームまで様々なアプリケーションをサポートする。言語的に代表されるNLG評価ベンチマークを,フランス語,マラティー語,ロシア語の3言語で作成する。
論文参考訳（メタデータ） (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]
変換は、$x=ysetminus z$, $x neq ysetminus z$, $z =x$ という形のリテラルの結合からなる。対象言語の式は、集合のブール環にまたがる変数と、等式、非可分性、包含性を指定する差分演算子とレギュレータを含む。提案した翻訳は2次アルゴリズムの時間複雑度を持ち、どちらもNP完全満足度問題を持つことが知られている2つの言語を橋渡しする。
論文参考訳（メタデータ） (2021-12-09T09:36:39Z)
Safety Synthesis Sans Specification [5.874782446136914]
ハードウェアおよびソフトウェア検証の多くの状況において、これは自然な問題である、と私たちは主張する。この問題に対する学習アルゴリズムを考案し、その時間とクエリの複雑さが、対象言語のランク、不適合性尺度、与えられた反例の最大長に関するものであることを示す。
論文参考訳（メタデータ） (2020-11-15T21:13:17Z)
Learning Languages with Decidable Hypotheses [1.2728819383164875]
極限における言語学習において、最も一般的な仮説は、ある言語の列挙子を与えることである。いわゆる$W$-indexは任意の計算可能可算言語を命名することができる。我々は、任意の決定可能な言語、すなわち特徴関数のプログラムを命名できる別のシステム($C$-indices)を使用している。
論文参考訳（メタデータ） (2020-10-15T09:27:47Z)
RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
RNNは、自然言語構文の足場を反映した境界階層言語を効率的に生成できることを示す。 Dyck-($k$,$m$)は、よくネストされた括弧($k$型)と$m$バウンドされたネスト深さの言語である。明示的な構成により,$O(m log k)$ hidden units の RNN がメモリの指数的削減に十分であることを示す。
論文参考訳（メタデータ） (2020-10-15T04:42:29Z)
Ambiguity Hierarchy of Regular Infinite Tree Languages [77.34726150561087]
言語が k アンビグラス (k アンビグラス) であれば、言語は k アンビグラス (k アンビグラスオートマトン) である。オートマトンは k が mathbbN$ の約 $k に対して曖昧であれば有界不明瞭である。
論文参考訳（メタデータ） (2020-09-07T10:08:24Z)
Inducing Language-Agnostic Multilingual Representations [61.97381112847459]
言語間の表現は、世界中のほとんどの言語でNLP技術が利用可能になる可能性がある。 i) 対象言語のベクトル空間をピボットソース言語に再配置すること、(ii) 言語固有の手段と分散を取り除くこと、(ii) 副産物としての埋め込みの識別性を向上すること、(iii) 形態的制約や文の並べ替えを除去することによって言語間の入力類似性を高めること、の3つのアプローチを検討する。
論文参考訳（メタデータ） (2020-08-20T17:58:56Z)
Decidability of cutpoint isolation for probabilistic finite automata on letter-bounded inputs [0.1269104766024433]
確率的有限オートマタ(PFA)においてカットポイント分離問題が決定可能であるという驚くべき結果を示す。 PFAが指数的不明瞭である場合でも保持するカットポイント分離問題を解決するための構成的非決定論的アルゴリズムを提供する。
論文参考訳（メタデータ） (2020-02-18T15:47:14Z)
VC-dimensions of nondeterministic finite automata for words of equal length [2.099922236065961]
NFA_b(q)$ は、非決定論的有限オートマトンで許容される言語の集合を、$b$文字のアルファベット上の$q$状態とする。 B_n$ は長さ $n$ の単語の集合を表す。
論文参考訳（メタデータ） (2020-01-07T22:49:55Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。