Show HN: State Algebra, new algebraic framework for logic, an alternative to BDD
My co-author and I just published a paper on arXiv that formalises a framework we've been using successfully in probabilistic logic for many years. We decided it was time to properly lay out its foundations for classical propositional logic.
We cast propositional logic into a formal algebra where logical formulas are represented by sparse matrices. State Algebra isn't an algorithm in itself, but rather a language for manipulating Boolean functions. It provides a new set of tools that lets you express and reformulate existing optimization heuristics (like those from modern SAT solvers) and design completely new ones. State Algebra is trading the strict canonicity of ROBDDs for greater representational flexibility.
For those interested in abstract-algebraic logic, we build a self-contained formalism from the ground up. The core building block is an object we call a "t-object," which forms the basis of the algebra. It provides a different way to look at the structure of logical problems.
The algebra naturally extends to handle real-valued coefficients, which turns it into a tool for probabilistic logic and Weighted Model Counting.
The paper is a bit of a deep dive into the maths, but we'd love to hear your thoughts. We'll be in the comments to answer any questions. Critiques are very welcome!
No comments yet