Fugu-MT 論文翻訳(概要): Nominal Unification and Matching of Higher Order Expressions with Recursive Let

論文の概要: Nominal Unification and Matching of Higher Order Expressions with Recursive Let

arxiv url: http://arxiv.org/abs/2102.08146v1
Date: Tue, 16 Feb 2021 13:36:59 GMT
ステータス: 処理完了
システム内更新日: 2021-02-17 21:45:59.324946
Title: Nominal Unification and Matching of Higher Order Expressions with Recursive Let
Title（参考訳）: Recursive Let を用いた高次表現の公称統一とマッチング
Authors: Manfred Schmidt-Schau{\ss} and Temur Kutsia and Jordi Levy and Mateu Villaret and Yunus Kutz
Abstract要約: 再帰的なletで高階表現を名目で統一する音響完全アルゴリズムを記述し、非決定論的時間で実行可能であることを示す。また、公称 letrec-matching forvariable 式、DAG 用、ガベージフリー式などの特殊化も検討し、その複雑さを決定します。
参考スコア（独自算出の注目度）: 2.0474241801643114
License: http://creativecommons.org/licenses/by-sa/4.0/
Abstract: A sound and complete algorithm for nominal unification of higher-order expressions with a recursive let is described, and shown to run in nondeterministic polynomial time. We also explore specializations like nominal letrec-matching for expressions, for DAGs, and for garbage-free expressions and determine their complexity. Finally, we also provide a nominal unification algorithm for higher-order expressions with recursive let and atom-variables, where we show that it also runs in nondeterministic polynomial time.
Abstract（参考訳）: 再帰リートを用いた高階表現の公称統一のための健全で完全なアルゴリズムを記述し、非決定論的多項式時間で実行することを示した。また,表現に対する名目上のレレックマッチング,DAG,ガベージフリー表現などの特殊化についても検討し,その複雑さを判断する。最後に、再帰的なlet と atom-variables を持つ高次式に対する名目統一アルゴリズムも提供し、非決定論的多項式時間でも動作することを示す。

関連論文リスト

From Exponential to Polynomial Complexity: Efficient Permutation Counting with Subword Constraints [0.0]
置換による異なる置換を数えることは、特に複数のサブワードを含む場合、分析における長年の課題である。本稿では,置換による異なる置換を計算するための閉形式式を示す新しいフレームワークを提案する。次に、新たな式を開発することにより、基本公式を複数のサブワードを扱うように拡張する。
論文参考訳（メタデータ） (2024-11-23T19:52:11Z)
A novel framework for systematic propositional formula simplification based on existential graphs [1.104960878651584]
本稿では、パースの実在グラフの推論と含意グラフの規則から導かれる命題論理の単純化計算について述べる。我々の規則は、ネスト形式の命題論理式に適用でき、同値保存であり、単調に減少する変数、節、リテラルの数を保証し、構造的問題情報の保存を最大化することができる。
論文参考訳（メタデータ） (2024-05-27T11:42:46Z)
The Inefficiency of Genetic Programming for Symbolic Regression -- Extended Version [0.0]
我々は,遺伝的プログラミングの探索挙動を,実用上は関係するが限定的な状況下での象徴的回帰のために分析する。これにより、最良の表現を見つける成功確率を定量化できる。遺伝的プログラミングの探索効率を意味的一意表現の空間におけるランダム探索と比較する。
論文参考訳（メタデータ） (2024-04-26T09:49:32Z)
An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
有限状態オートマトンをオンザフライで決定する手法の抽象化を確立し, オートマトンにどのように適用できるかを実証する。我々の発見の特別な例は、多くの非決定論的遷移を持つオートマトンが、ほとんど常に複雑性の決定性を持っていることである。
論文参考訳（メタデータ） (2023-08-27T11:51:27Z)
Real-time Regular Expression Matching [65.268245109828]
本稿では,有限状態オートマトン,正規表現マッチング,パターン認識,指数的爆破問題について述べる。本稿では,正規言語の複雑なクラスに対する指数的爆破問題に対する理論的およびハードウェア的解法を提案する。
論文参考訳（メタデータ） (2023-08-20T09:25:40Z)
Compositional Generalization without Trees using Multiset Tagging and Latent Permutations [121.37328648951993]
まず、各入力トークンに複数の出力トークンをタグ付けします。次に、新しいパラメータ化法と置換予測法を用いて、トークンを出力シーケンスに配置する。我々のモデルは、事前訓練されたセq2seqモデルと、現実的なセマンティック解析タスクに関する先行研究より優れている。
論文参考訳（メタデータ） (2023-05-26T14:09:35Z)
Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective [97.57162770792182]
文字列内のトークンのペア間の関係をモデル化するタスクは、自然言語を理解する上で不可欠な部分である。これらの徹底的な比較は避けられ、さらに、トークン間の関係を文字列上の部分順序としてキャストすることで、複雑さを線形に減らすことができる。提案手法は,文字列中の各トークンの実際の数を並列に予測し,それに従ってトークンをソートすることで,文字列内のトークンの総順序を決定する。
論文参考訳（メタデータ） (2023-05-24T11:47:35Z)
A dynamic programming algorithm for span-based nested named-entity recognition in O(n^2) [5.228711636020665]
探索空間に補足的構造制約を加えることで、ネストされたNERは2次時間複雑性を持ち、これは非ネストの場合と同じ複雑さを持つことを示す。提案アルゴリズムは、3つの標準英語ベンチマークの大部分をカバーし、同等の実験結果を提供する。
論文参考訳（メタデータ） (2022-10-10T14:47:36Z)
XSTEM: An exemplar-based stemming algorithm [0.0]
ステミング(英: Stemming)とは、接尾辞を除去することで、関連語を標準語に還元する過程である。本稿では,単語ベースのルックアップテーブルの単純さと性能を,規則に基づく手法の強い一般化性と組み合わせて,語彙外単語による問題を回避する,高速,シンプル,高精度,高速なスリーミングアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-05-09T14:58:34Z)
Hierarchical Sketch Induction for Paraphrase Generation [79.87892048285819]
本稿では、高密度符号化の分解を学習するHRQ-VAE(Hierarchical Refinement Quantized Variational Autoencoders)を紹介する。 HRQ-VAEを用いて、入力文の構文形式を階層化の経路としてエンコードすることで、テスト時の構文スケッチをより容易に予測できる。
論文参考訳（メタデータ） (2022-03-07T15:28:36Z)
Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
論文参考訳（メタデータ） (2022-01-25T00:10:03Z)

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