Skip to content
STIMSMITH

Approximate Union Operation

Concept WIKI v1 · 6/18/2026

The Approximate Union Operation (denoted ∪∼) is a bitwise combination operator defined on data set expressions in symbolic ternary simulation. It produces a conservative (over-approximating) result when the exact set-theoretic union of two data sets cannot be represented precisely in ternary form, and it is the mechanism by which the Efficient Memory Model (EMM) merges data from possibly-overlapping memory list entries during a Read operation.

Overview

In the symbolic ternary simulation framework used to verify pipelined microprocessors by correspondence checking, memory contents are represented as data set expressions (DSExpr) whose bits are pairs drawn from {0, 1, X} (low and high Boolean halves). Because the X value denotes uncertainty over both 0 and 1, the bitwise-OR of two data set expressions is not in general equal to the exact set-theoretic union of the two sets. To obtain a value that is guaranteed to be a conservative (super-set) approximation, the framework defines a dedicated operator called the approximate union, written with a tilde over the union symbol:

[d1 ∪∼ d2]i = [d1.hi ∨ d2.hi, d1.li ∨ d2.li],   i = 1, ..., w

where w is the data width, and d.hi / d.li denote the high and low Boolean halves of bit i of data set expression d.

Why Approximation Is Needed

A naive bitwise combination of two data set expressions over-approximates the union. For example, given

  • d1 = ⟨0, 1⟩ (representing data set {0})
  • d2 = ⟨1, 0⟩ (representing data set {1})

the result of d1 ∪∼ d2 is ⟨X, X⟩, which denotes the full data set {0, 1}. This is a superset of the exact union (which is also {0, 1} in this case), but the over-approximation becomes evident when d1 = ⟨0, 1⟩ and d2 = ⟨1, 0⟩ are combined with other values: the bitwise X interpretation also admits the data sets ⟨0, 0⟩ and ⟨1, 1⟩, which are not subsets of either d∼1 or d∼2. The approximate union therefore trades precision for a guarantee that the result is a sound (conservative) cover of both operands.

Role in the Efficient Memory Model (EMM)

The Efficient Memory Model represents a memory array as an ordered list of entries ⟨h, s, a, d⟩, where h and s are Boolean control expressions, a is an address set expression, and d is a data set expression. During a Read operation, the EMM walks the list from head (low priority) to tail (high priority) and, for each entry whose address overlaps the read address a under contexts captured by soft_match, selects

rd ← ITE(soft_match, (ed ∪∼ rd), rd)

That is, the new running data set expression rd is set to the approximate union of the previously accumulated value and the current entry's data ed. This use of the approximate union is what allows the EMM to provide a conservative approximation of a real memory array: when the exact data for an address cannot be determined statically, the EMM soundly reports a superset of the possible values rather than an under-approximation. Boolean expressions in the implementation are represented using Ordered Binary Decision Diagrams (OBDDs), although any Boolean representation supporting a Valid() test can be substituted.

Notation and Symbol

The operator is consistently typeset in the source as a union symbol with a tilde (∼) above it (e.g., ∪∼), distinguishing it from the set-theoretic union. It applies element-wise across all w bits of two DSExprs.

See Also

  • Read Operation (EMM) — the list-walking routine that consumes ∪∼ while accumulating read results.
  • Efficient Memory Model (EMM) — the memory-array abstraction in which this operator is the soundness-preserving merge step.

LINKED ENTITIES

2 links
Read Operation (EMM) USES
Efficient Memory Model (EMM) PART_OF

CITATIONS

5 sources
5 citations
[1] The Approximate Union Operation is defined element-wise as [d1 ∪∼ d2]i = [d1.hi ∨ d2.hi, d1.li ∨ d2.li] for i = 1, ..., w, where d.hi and d.li are the high and low Boolean halves of each bit. Verification of Pipelined Microprocessors by Correspondence Checking in Symbolic Ternary Simulation
[2] The operation is approximate rather than exact because ternary bitwise combination yields X-bits that over-approximate the union; e.g., d1 = ⟨0,1⟩ combined with d2 = ⟨1,0⟩ yields ⟨X,X⟩ which also admits ⟨0,0⟩ and ⟨1,1⟩. Verification of Pipelined Microprocessors by Correspondence Checking in Symbolic Ternary Simulation
[3] The Read operation of the EMM uses the approximate union in the soft_match branch as rd ← ITE(soft_match, (ed ∪∼ rd), rd) when scanning the memory list from head to tail. Verification of Pipelined Microprocessors by Correspondence Checking in Symbolic Ternary Simulation
[4] The approximate union is the mechanism by which the EMM provides a conservative approximation of the replaced memory array, ensuring that the reported read data soundly covers all possible values. Verification of Pipelined Microprocessors by Correspondence Checking in Symbolic Ternary Simulation
[5] Boolean expressions (including those used in the approximate union) are represented with Ordered Binary Decision Diagrams (OBDDs) in the implementation, though any Boolean representation supporting a Valid() test can be substituted. Verification of Pipelined Microprocessors by Correspondence Checking in Symbolic Ternary Simulation