論文の概要: On the Intersection of Context-Free and Regular Languages

• arxiv url: http://arxiv.org/abs/2209.06809v1
• Date: Wed, 14 Sep 2022 17:49:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-15 13:37:06.913097
• Title: On the Intersection of Context-Free and Regular Languages
• Title（参考訳）: 文脈自由言語と正規言語の交叉について
• Authors: Clemente Pasti, Andreas Opedal, Tiago Pimentel, Tim Vieira, Jason Eisner, Ryan Cotterell
• Abstract要約: オートマトンが$epsilon$-arcsを含む場合でも、Bar-Hillel構造を一般化して交差点を正しく計算する。 我々は,本構造が,原構造を入力サイズに保ちながら,オートマトンと文法の両方の構造を符号化する文法に導かれることを証明した。
• 参考スコア（独自算出の注目度）: 71.61206349427509
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Bar-Hillel construction is a classic result in formal language theory. It shows, by construction, that the intersection between a context-free language and a regular language is itself context-free. However, neither its original formulation (Bar-Hillel et al., 1961) nor its weighted extension (Nederhof and Satta, 2003) can handle automata with $\epsilon$-arcs. In this short note, we generalize the Bar-Hillel construction to correctly compute the intersection even when the automaton contains $\epsilon$-arcs. We further prove that our generalized construction leads to a grammar that encodes the structure of both the input automaton and grammar while retaining the asymptotic size of the original construction.
• Abstract（参考訳）: バーヒルル構成は形式言語理論の古典的な結果である。 構成上、文脈自由言語と正規言語との交点自体が文脈自由であることを示している。 しかし、オリジナルの定式化(Bar-Hillel et al., 1961)や重み付き拡張(Nederhof and Satta, 2003)は、$\epsilon$-arcsでオートマトンを扱うことはできない。 本稿では,オートマトンが$\epsilon$-arcsを含む場合でも,Bar-Hillel構造を一般化して交差点を正しく計算する。 さらに、一般化された構成は、入力オートマトンと文法の両方の構造を符号化し、元の構成の漸近的な大きさを維持している文法につながることを証明した。

関連論文リスト

• Efficient Semiring-Weighted Earley Parsing [71.77514972816347]
  本稿では,様々なスピードアップを伴うEarey (1970) の文脈自由構文解析アルゴリズムの,推論システムという形での参照記述を提供する。 私たちのプレゼンテーションには、Earey氏の$O(N3|GR|)$から、既知の最悪のランタイム改善が含まれています。 半重み付き推論への一般化を扱い、Stolcke (1995)のような文法を前処理して推論サイクルを排除し、さらに文プレフィックスの重みを計算するStolckeの手法を一般化する。
  論文  参考訳（メタデータ） (2023-07-06T13:33:59Z)
• Memory Augmented Large Language Models are Computationally Universal [44.64529266193095]
  変換器をベースとした大規模言語モデルは,外部メモリで拡張した場合に計算的に普遍的であることを示す。 我々は,既存の大規模言語モデルであるFlan-U-PaLM 540Bと連想型読み書きメモリを組み合わせることで,汎用チューリングマシンの実行を正確にシミュレートできることを確認した。
  論文  参考訳（メタデータ） (2023-01-10T02:37:44Z)
• On (co-lex) Ordering Automata [2.800608984818919]
  言語Lを受け入れる正準、最小幅、部分的に順序付けられたオートマトンを提示できることを示す。 Hを用いて、言語を認識する最小限のオートマトンから、言語幅を効果的に計算できることを証明する。
  論文  参考訳（メタデータ） (2021-06-04T07:41:58Z)
• Hierarchical Poset Decoding for Compositional Generalization in Language [52.13611501363484]
  出力が部分的に順序付けられた集合(命題)である構造化予測タスクとして人間の言語理解を形式化する。 現在のエンコーダ・デコーダアーキテクチャは意味論のポーズ構造を適切に考慮していない。 本稿では,言語における合成一般化のための新しい階層型ポーズデコーディングパラダイムを提案する。
  論文  参考訳（メタデータ） (2020-10-15T14:34:26Z)
• 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)
• Automatic Extraction of Rules Governing Morphological Agreement [103.78033184221373]
  原文から第一パス文法仕様を抽出する自動フレームワークを開発する。 我々は、世界の多くの言語の文法の中核にあるモルフォシンタクティックな現象である合意を記述する規則の抽出に焦点をあてる。 我々のフレームワークはUniversal Dependenciesプロジェクトに含まれるすべての言語に適用され、有望な結果が得られます。
  論文  参考訳（メタデータ） (2020-10-02T18:31:45Z)
• Ambiguity Hierarchy of Regular Infinite Tree Languages [77.34726150561087]
  言語が k アンビグラス (k アンビグラス) であれば、言語は k アンビグラス (k アンビグラスオートマトン) である。 オートマトンは k が mathbbN$ の約 $k に対して曖昧であれば有界不明瞭である。
  論文  参考訳（メタデータ） (2020-09-07T10:08:24Z)
• Named Entity Extraction with Finite State Transducers [0.0]
  最小限の言語知識を必要とする名前付きエンティティタグシステムについて述べる。 このシステムはBrillのタグのアイデアに基づいており、非常にシンプルです。
  論文  参考訳（メタデータ） (2020-06-20T11:09:04Z)
• On the Power of Unambiguity in B\"uchi Complementation [0.0]
  我々は,B"uchi Automaticaの補間問題に対して,不明瞭さの力を利用する。 我々は,このタイプの縮小型DAGを,ランクベースおよびスライスベース補完構造を最適化するインフン化ツールとして利用する方法を示す。
  論文  参考訳（メタデータ） (2020-05-18T22:51:34Z)
• Incremental Monoidal Grammars [2.685668802278155]
  形式文法を自由モノイド圏という観点から定義し、形式文法の圏からオートマトン圏への関手も定義する。 これにより、自然言語のカテゴリー的視点と確率的言語モデルの標準的な機械学習概念を結びつけることができる。
  論文  参考訳（メタデータ） (2020-01-02T22:37:12Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。