論文の概要: Convergence and Diversity in the Control Hierarchy
- arxiv url: http://arxiv.org/abs/2306.03628v1
- Date: Tue, 6 Jun 2023 12:30:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-07 15:35:51.186796
- Title: Convergence and Diversity in the Control Hierarchy
- Title（参考訳）: 制御階層における収束と多様性
- Authors: Alexandra Butoi, Ryan Cotterell, David Chiang
- Abstract要約: 4つの形式主義は弱同値であるだけでなく、d-弱同値(d-weak equivalence)と呼ばれるより厳密な意味で等価であることを示す。
CFGを制御するCFGはTAGであり、PDAを制御するPDAは組み込みPDAであり、CFGを制御するPDAはLIGである。
このファミリーの4番目のメンバーであるCFGは、我々が知っているいかなる形式主義にも対応しないので、我々はそれを発明し、それをプッシュダウン随伴オートマトン(Pushdown Adjoining Automaton)と呼ぶ。
- 参考スコア（独自算出の注目度）: 134.09048604473793
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Weir has defined a hierarchy of language classes whose second member
($\mathcal{L}_2$) is generated by tree-adjoining grammars (TAG), linear indexed
grammars (LIG), combinatory categorial grammars, and head grammars. The
hierarchy is obtained using the mechanism of control, and $\mathcal{L}_2$ is
obtained using a context-free grammar (CFG) whose derivations are controlled by
another CFG. We adapt Weir's definition of a controllable CFG to give a
definition of controllable pushdown automata (PDAs). This yields three new
characterizations of $\mathcal{L}_2$ as the class of languages generated by
PDAs controlling PDAs, PDAs controlling CFGs, and CFGs controlling PDAs. We
show that these four formalisms are not only weakly equivalent but equivalent
in a stricter sense that we call d-weak equivalence. Furthermore, using an even
stricter notion of equivalence called d-strong equivalence, we make precise the
intuition that a CFG controlling a CFG is a TAG, a PDA controlling a PDA is an
embedded PDA, and a PDA controlling a CFG is a LIG. The fourth member of this
family, a CFG controlling a PDA, does not correspond to any formalism we know
of, so we invent one and call it a Pushdown Adjoining Automaton.
- Abstract（参考訳）: Weir氏は、第2のメンバ(\mathcal{L}_2$)が木結合文法(TAG)、線形インデックス文法(LIG)、結合圏文法、ヘッド文法によって生成される言語クラスの階層を定義した。
階層構造は制御機構を用いて取得され、$\mathcal{L}_2$は文脈自由文法(CFG)を用いて取得され、その導出は別のCFGによって制御される。
我々は、制御可能なCFGの定義を適用して、制御可能なプッシュダウンオートマトン(PDA)を定義する。
これは、PDAを制御するPDA、CFGを制御するPDA、PDAを制御するCFGによって生成される言語のクラスとして$\mathcal{L}_2$という3つの新しい特徴を与える。
これらの4つの形式は弱同値であるだけでなく、d-弱同値と呼ばれるより厳密な意味で同値であることを示している。
さらに、d-strong equivalenceと呼ばれるより厳密な等価性の概念を用いて、CFGを制御するCFGがTAGであり、PDAを制御するPDAが埋め込みPDAであり、CFGを制御するPDAがLIGであるという直感を正確にする。
pdaを制御するcfgであるこのファミリーの4番目のメンバーは、我々が知っているいかなる形式主義とも一致しないので、それを発明し、それをプッシュダウン随伴オートマトンと呼ぶ。
関連論文リスト
- Annotating Control-Flow Graphs for Formalized Test Coverage Criteria [0.3277163122167433]
制御フローグラフにグラフ自体から推測される決定情報をアノテートする方法を示す。
我々は,一般的なコンパイラから出力されるCFGを自動的にアノテートするツールとして,アルゴリズムを実装した。
論文 参考訳（メタデータ） (2024-07-04T20:13:03Z) - Incoherent GRAPE (inGRAPE) for optimization of quantum systems with environmentally assisted control [51.3422222472898]
オープン1ビットおよび2ビット系に対する非コヒーレントGRAPE法の高忠実度ゲート生成への応用について議論する。
クエトリットには、環境支援型非コヒーレント制御と時間依存デコヒーレンス率の定式化が提供される。
論文 参考訳（メタデータ） (2024-03-26T05:13:26Z) - Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。
我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。
EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文 参考訳（メタデータ） (2023-10-23T18:26:00Z) - Stay on topic with Classifier-Free Guidance [57.28934343207042]
CFGは純粋言語モデリングにおける推論時手法として広く利用できることを示す。
CFG は Pythia, GPT-2 および LLaMA ファミリーモデルの性能をタスクの配列にわたって改善することを示す。
論文 参考訳（メタデータ） (2023-06-30T17:07:02Z) - Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning [27.59524153097858]
文法制約付き復号法(GCD)は、大言語モデル(LM)の生成を制御するために用いられる。
GCDは一般に構造化NLPタスクの統一フレームワークとして機能する。
文法制約付きLMは、制約なしLMよりも大幅に優れるか、タスク固有の微調整モデルよりも優れていることを示す。
論文 参考訳（メタデータ） (2023-05-23T11:54:37Z) - Physics of Language Models: Part 1, Learning Hierarchical Language Structures [51.68385617116854]
トランスフォーマーベースの言語モデルは効率的だが複雑であり、内部動作を理解することは大きな課題である。
本稿では,長文を生成可能な階層規則を生成する合成CFGのファミリーを紹介する。
我々は、GPTのような生成モデルがこのCFG言語を正確に学習し、それに基づいて文を生成することを実証する。
論文 参考訳（メタデータ） (2023-05-23T04:28:16Z) - CODEP: Grammatical Seq2Seq Model for General-Purpose Code Generation [13.702504014245713]
汎用コード生成は、自然言語(NL)記述をPythonのような汎用プログラミング言語(GPL)のコードスニペットに自動的に変換することを目的としている。
既存のシーケンス・ツー・シーケンス(Seq2Seq)アプローチは文法規則を無視したコードを生成する。
本稿では,プッシュダウン・オートマトン(PDA)モジュールを備えた文法型Seq2Seqコード生成フレームワークであるCODEPを提案する。
論文 参考訳（メタデータ） (2022-11-02T01:40:18Z) - Algorithms for Weighted Pushdown Automata [118.67634716230025]
重み付きプッシュダウンオートマトン(WPDA)は多くの自然言語処理タスクの中核にある。
WPDA上で直接動作する新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-13T10:21:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。