Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.10326 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911151432925184 |
|---|---|
| author | Lesnik, Dmitry Schäfer, Tobias |
| author_facet | Lesnik, Dmitry Schäfer, Tobias |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10326 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | State Algebra for Propositional Logic Lesnik, Dmitry Schäfer, Tobias Artificial Intelligence Logic in Computer Science 03G27 (Primary) 68W30, 68T27 (Secondary) 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. |
| title | State Algebra for Propositional Logic |
| topic | Artificial Intelligence Logic in Computer Science 03G27 (Primary) 68W30, 68T27 (Secondary) |
| url | https://arxiv.org/abs/2509.10326 |