Elamur Groupants⌕
☰

algorithm-minimal-rotation

The groupant beside algorithms/src/minimal_rotation/mod.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.

Facts

Implementation material. A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised.

Components

componentlabelwhere
approximantpartialapproximant
astpartialsyntax.json
descriptantpresentdescriptant
invariantpartialapproximant
testsexisting checks referencedtests

Obernants

The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.

idtypelabelwhere
behavior_complementbehavior_complementpartial source derived modelbehavior_complement
reverse_reconstructionreverse_reconstructionpartial source derived modelreverse_reconstruction
periodic_tieperiodic_tiepartial source derived modelperiodic_tie
cyclic_arithmeticcyclic_arithmeticpartial source derived modelcyclic_arithmetic
order_embeddingorder_embeddingpartial source derived modelorder_embedding

Model text

descriptant

Description and epoch memory

2026-10-30: original implementation and independent finite oracles added. For bytes s, return the smallest i among all indices whose rotation s[i..]+s[..i] is lexicographically minimal. Return 0 for the empty slice.

Prospective design: use a single u64 state and fixed byte masks for Shift-And; eliminate candidate intervals without a doubled buffer for minimum rotation. Predicted costs: O(n) comparisons/time, O(1) auxiliary storage and no allocation. After a mismatch, matched+1 candidates are eliminated and one candidate advances by that amount; equal comparisons are charged to the following advance or final n-match tie. No doubled string or 2*n arithmetic is used. No benchmark or speed claim is made.

Retained observations: empty-pattern terminal boundaries, top-bit masks and periodic earliest ties require explicit fixtures; a result index or match vector loses input identity. Saturated rotation advancement denotes exhaustion, not a wrapped candidate.

Classical attribution is in mod.rs: Baeza-Yates and Gonnet, CACM 35(10), 1992, 74–82; Booth, IPL 10(4–5), 1980, 240–242. No copied implementation. Partial syntax excludes macro expansion, name resolution and semantic AST. Finite observations and structural acceptance do not constitute a proof.

approximant

Forward, invariant and cost

For bytes s, return the smallest i among all indices whose rotation s[i..]+s[..i] is lexicographically minimal. Return 0 for the empty slice.

Two distinct surviving starts are in 0..n while comparing; matched<n. A first mismatch after matched equal bytes eliminates the losing candidate and the intervening matched starts. Advancing saturates at exhausted sentinel n; modular lookup adds only when start+offset<n. At a full-period tie the smaller surviving start is selected, preserving the earliest minimal rotation.

O(n) comparisons/time, O(1) auxiliary storage and no allocation. After a mismatch, matched+1 candidates are eliminated and one candidate advances by that amount; equal comparisons are charged to the following advance or final n-match tie. No doubled string or 2*n arithmetic is used.

Implementation observation: one successful call and its exact returned value; no process or allocator timing is modeled.

The test oracle uses independent window enumeration (132253 text-pattern pairs) or sorting all materialized rotations (9841 ternary strings through length eight). Test-oracle cost is O(n*m) per matcher case and O(n^2 log n) per rotation case, including materialization. These oracle costs do not describe production complexity.

models

Typed models

All entries bind the adjacent manifest source revision. Domain and observation are stated per relation; these are source-derived specifications with finite correspondence evidence, not proofs. Implementation observation: one successful call and its exact returned value; no process or allocator timing is modeled.

behavior_complement

Universe: finite byte strings and usize outcomes. Empty input excludes every outcome except zero. Nonempty input excludes i>=n, every i whose rotation is larger than any competing rotation, and any i with an equal rotation at a smaller index. This is a concrete exact complement specification, not a finite sample extrapolation.

reverse_reconstruction

For observed i retain all strings for which rotation i is minimal and no earlier index ties it; i=0 additionally admits empty input. abc and xyz both map to zero. Positive output does not determine length, alphabet, period, or bytes. Complete fiber enumeration is not implemented.

periodic_tie

If s is k copies of primitive word w and its minimal rotation starts at r<|w|, all r+j|w| tie, but only r is returned. baba selects 1 rather than 3; constant strings select 0. Status: source-derived mathematical relation; checked by the adjacent named tests on bounded inputs, with no general semantic proof.

cyclic_arithmetic

For start,offset<n, modular position is offset-(n-start) if offset>=n-start, otherwise start+offset. This avoids overflow even at n=usize::MAX; private helper tests exercise this arithmetic independently of allocatable slices. Status: source-derived mathematical relation; checked by the adjacent named tests on bounded inputs, with no general semantic proof.

order_embedding

A strictly increasing injective byte relabeling preserves every rotation comparison and the returned index. It cannot reconstruct original byte labels; abc and xyz witness this observation loss. Status: source-derived mathematical relation; checked by the adjacent named tests on bounded inputs, with no general semantic proof.

tests

Evidence

Four named tests per module, each repeated twice in debug and twice in release. Independent exhaustive byte-window and all-rotation oracles; literal empty/overlap/top-bit/periodic fixtures; arithmetic helper boundary checks. Production and false-oracle mutation controls must compile and fail named assertions. Final evidence receipt records hashes and outcomes. No live parser, corpus, teacher, GPU or timing experiment.

See evidence.md for final source bindings, named mutation witnesses, repeated outcomes and raw receipt hashes.

evidence

Final evidence, 2026-10-30

Eight tests total: four per module, each passed twice in debug and twice in release with equal sorted named outcomes. Shift-And exhaustive oracle: 1093 texts times 121 patterns = 132253 comparisons. Rotation oracle: 9841 strings. Additional high-byte, 64-bit, overlap, empty and periodic fixtures; arithmetic helpers tested at usize::MAX. Four compiled controls were rejected by equality assertions and exact source restoration passed all eight tests. Strict all-target algorithm Clippy and narrow rustfmt pass. Four partial syntax projections generated twice identically; full-registry scaffold structural reports repeat identically and have no diagnostics. Scaffold parent manifests were restored and are not committed. No benchmark, semantic proof or live system run is claimed.

Source bindings
Raw receipt hashes

Raw files are retained in the external wave14 strings run bundle.

Rejected controls

Shift-And removes the start bit and fails word_boundaries_and_overlaps. Rotation changes min to max and fails periodic_and_byte_boundaries. The window oracle inverts equality and fails exhaustive_windows. The rotation oracle reverses ordering and fails exhaustive_all_rotations. Each log contains a compiled test run and named equality assertion failure.

This page in Markdown → https://md.groupants.elamur.ai/free/en/mova/algorithms/src/minimal_rotation/mod.rs.groupant/