論文の概要: On the Intersection of Context-Free and Regular Languages
- arxiv url: http://arxiv.org/abs/2209.06809v2
- Date: Thu, 18 May 2023 09:57:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-19 20:50:22.029573
- 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要約: 我々はBar-Hillel構造を一般化し、$varepsilon$-arcsで有限状態オートマトンを扱う。
我々の構成が入力オートマトンと文法の両方の構造を符号化し、元の構成のサイズを維持した文法につながることを証明している。
- 参考スコア(独自算出の注目度): 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 a simple construction, that the intersection of a context-free
language and a regular language is itself context-free. In the construction,
the regular language is specified by a finite-state automaton. However, neither
the original construction (Bar-Hillel et al., 1961) nor its weighted extension
(Nederhof and Satta, 2003) can handle finite-state automata with
$\varepsilon$-arcs. While it is possible to remove $\varepsilon$-arcs from a
finite-state automaton efficiently without modifying the language, such an
operation modifies the automaton's set of paths. We give a construction that
generalizes the Bar-Hillel in the case where the desired automaton has
$\varepsilon$-arcs, and 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) も、$\varepsilon$-arcs で有限状態オートマトンを扱うことはできない。
言語を変更することなく、有限状態オートマトンから$\varepsilon$-arcsを効率的に取り除くことができるが、そのような操作はオートマトンのパスセットを修正する。
我々は、所望のオートマトンが$\varepsilon$-arcsである場合にバーヒルルを一般化する構成を示し、さらに、我々の一般化された構成が、入力オートマトンと文法の両方の構造を符号化し、元の構成の漸近的なサイズを保った文法に導くことを証明する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。