# RePair upper bound — Siebert et al. (2026)

Publication-based design review, 2026-09-19. This is an independent C++17
implementation of a published method, not a port of the authors' software.

## Sources and scope

- Siebert, Chowdhury, Slocombe and Walker, *Assembly Spaces: Formal Definitions
  and Fast Methods for Approximating Assembly Indices*,
  [arXiv:2606.15499v1](https://arxiv.org/abs/2606.15499v1), pp. 28–29,
  “Upper Bound”; pp. 24–25 supply the string grammar/path correspondence.
- Original RePair: Larsson and Moffat (2000), *Off-line Dictionary-Based
  Compression*, [DOI](https://doi.org/10.1109/5.892708). The original author's
  [1999 dissertation](https://inf.ufes.br/~raulh/ufes/teaching/courses/ds/texts/larsson99.pdf),
  Sections 7.2–7.3.2, was also read to resolve occurrence counting: equal-symbol
  runs are counted and replaced without overlap, scanning left to right.

The published name is **RePair**; “RePair upper bound — Siebert et al. (2026)”
identifies the assembly adaptation. `repair-upper-bound` is our protocol ID,
not a claimed name from the paper. It supports strings and molecular graphs.
The general producing-join solver remains available for arbitrary assembly spaces.

## Algorithm decisions

Repeatedly choose the most frequent adjacent token pair with at least two
nonoverlapping occurrences and replace those occurrences by a fresh token.
Count across all sequences, never across sequence boundaries. Stop when no pair
repeats. Convert the grammar and its residual sequences into binary assembly
joins. Molecular input is first partitioned into edge-disjoint simple paths,
compressed jointly, and assembled path by path before joining the paths.
The paper calls these paths “trails” and explicitly defines their vertex degrees.

The following deterministic conventions fill gaps in the assembly paper; they
are not claimed to reproduce the authors' software or figure values:

| Unspecified choice | Convention here |
| --- | --- |
| Equal-frequency pair | Lexicographically smallest pair of token IDs; initial IDs follow first encounter and new IDs increase |
| Molecular path partition | Start at the left endpoint of the first unused input bond; extend along the first unused incident bond to an unvisited vertex; repeat |
| Molecular token/orientation | Ordered `(element, bond order, element)` in path traversal direction; no reversal search |
| Residual sequence assembly | Left-to-right binary joins |
| Path recombination | First available pair whose edge union is connected, in partition order |

Larsson's dissertation leaves ties unspecified in the abstract algorithm, then
describes a least-recently-accessed choice in its implementation. We implement
the abstract pair-selection method, not that particular priority-queue policy.
Frequency rescanning is used for clarity (polynomial, not a claimed linear-time
implementation). String adaptation currently uses the common finite substring
representation; its preprocessing cost is included in timing.

The common domain layer identifies equal constructed objects and retains their
first producing join, as required by assembly-space reuse. It does not change
the grammar's token IDs, pair frequencies or selected replacements. Removing
unreferenced definitions when emitting a rooted certificate is representation
normalization, not another search. No alternative path partitions, restarts,
branch-and-bound, improved tie search or cross-engine incumbents are used.

## Status, safety and verification contract

A completed run reports `exact: false, reason: heuristic`, even when its bound
happens to equal an independently known optimum. A deadline or cancellation
retains only an already validated complete construction. An elementary
one-unit-at-a-time construction is the interruption fallback, not a search seed
or source of compression choices. Preparation, graph identity and certificate
validation consume the same deadline and process limits.

`candidate_pathways_considered` counts completed RePair pathway candidates
(normally one), not branch-and-bound subspaces. Separate CLI diagnostics count
replacement rounds and replaced occurrences. Comparisons must label these work
units rather than treating them as equal work across algorithms.

Tests must cover independently specified replacement traces, overlapping runs,
boundaries between sequences, Unicode, exhaustive small-string bounds, molecular
path partitions, checked joins, deadlines, output limits and rejection of custom
spaces. A valid witness certifies an upper bound, not publication fidelity; this
design record and trace tests address the latter separately.

## Provenance and licensing

The arXiv article is offered under CC BY 4.0; the associated software has a
separate MIT license. No source, figures or expressive pseudocode are imported
into this implementation. Earlier project research inspected that software, so
this is not described as clean-room work. See [SOLVER_INTEGRATION.md](SOLVER_INTEGRATION.md)
for the wider audit. No new license is assigned to the owner's repository and
no patent/freedom-to-operate conclusion is implied.