On Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time

Simon Guilloud, Viktor KuncakarXiv 2021 · arXiv

TL;DR

This paper introduces a novel algorithm for efficiently checking the equivalence of propositional logic formulas within a specific algebraic framework called orthocomplemented bisemilattices (OCBSLs). The algorithm achieves a log-linear time complexity, significantly outperforming previous approaches and offering a practical solution for problems that are computationally challenging in standard Boolean algebra.

What Problem Does This Paper Address?

The paper tackles the problem of efficiently determining if two propositional logic formulas are equivalent. While propositional logic is fundamental in areas like SMT solvers and proof assistants, checking equivalence can be computationally expensive, often falling into coNP-complete complexity classes. This difficulty arises even for formulas that are syntactically similar but differ in the ordering of conjuncts or disjuncts. The authors propose to relax the full completeness of Boolean algebra by considering orthocomplemented bisemilattices (OCBSLs), which are a generalization of Boolean algebras that omit the distributivity law. This relaxation allows for a more efficient equivalence checking algorithm while still providing useful consistency guarantees. The core problem is to solve the "word problem" for OCBSLs, which means determining if two terms (formulas) are equal given the axioms of OCBSLs.

Methods

The core of the paper's contribution is a new algorithm that solves the word problem for OCBSLs in log-linear time. This algorithm is built upon a variation of the Aho, Hopcroft, and Ullman algorithm for tree isomorphism. The key ideas are:

  • Generalization to DAGs: The algorithm is adapted to work with Directed Acyclic Graphs (DAGs), which are a more general representation of formulas than trees, especially when dealing with commutativity.
  • Term Rewriting System: A terminating and confluent term rewriting system is developed to express the axioms of OCBSLs. This system allows for the computation of a normal form for any given term.
  • Combined Approach: The algorithm combines the DAG equivalence checking with the term rewriting system. It efficiently computes a canonical representation (normal form) for each term by traversing the DAG structure and applying rewrite rules. This allows for equivalence checking by simply comparing the computed normal forms.
  • Log-Linear Time Complexity: The algorithm achieves log-linear time complexity by carefully handling commutativity and by employing efficient data structures and techniques, such as sorting nodes in reverse topological order and using hash maps for code assignment.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm development and does not present experimental evaluations on specific datasets.

Key Insights and Ideas

  • OCBSLs as a Tractable Subtheory: The paper demonstrates that by relaxing the full axioms of Boolean algebra (specifically, omitting distributivity), one can achieve a significantly more efficient algorithm for equivalence checking. This highlights the power of identifying and exploiting algebraic substructures for computational gains.
  • DAG Equivalence for Commutativity: The adaptation of tree isomorphism algorithms to DAGs is crucial for efficiently handling commutative operations (like conjunction and disjunction) without the exponential blow-up that would occur with naive permutation checks.
  • Normal Forms for Equivalence: The development of a terminating and confluent term rewriting system provides a theoretical foundation for computing normal forms. Equivalence then becomes a matter of comparing these canonical forms, a standard technique in algebraic computation.
  • Log-Linear Time is Achievable: The paper's main achievement is demonstrating that log-linear time complexity is attainable for this problem, which was previously considered much harder. This suggests that many problems in this domain might have more efficient solutions than initially assumed.

Key Results

  • Log-Linear Time Algorithm: The paper presents an algorithm that solves the word problem for orthocomplemented bisemilattices in O(n log n) time, where n is the size of the input terms.
  • Correctness Proof: The algorithm's correctness is established through inductive proofs and the properties of terminating and confluent term rewriting systems.
  • Implementation: A minimal working implementation in Scala is provided, demonstrating the practical feasibility of the algorithm.

Limitations and Future Work

  • Focus on OCBSLs: The algorithm is specifically designed for orthocomplemented bisemilattices. While it can be adapted to weaker theories, extending it to stronger theories (like full Boolean algebras) might require different approaches or result in higher complexity.
  • No Variable Instantiation: The algorithm does not perform variable instantiation, which is a key reason for its efficiency. This means it's not a full-fledged theorem prover but rather a specialized equivalence checker.
  • Future Work: The authors suggest that the algorithm could be reinforced to decide equivalence for stronger theories in polynomial time. They also envision its use as a kernel for proof assistants and its potential application in SMT and SAT solvers, particularly for detecting non-trivial equivalences in large formulas. The implementation is available for further exploration and extension.

Summary updated

BibTeX
@misc{guilloud2021equivalence,
  author = {Simon Guilloud and Viktor Kuncak},
  title = {{On Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time}},
  year = {2021},
  eprint = {2110.03315},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2110.03315},
}
Figure