State Algebra for Propositional Logic
This provides a novel algebraic framework for propositional logic manipulation, potentially benefiting areas like knowledge compilation and probabilistic logic, though it appears incremental as it builds on existing semantics.
The paper tackles the problem of representing and manipulating propositional logic by introducing State Algebra, a framework using algebraic methods with three hierarchical representations (Set, Coordinate, and Row Decomposition). The result shows that while the default state vector reduction is not canonical, a unique canonical form can be achieved with a fixed variable order, offering flexibility for more compact problem representations.
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.