論文の概要: Minimizing LR(1) State Machines is NP-Hard

• arxiv url: http://arxiv.org/abs/2110.00776v1
• Date: Sat, 2 Oct 2021 10:21:34 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-05 15:21:31.790494
• Title: Minimizing LR(1) State Machines is NP-Hard
• Title（参考訳）: LR(1)状態マシンの最小化はNPハード
• Authors: Wuu Yang
• Abstract要約: ノードカラー化問題は最小化パズルに還元される。 最小のLR(1)マシンを使用して、元のグラフの最小色を復元することができる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: LR(1) parsing was a focus of extensive research in the past 50 years. Though most fundamental mysteries have been resolved, a few remain hidden in the dark corners. The one we bumped into is the minimization of the LR(1) state machines, which we prove is NP-hard. It is the node-coloring problem that is reduced to the minimization puzzle. The reduction makes use of two technique: indirect reduction and incremental construction. Indirect reduction means the graph to be colored is not reduced to an LR(1) state machine directly. Instead, it is reduced to a context-free grammar from which an LR(1) state machine is derived. Furthermore, by considering the nodes in the graph to be colored one at a time, the context-free grammar is incrementally extended from a template context-free grammar that is for a two-node graph. The extension is done by adding new grammar symbols and rules. A minimized LR(1) machine can be used to recover a minimum coloring of the original graph.
• Abstract（参考訳）: LR(1)解析は過去50年間の広範な研究の焦点であった。 ほとんどの基本的な謎は解決されているが、一部は暗い角に隠れている。 私たちが突き当たったのはLR(1)状態機械の最小化であり、NPハードであることが証明されている。 最小化パズルに還元されるノードカラー化問題である。 この削減は間接的縮小と漸進的構成という2つのテクニックを利用する。 間接還元は、着色するグラフが直接lr(1)状態機械に還元されないことを意味する。 代わりに、LR(1)状態機械が導出される文脈自由文法に還元される。 さらに、グラフ内のノードを一度に色付けすることを考えると、文脈自由文法は2ノードグラフのテンプレート自由文法から漸進的に拡張される。 この拡張は、新しい文法記号とルールを追加することで行われる。 最小のLR(1)マシンを使用して、元のグラフの最小色を復元することができる。

関連論文リスト

• Red-QAOA: Efficient Variational Optimization through Circuit Reduction [18.10796328987414]
  本稿では,シミュレーショングラフによるエネルギーランドスケープ濃度の低減を目的としたRed-QAOAを提案する。 Red-QAOAは、元のグラフとほぼ同じパラメータを持つより小さな(蒸留された)グラフを生成する。 最適化の最後に、Red-QAOAは原グラフ上の蒸留グラフからパラメータを使用し、原グラフ上のパラメータ探索を継続する。
  論文  参考訳（メタデータ） (2024-07-19T17:44:29Z)
• Rate-Preserving Reductions for Blackwell Approachability [72.03309261614991]
  Abernethy et al. (2011) はブラックウェルのアプローチ可能性と非回帰学習が等価であることを示した。 一般化された後悔最小化の例に対して、いかなるアプローチ可能性のインスタンスも厳格に削減できることが示される。
  論文  参考訳（メタデータ） (2024-06-10T23:23:52Z)
• Edge-Parallel Graph Encoder Embedding [0.0]
  One-Hot Graph Embedding (GEE) は1つの線形パスオーバーエッジを使用し、スペクトル埋め込みに収束する埋め込みを生成する。 本稿では,グラフのエッジ上で関数をマッピングし,ロックフリーなアトミックインストラクションを用いてデータ競合を防止するLigraグラフエンジンの並列プログラムを提案する。
  論文  参考訳（メタデータ） (2024-02-06T21:04:57Z)
• A Simple and Scalable Representation for Graph Generation [13.111214838770296]
  本稿では,エッジ数に適合する小さな表現サイズを持つ,ギャップ符号化エッジリスト (GEEL) という,新しい,シンプルでスケーラブルなグラフ表現を提案する。 GEELは、ギャップエンコーディングと帯域幅制限スキームを組み込むことにより、語彙サイズを著しく削減する。 我々は、GEELの有効性を実証し、10の非分散および2つの分子グラフ生成タスクを総合的に評価する。
  論文  参考訳（メタデータ） (2023-12-04T03:43:26Z)
• Can Language Models Solve Graph Problems in Natural Language? [51.28850846990929]
  大型言語モデル (LLM) は暗黙的なグラフィカル構造を持つ様々なタスクに採用されている。 自然言語をシミュレーションするグラフベース問題解決のベンチマークであるNLGraphを提案する。
  論文  参考訳（メタデータ） (2023-05-17T08:29:21Z)
• Gradient scarcity with Bilevel Optimization for Graph Learning [0.0]
  勾配不足は、ノードのサブセットの損失を最小限にすることでグラフを学習する際に発生する。 我々は、この現象の正確な数学的特徴を与え、双レベル最適化にも現れることを証明した。 この問題を緩和するために,グラフ・ツー・グラフモデル(G2G)を用いた潜時グラフ学習,グラフに先行構造を課すグラフ正規化,あるいは直径を縮小した元のグラフよりも大きなグラフを最適化することを提案する。
  論文  参考訳（メタデータ） (2023-03-24T12:37:43Z)
• Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs [131.53471236405628]
  グラフ空間における[0, 1]2の分割上のグラフとグラフ信号の誘導的グラフ表現を利用する3つの方法を提案する。 これらの低次元表現がグラフとグラフ信号の収束列を構成することを証明している。 我々は,層間次元減少比が大きい場合,グラノンプーリングは文献で提案した他の手法よりも有意に優れていることを観察した。
  論文  参考訳（メタデータ） (2022-12-15T22:11:34Z)
• Boosting Graph Embedding on a Single GPU [3.093890460224435]
  大規模グラフを最小限のハードウェア制約で埋め込むためのGPUベースのツールであるGOSHを提案する。 更新の影響を高め、埋め込み作業を最小限にするため、新しいグラフ粗化アルゴリズムを採用している。 また、任意の任意の大きなグラフを単一のGPUで埋め込むことができる分解スキーマも組み込まれている。
  論文  参考訳（メタデータ） (2021-10-19T15:25:04Z)
• LAPAR: Linearly-Assembled Pixel-Adaptive Regression Network for Single Image Super-Resolution and Beyond [75.37541439447314]
  単一画像超解像(SISR)は、低解像度(LR)画像を高解像度(HR)バージョンにアップサンプリングする根本的な問題を扱う。 本稿では,線形組立画素適応回帰ネットワーク (LAPAR) を提案する。
  論文  参考訳（メタデータ） (2021-05-21T15:47:18Z)
• An Interpretation of Regularization by Denoising and its Application with the Back-Projected Fidelity Term [55.34375605313277]
  RED勾配は以前の関数の(部分)階調と見なすことができるが、その点の分極バージョンで考えることができる。 本稿では, RED と Back-Projection (BP) のフィデリティ項を組み合わせることを提案する。
  論文  参考訳（メタデータ） (2021-01-27T18:45:35Z)
• Closed-loop Matters: Dual Regression Networks for Single Image Super-Resolution [73.86924594746884]
  ディープニューラルネットワークは、画像超解像において有望な性能を示した。 これらのネットワークは、低分解能(LR)画像から高分解能(HR)画像への非線形マッピング関数を学習する。 本稿では,可能な関数の空間を削減するために,LRデータに新たな制約を導入することで,二重回帰手法を提案する。
  論文  参考訳（メタデータ） (2020-03-16T04:23:42Z)

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

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