Search research articles

ABOUT JoVE

Overview Leadership Blog JoVE Help Center

AUTHORS

Publishing Process Editorial Board Scope & Policies Peer Review FAQ Submit

LIBRARIANS

Testimonials Subscriptions Access Resources Library Advisory Board FAQ

RESEARCH

JoVE Journal Methods Collections JoVE Encyclopedia of Experiments Archive

EDUCATION

JoVE Core JoVE Business JoVE Science Education JoVE Lab Manual Faculty Resource Center Faculty Site

Terms & Conditions of Use

Related Concept Videos

Block Diagram Reduction

Block Diagram Reduction

The process of deriving the transfer function of a control system often involves reducing its block diagram to a single block. This simplification can be achieved through a series of strategic operations, including relocating branch points and comparators. These operations preserve the overall function of the system while allowing for easier manipulation and combination of blocks.
The first step in this process is the identification and relocation of a branch point. A branch point, where a...

Rationalizing Substitutions

Rationalizing Substitutions

Integrals involving non-rational functions are often difficult to evaluate using standard techniques, especially when radicals appear in the integrand. Rationalizing substitution provides a systematic method for simplifying such integrals by converting them into rational forms that are easier to handle.Consider a rod whose linear mass density depends on a constant linear density, a characteristic length, and the distance from the left end of the rod. Determining the total mass requires...

Algebraic Expressions

Algebraic Expressions

Algebraic expressions are essential in mathematics. They represent relationships through variables, constants, and operations. These expressions help describe patterns and solve problems in various mathematical fields. Understanding their components, classifications, and operations allows for efficient simplification and manipulation.Each algebraic expression consists of individual parts, including numbers and symbols, that work together to form meaningful mathematical statements. The numerical...

Rational Expressions

Rational Expressions

Rational expressions are algebraic fractions in which both the numerator and the denominator are polynomials. These expressions follow the arithmetic rules of numerical fractions but require extra care due to the presence of variables. A fundamental part of working with rational expressions is identifying values that make the expression undefined, typically those that result in division by zero or undefined radicals.Determining the DomainThe domain of a rational expression includes all real...

Relation between Mathematical Equations and Block Diagrams

Relation between Mathematical Equations and Block Diagrams

In a spring-mass-damper system, the second-order differential equation describes the dynamic behavior of the system. When transformed into the Laplace domain under zero initial conditions, this equation can be effectively analyzed and manipulated. The transformation into the Laplace domain converts differential equations into algebraic equations, simplifying the process of isolating the output.

Elements of Block Diagrams

Elements of Block Diagrams

Block diagrams serve as a visual representation of the input-output relationships within a system. An illustrative example is a heating system, where the set temperature activates the furnace to warm the room to the desired level. Block diagrams are versatile, modeling linear systems through Laplace transform variables and nonlinear systems using time domain variables.
A block diagram typically includes essential elements such as comparators, blocks, and feedback loops. Each of these elements...

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by

Same author

Ball-morph: definition, implementation, and comparative evaluation.

IEEE transactions on visualization and computer graphics·2011

See all related articles

Search research articles

Related Experiment Video

Updated: May 31, 2026

Complete and Partial Resuscitative Endovascular Balloon Occlusion of the Aorta for Hemorrhagic Shock

Complete and Partial Resuscitative Endovascular Balloon Occlusion of the Aorta for Hemorrhagic Shock

Published on: May 19, 2022

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

Jaroslaw Jarek Rossignac¹

¹School of Interactive Computing, Georgia Institute of Technology, Atlanta, GA 30308-0760, USA. rossignac@gatech.edu

IEEE Transactions on Visualization and Computer Graphics

|July 9, 2011

Summary

We present an algorithm to convert Expanded Boolean Expressions (EBEs) into Ordered Boolean Lists (OBLs). This conversion enables efficient EBE evaluation with minimal space, ideal for SIMD architectures and GPU rendering.

More Related Videos

Hierarchical and Programmable One-Pot Oligosaccharide Synthesis

Hierarchical and Programmable One-Pot Oligosaccharide Synthesis

Published on: September 6, 2019

Related Experiment Videos

Last Updated: May 31, 2026

Complete and Partial Resuscitative Endovascular Balloon Occlusion of the Aorta for Hemorrhagic Shock

Complete and Partial Resuscitative Endovascular Balloon Occlusion of the Aorta for Hemorrhagic Shock

Published on: May 19, 2022

Hierarchical and Programmable One-Pot Oligosaccharide Synthesis

Hierarchical and Programmable One-Pot Oligosaccharide Synthesis

Published on: September 6, 2019

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.