Ordered Boolean List (OBL): reducing the footprint for evaluating Boolean expressions.

Area of Science:

• Computer Science
• Boolean Algebra
• Algorithm Design

Background:

• Expanded Boolean Expressions (EBEs) are a subset of Boolean expressions lacking XOR or EQUAL operators.
• Efficient evaluation of EBEs is crucial for applications like Constructive Solid Geometry (CSG) rendering on SIMD architectures.
• Current methods may not fully optimize space and time complexity for large-scale EBEs.

Purpose of the Study:

• To introduce a linear time algorithm for converting EBEs into Ordered Boolean Lists (OBLs).
• To demonstrate an efficient EBE evaluation method using OBLs with minimal space requirements.
• To explore the application of OBLs in SIMD architectures and compare them with existing methods like ROBDDs.

Main Methods:

• Developed a linear time algorithm to transform an EBE into a logically equivalent OBL.
• Designed an evaluation procedure for EBEs using the generated OBL, requiring n steps and O(log log n) space.
• Analyzed the space complexity, showing 5 bits suffice for EBEs up to six billion literals.

Main Results:

• A novel algorithm converting EBEs to OBLs in linear time.
• Efficient EBE evaluation in n steps and O(log log n) space.
• Demonstrated minimal space requirements for large EBEs, with practical implications for GPU rendering.

Conclusions:

• The OBL data structure offers a highly efficient method for evaluating EBEs, particularly on SIMD architectures.
• OBLs provide a competitive alternative to ROBDDs, with potential applications in logic verification and circuit design.
• The proposed algorithm and evaluation method significantly advance the efficient processing of Boolean expressions in computational geometry and graphics.