論文の概要: Power Term Polynomial Algebra for Boolean Logic

• arxiv url: http://arxiv.org/abs/2603.13854v1
• Date: Sat, 14 Mar 2026 09:22:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-17 16:19:35.446554
• Title: Power Term Polynomial Algebra for Boolean Logic
• Title（参考訳）: ブール論理のためのパワー項多項式代数
• Authors: Emanuele Sansone, Armando Solar-Lezama,
• Abstract要約: 直交正規形(CNF)と代数正規形(ANF)を橋渡しするために設計されたブール公式の表現言語であるパワー項代数を導入する。 直接CNF->ANF変換は、式が小さな断片に分解されない限り指数的な爆発を引き起こす。 我々のフレームワークは、CNF節を直接表現しながら、モノミアルの構造化されたファミリーをコンパクトに符号化する、表現自体におけるこのミスマッチに対処する。
• 参考スコア（独自算出の注目度）: 10.458069629518985
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce power term polynomial algebra, a representation language for Boolean formulae designed to bridge conjunctive normal form (CNF) and algebraic normal form (ANF). The language is motivated by the tiling mismatch between these representations: direct CNF<->ANF conversion may cause exponential blowup unless formulas are decomposed into smaller fragments, typically through auxiliary variables and side constraints. In contrast, our framework addresses this mismatch within the representation itself, compactly encoding structured families of monomials while representing CNF clauses directly, thereby avoiding auxiliary variables and constraints at the abstraction level. We formalize the language through power terms and power term polynomials, define their semantics, and show that they admit algebraic operations corresponding to Boolean polynomial addition and multiplication. We prove several key properties of the language: disjunctive clauses admit compact canonical representations; power terms support local shortening and expansion rewrite rules; and products of atomic terms can be systematically rewritten within the language. Together, these results yield a symbolic calculus that enables direct manipulation of formulas without expanding them into ordinary ANF. The resulting framework provides a new intermediate representation and rewriting calculus that bridges clause-based and algebraic reasoning and suggests new directions for structure-aware CNF<->ANF conversion and hybrid reasoning methods.
• Abstract（参考訳）: 本稿では,結合正規形式 (CNF) と代数正規形式 (ANF) を橋渡しするために設計されたブール公式の表現言語であるパワー項多項式代数を導入する。 直接CNF<->ANF変換は、式がより小さな断片(典型的には補助変数と側制約)に分解されない限り、指数的な爆発を引き起こす可能性がある。 対照的に、我々のフレームワークは、CNF節を直接表現しながら、モノミアルの構造化された族をコンパクトに符号化し、抽象レベルでの補助変数や制約を避けるという、このミスマッチに対処する。 我々は、パワー項とパワー項多項式を通して言語を形式化し、それらの意味論を定義し、ブール多項式の加算と乗法に対応する代数的操作を認めることを示す。 可分節はコンパクトな正準表現を許容し、パワー項は局所的短縮および拡張リライトルールをサポートし、原子項の積は言語内で体系的に書き換えることができる。 これらの結果と共に、公式を通常のANFに拡張することなく直接操作できる記号計算が得られる。 結果として得られたフレームワークは、節ベースおよび代数的推論をブリッジする新しい中間表現と書き換え計算を提供し、構造を意識したCNF<->ANF変換とハイブリッド推論法のための新しい方向を提案する。

関連論文リスト

• Do It for HER: First-Order Temporal Logic Reward Specification in Reinforcement Learning (Extended Version) [49.462399222747024]
  本研究では,大規模状態空間を持つ決定過程(MDP)における非マルコフ報酬の論理的仕様に関する新しい枠組みを提案する。 我々のアプローチは有限トレース(LTLfMT)上での線形時間論理モデュロ理論を利用する 本稿では,報酬マシンとHER(Hindsight Experience Replay)をベースとした一階述語論理仕様の翻訳手法を提案する。
  論文  参考訳（メタデータ） (2026-02-05T22:11:28Z)
• State Algebra for Propositional Logic [0.0]
  State Algebraは命題論理を表現および操作するためのフレームワークである。 集合、座標、Row Decompositionの3つの表現の階層として構成されている。 状態ベクトルのデフォルトの還元は正準ではないが、固定変数順序を適用することで一意な正準形式が得られることを示す。
  論文  参考訳（メタデータ） (2025-09-12T15:05:52Z)
• On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
  CoT推論による現代言語モデル(LM)の性能向上 LMは弦上の分布の族を確率的チューリングマシンと同一に表現できることを示す。
  論文  参考訳（メタデータ） (2024-06-20T10:59:02Z)
• Linearity of Relation Decoding in Transformer Language Models [82.47019600662874]
  トランスフォーマー言語モデル(LM)で符号化された知識の多くは、関係性の観点から表現することができる。 関係のサブセットに対して、この計算は対象表現上の1つの線形変換によってよく近似されることを示す。
  論文  参考訳（メタデータ） (2023-08-17T17:59:19Z)
• On Loop Formulas with Variables [2.1955512452222696]
  最近、フェラーリス、リー、リフシッツはグラウンド化に言及しない安定モデルの新たな定義を提案した。 我々は、Chen, Lin, Wang, Zhang による変数を持つループ公式のアイデアとの関係を示す。 論理プログラムの構文を拡張して、明示的な量化を許容し、その意味論を安定モデルの新しい言語のサブクラスとして定義する。
  論文  参考訳（メタデータ） (2023-07-15T06:20:43Z)
• A unified logical framework for explanations in classifier systems [10.256904719009471]
  本稿では,二項入力分類器とその性質の推論を支援するセテリスパリバスの性質のモーダル言語を提案する。 我々は、モデルの族を研究し、言語の濃度に関する2つの証明システムとしてそれを公理化し、我々の公理学の完全性を示す。 我々は、この言語を利用して反実的条件を定式化し、帰納的、対照的な、反実的説明を含む様々な説明概念を定式化する。
  論文  参考訳（メタデータ） (2021-05-30T07:49:56Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。 それらの構造的特性について検討する。
  論文  参考訳（メタデータ） (2020-12-01T13:53:23Z)

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

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