論文の概要: Elementary Sets for Logic Programs
- arxiv url: http://arxiv.org/abs/2307.09168v1
- Date: Sat, 15 Jul 2023 08:00:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-19 15:01:58.014422
- Title: Elementary Sets for Logic Programs
- Title（参考訳）: 論理プログラムのための基本セット
- Authors: Martin Gebser, Joohyung Lee, Yuliya Lierler
- Abstract要約: 「初等ループと呼ばれるループの特別なクラスにループ公式を限定しても、リン・ザオの定理は正しいことを証明している。」
非共役プログラムとは異なり、初等集合を決定する問題は、非共役プログラムに対してcoNP完全であることを示す。
- 参考スコア（独自算出の注目度）: 4.759005117636891
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: By introducing the concepts of a loop and a loop formula, Lin and Zhao showed
that the answer sets of a nondisjunctive logic program are exactly the models
of its Clark's completion that satisfy the loop formulas of all loops.
Recently, Gebser and Schaub showed that the Lin-Zhao theorem remains correct
even if we restrict loop formulas to a special class of loops called
``elementary loops.'' In this paper, we simplify and generalize the notion of
an elementary loop, and clarify its role. We propose the notion of an
elementary set, which is almost equivalent to the notion of an elementary loop
for nondisjunctive programs, but is simpler, and, unlike elementary loops, can
be extended to disjunctive programs without producing unintuitive results. We
show that the maximal unfounded elementary sets for the ``relevant'' part of a
program are exactly the minimal sets among the nonempty unfounded sets. We also
present a graph-theoretic characterization of elementary sets for
nondisjunctive programs, which is simpler than the one proposed in (Gebser &
Schaub 2005). Unlike the case of nondisjunctive programs, we show that the
problem of deciding an elementary set is coNP-complete for disjunctive
programs.
- Abstract（参考訳）: ループの概念とループ公式を導入することで、リンとザオは非可分論理プログラムの解集合が、すべてのループのループ公式を満たすクラークの完備化のモデルであることを示した。
近年、gebser と schaub は、ループ公式を ‘elementary loops' と呼ばれるループの特別なクラスに制限しても、lin-zhao の定理は正しいことを示した。
そこで本稿では,基本ループの概念を単純化し,一般化し,その役割を明らかにする。
本稿では,非可分型プログラムに対する基本ループの概念とほぼ同値な基本集合の概念を提案するが,単純であり,初等ループとは異なり,直観的な結果が得られず,非可分型プログラムに拡張することができる。
プログラムの ‘relevant'' 部分に対する最大非基礎的基本集合は、空でない非基礎的集合の中のちょうど極小集合であることを示す。
また,非分離型プログラムのための基本集合のグラフ理論的特徴付けについても述べる(gebser & schaub 2005)。
非分離型プログラムの場合とは異なり、基本集合を決定する問題は分離型プログラムのconp完全であることを示す。
関連論文リスト
- Invariant Relations: A Bridge from Programs to Equations [1.3342735568824553]
任意のレベルにネストしたループを持つプログラムを含む,C型プログラムの関数を導出する手法を提案する。
ループの意味を捉えるために、不変関係の概念を用いる。
論文 参考訳（メタデータ） (2023-10-07T04:11:23Z) - On Loop Formulas with Variables [2.1955512452222696]
最近、フェラーリス、リー、リフシッツはグラウンド化に言及しない安定モデルの新たな定義を提案した。
我々は、Chen, Lin, Wang, Zhang による変数を持つループ公式のアイデアとの関係を示す。
論理プログラムの構文を拡張して、明示的な量化を許容し、その意味論を安定モデルの新しい言語のサブクラスとして定義する。
論文 参考訳（メタデータ） (2023-07-15T06:20:43Z) - A Hybrid System for Systematic Generalization in Simple Arithmetic
Problems [70.91780996370326]
本稿では,記号列に対する合成的および体系的推論を必要とする算術的問題を解くことができるハイブリッドシステムを提案する。
提案システムは,最も単純なケースを含むサブセットでのみ訓練された場合においても,ネストした数式を正確に解くことができることを示す。
論文 参考訳（メタデータ） (2023-06-29T18:35:41Z) - Consistent circuits for indefinite causal order [0.0]
論理的に一貫性があるが、循環因果構造を特徴とする多くの量子過程が提案されている。
ここでは,エキゾチックな因果構造を持つプロセスを構築する方法を提案する。
因果不等式に反するプロセスを含む、エキゾチックなプロセスの標準的な例が、このような方法で生成可能なプロセスのクラスであることを示す。
論文 参考訳（メタデータ） (2022-06-20T23:15:52Z) - Will Bilevel Optimizers Benefit from Loops [63.22466953441521]
AID-BiOとITD-BiOの2つの一般的な双レベルマトリクスは、自然に1つまたは2つのサブプロブレムを解決する。
AID-BiO と ITD-BiO の両ループ実装選択に適用可能な統合収束解析をまず確立する。
論文 参考訳（メタデータ） (2022-05-27T20:28:52Z) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - Enforcing Consistency in Weakly Supervised Semantic Parsing [68.2211621631765]
本稿では,関連する入力に対する出力プログラム間の整合性を利用して,スプリアスプログラムの影響を低減することを提案する。
より一貫性のあるフォーマリズムは、一貫性に基づくトレーニングを必要とせずに、モデルパフォーマンスを改善することにつながります。
論文 参考訳（メタデータ） (2021-07-13T03:48:04Z) - Sequential composition of answer set programs [0.0]
本稿では,解集合プログラムの逐次構成を導入,研究することにより,論理プログラミングの数学的基礎に寄与する。
より広い意味では、本論文は、解集合プログラムの代数への第一歩であり、将来的には、この論文の手法をプログラムのより広範なクラスに引き上げる計画である。
論文 参考訳（メタデータ） (2021-04-25T13:27:22Z) - Latent Programmer: Discrete Latent Codes for Program Synthesis [56.37993487589351]
プログラム合成や文書要約などの多くのシーケンス学習タスクにおいて、重要な問題は出力シーケンスの広い空間を探索することである。
本稿では,検索対象とする出力の表現を学習することを提案する。
本稿では,まず入力/出力サンプルから離散潜在コードを予測するプログラム合成手法であるemphLatent Programmerを紹介し,そのプログラムを対象言語で生成する。
論文 参考訳（メタデータ） (2020-12-01T10:11:35Z) - ConjNLI: Natural Language Inference Over Conjunctive Sentences [89.50542552451368]
連接文における連接関係の推論は、連接関係のより深い理解にとって重要である。
既存のNLIストレステストでは、結合の非ブール的使用は考慮されていない。
本稿では,接続文に対する自然言語推論のためのストレステストであるConjNLIを紹介する。
論文 参考訳（メタデータ） (2020-10-20T16:29:13Z) - Sequential composition of propositional logic programs [0.0]
本稿では,非循環プログラムを単一ルールプログラムに分解し,任意のプログラムに対して一般的な分解結果を提供する。
プログラムの即時結果演算子は、演算子への明示的な参照を伴わずに最小モデルを計算することができる構成によって表現できることを示す。
論文 参考訳（メタデータ） (2020-09-12T11:57:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。