論文の概要: A novel framework for systematic propositional formula simplification based on existential graphs
- arxiv url: http://arxiv.org/abs/2405.17072v1
- Date: Mon, 27 May 2024 11:42:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-28 15:42:27.312713
- Title: A novel framework for systematic propositional formula simplification based on existential graphs
- Title（参考訳）: 存在グラフに基づく体系的命題式単純化のための新しい枠組み
- Authors: Jordina Francès de Mas, Juliana Bowles,
- Abstract要約: 本稿では、パースの実在グラフの推論と含意グラフの規則から導かれる命題論理の単純化計算について述べる。
我々の規則は、ネスト形式の命題論理式に適用でき、同値保存であり、単調に減少する変数、節、リテラルの数を保証し、構造的問題情報の保存を最大化することができる。
- 参考スコア（独自算出の注目度）: 1.104960878651584
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: This paper presents a novel simplification calculus for propositional logic derived from Peirce's existential graphs' rules of inference and implication graphs. Our rules can be applied to propositional logic formulae in nested form, are equivalence-preserving, guarantee a monotonically decreasing number of variables, clauses and literals, and maximise the preservation of structural problem information. Our techniques can also be seen as higher-level SAT preprocessing, and we show how one of our rules (TWSR) generalises and streamlines most of the known equivalence-preserving SAT preprocessing methods. In addition, we propose a simplification procedure based on the systematic application of two of our rules (EPR and TWSR) which is solver-agnostic and can be used to simplify large Boolean satisfiability problems and propositional formulae in arbitrary form, and we provide a formal analysis of its algorithmic complexity in terms of space and time. Finally, we show how our rules can be further extended with a novel n-ary implication graph to capture all known equivalence-preserving preprocessing procedures.
- Abstract（参考訳）: 本稿では、パースの実在グラフの推論と含意グラフの規則から導かれる命題論理の単純化計算について述べる。
我々の規則は、ネスト形式の命題論理式に適用でき、同値保存であり、単調に減少する変数、節、リテラルの数を保証し、構造的問題情報の保存を最大化することができる。
また、我々の手法は、上位のSAT前処理と見なすことができ、我々のルールの1つ(TWSR)が、既知の同値保存SAT前処理手法のほとんどを一般化し、合理化しているかを示す。
さらに,この2つのルール (EPR と TWSR) の体系的適用に基づく単純化手法を提案する。
最後に、我々のルールを新しいn-ary含意グラフでさらに拡張して、既知の同値保存前処理の手順をすべて捉える方法を示す。
関連論文リスト
- From Exponential to Polynomial Complexity: Efficient Permutation Counting with Subword Constraints [0.0]
置換による異なる置換を数えることは、特に複数のサブワードを含む場合、分析における長年の課題である。
本稿では,置換による異なる置換を計算するための閉形式式を示す新しいフレームワークを提案する。
次に、新たな式を開発することにより、基本公式を複数のサブワードを扱うように拡張する。
論文 参考訳（メタデータ） (2024-11-23T19:52:11Z) - Learning Visual-Semantic Subspace Representations for Propositional Reasoning [49.17165360280794]
本稿では,特定の意味構造に適合する視覚表現を学習するための新しい手法を提案する。
我々のアプローチは、新しい核規範に基づく損失に基づいている。
部分空間格子におけるセマンティクスのスペクトル幾何学を最小エンコードしていることを示す。
論文 参考訳（メタデータ） (2024-05-25T12:51:38Z) - A Neural Rewriting System to Solve Algorithmic Problems [47.129504708849446]
ネストされた数学的公式を解くための一般的な手順を学習するために設計されたモジュラーアーキテクチャを提案する。
シンボリック人工知能の古典的なフレームワークである書き換えシステムに触発され、アーキテクチャには3つの専門的で対話的なモジュールが含まれます。
我々は、系統的な一般化に特化した最近のモデルであるNeural Data Routerと、先進的なプロンプト戦略で探索された最先端の大規模言語モデル(GPT-4)とを比較した。
論文 参考訳（メタデータ） (2024-02-27T10:57:07Z) - From Probabilistic Programming to Complexity-based Programming [0.5874142059884521]
本稿では,CompLogという新しい計算フレームワークの主な特徴と実装について述べる。
ProbLogのような確率的プログラミングシステムにインスパイアされたCompLogは、Simplicity Theoryによって提案された推論メカニズムに基づいている。
提案システムでは,ある状況の予期せぬ事柄を,元投稿や元被写体で計算することができる。
論文 参考訳（メタデータ） (2023-07-28T10:11:01Z) - A Hybrid System for Systematic Generalization in Simple Arithmetic
Problems [70.91780996370326]
本稿では,記号列に対する合成的および体系的推論を必要とする算術的問題を解くことができるハイブリッドシステムを提案する。
提案システムは,最も単純なケースを含むサブセットでのみ訓練された場合においても,ネストした数式を正確に解くことができることを示す。
論文 参考訳（メタデータ） (2023-06-29T18:35:41Z) - String Theories involving Regular Membership Predicates: From Practice
to Theory and Back [12.98284167710378]
文字列制約系に対する満足度問題に対するアルゴリズムは、対象ケースに存在する制約の構造を徹底的に理解する必要がある。
本稿では,正規表現構成述語を含む文献で提示されるベンチマークを調査し,異なる一階述語論理理論を抽出し,決定不能性を証明する。
特に、現実世界のベンチマークで最も一般的な理論はPSPACE完全であり、文字列制約を解決するためのより効率的なアルゴリズムの実装に直結する。
論文 参考訳（メタデータ） (2021-05-15T13:13:50Z) - Controllable Text Simplification with Explicit Paraphrasing [88.02804405275785]
テキストの単純化は、語彙パラフレーズ、削除、分割など、いくつかの書き換え変換を通じて文の可読性を向上させる。
現在の単純化システムは、主にシーケンス・ツー・シーケンスのモデルであり、これらすべての操作を同時に実行するためにエンドツーエンドで訓練されている。
そこで我々は,言語的に動機づけられた規則を用いて分割と削除を行い,それらをニューラルパラフレーズモデルと組み合わせて様々な書き直しスタイルを創出するハイブリッド手法を提案する。
論文 参考訳（メタデータ） (2020-10-21T13:44:40Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。