Power Term Polynomial Algebra for Boolean Logic

• URL: http://arxiv.org/abs/2603.13854v1
• Date: Sat, 14 Mar 2026 09:22:52 GMT
• Title: Power Term Polynomial Algebra for Boolean Logic
• Abstract summary: We introduce power term algebra, a representation language for Boolean formulae designed to bridge conjunctive normal form (CNF) and algebraic normal form (ANF)<n>The language is motivated by the 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.<n>Our framework addresses this mismatch within the representation itself, compactly encoding structured families of monomials while representing CNF clauses directly.
• Score: 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.

Related papers

• A Compositional Theory of Causally Masked Transformers [50.88598486616582]
  We develop a formalization that derives expressivity directly from the model's implemented dynamics.<n>Each attention head updates its own state independently within a layer.<n>A modified form of soft attention supports irreversible, checklist-like state.
  arXiv  Detail & Related papers  (2026-07-29T14:47:19Z)
• An Algebraic View of the Expressivity of Recurrent Language Models [50.88598486616582]
  The paper develops a unified algebraic account of the expressivity of recurrent neural networks.<n>The same architecture cannot implement an even-modulus counter once floating-point recurrences are enforced, yet realizes every even-modulus counter under unsigned-integer quantization.
  arXiv  Detail & Related papers  (2026-06-01T06:47:58Z)
• Geometric Factual Recall in Transformers [57.48371649045765]
  A common view casts internal weight matrices as associative memories over pairs of embeddings, requiring memorization counts that scale linearly with the number of facts.<n>We develop a theoretical and empirical account of an alternative, emphgeometric form of memorization in which learned embeddings encode structure directly.<n>In a controlled setting where a single-layer transformer must memorize random vectors from subjects to a shared attribute set, we prove that a logarithmic embedding dimension suffices.<n>We extend these results to the multi-hop setting, providing constructions with and without chain-of-thought that exhibit a provable
  arXiv  Detail & Related papers  (2026-05-12T17:22:22Z)
• Do It for HER: First-Order Temporal Logic Reward Specification in Reinforcement Learning (Extended Version) [49.462399222747024]
  We propose a novel framework for the logical specification of non-Markovian rewards in Decision Processes (MDPs) with large state spaces.<n>Our approach leverages Linear Temporal Logic Modulo Theories over finite traces (LTLfMT)<n>We introduce a method based on reward machines and Hindsight Experience Replay (HER) to translate first-order logic specifications and address reward sparsity.
  arXiv  Detail & Related papers  (2026-02-05T22:11:28Z)
• State Algebra for Propositional Logic [0.0]
  State Algebra is a framework to represent and manipulate propositional logic.<n>It is structured as a hierarchy of three representations: Set, Coordinate, and Row Decomposition.<n>We show that although the default reduction of a state vector is not canonical, a unique canonical form can be obtained by applying a fixed variable order.
  arXiv  Detail & Related papers  (2025-09-12T15:05:52Z)
• Homomorphic Encryption of Intuitionistic Logic Proofs and Functional Programs: A Categorical Approach Inspired by Composite-Order Bilinear Groups [0.0]
  We present a conceptual framework for extending homomorphic encryption beyond arithmetic or Boolean operations into the domain of intuitionistic logic.<n>We outline strategies for making the approach potentially efficient, including software optimizations and hardware acceleration.
  arXiv  Detail & Related papers  (2025-02-26T10:10:10Z)
• On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
  Chain-of-thought (CoT) reasoning has improved the performance of modern language models (LMs)<n>We show that LMs can represent the same family of distributions over strings as probabilistic Turing machines.
  arXiv  Detail & Related papers  (2024-06-20T10:59:02Z)
• Linearity of Relation Decoding in Transformer Language Models [82.47019600662874]
  Much of the knowledge encoded in transformer language models (LMs) may be expressed in terms of relations. We show that, for a subset of relations, this computation is well-approximated by a single linear transformation on the subject representation.
  arXiv  Detail & Related papers  (2023-08-17T17:59:19Z)
• On Loop Formulas with Variables [2.1955512452222696]
  Recently Ferraris, Lee and Lifschitz proposed a new definition of stable models that does not refer to grounding. We show its relation to the idea of loop formulas with variables by Chen, Lin, Wang and Zhang. We extend the syntax of logic programs to allow explicit quantifiers, and define its semantics as a subclass of the new language of stable models.
  arXiv  Detail & Related papers  (2023-07-15T06:20:43Z)
• A unified logical framework for explanations in classifier systems [10.256904719009471]
  We present a modal language of a ceteris paribus nature which supports reasoning about binary input classifiers and their properties. We study a family of models, axiomatize it as two proof systems regarding the cardinality of the language and show completeness of our axiomatics. We leverage the language to formalize counterfactual conditional as well as a variety of notions of explanation including abductive, contrastive and counterfactual explanations.
  arXiv  Detail & Related papers  (2021-05-30T07:49:56Z)
• Polynomial Graph Parsing with Non-Structural Reentrancies [0.2867517731896504]
  Graph-based semantic representations are valuable in natural language processing. We introduce graph extension grammar, which generates graphs with non-structural reentrancies. We provide a parsing algorithm for graph extension grammars, which is proved to be correct and run in time.
  arXiv  Detail & Related papers  (2021-05-05T13:05:01Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.