# State Algebra for Propositional Logic

arXiv: https://arxiv.org/abs/2509.10326 · HTML: https://mlsanity.com/paper/2509.10326/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 0 of its 6 references that are in the map.
- First posted on arXiv 12 Sep 2025.

## Built on by (most cited first, 1 of 1)

- [State Algebra for Probabilistic Logic](https://mlsanity.com/paper/2603.13574/) (2026)

## Abstract (arXiv)

This paper presents State Algebra, a novel framework designed to represent and manipulate propositional logic using algebraic methods. The framework is structured as a hierarchy of three representations: Set, Coordinate, and Row Decomposition. These representations anchor the system in well-known semantics while facilitating the computation using a powerful algebraic engine. A key aspect of State Algebra is its flexibility in representation. 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 during the reduction process. This highlights a trade-off: by foregoing guaranteed canonicity, the framework gains increased flexibility, potentially leading to more compact representations of certain classes of problems. We explore how this framework provides tools to articulate both search-based and knowledge compilation algorithms and discuss its natural extension to probabilistic logic and Weighted Model Counting.