OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

Theorem 1.1: One fixed algorithm has a finite-alphabet bit-machine implementation and a guarantee measured in symbols

A polynomial-time factor-two superstring algorithm.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

The shortest common superstring problem asks for a word of minimum length that contains every input word as a contiguous substring. The input words may overlap in the output. The objective counts symbols, although a symbol itself may require several bits to describe.

A symbol is a finite binary string, so the symbol alphabet is Σ={0,1}*\Sigma=\{0,1\}^{*}.✦ A word T∈Σ*T\in\Sigma^{*} is a finite sequence of symbols, and |T||T| is its symbol length.✦ An instance S=(s1,…,sr)S=(s_1,\ldots,s_r) is a finite list of words; repetitions and empty words are allowed.✦ The input alphabet consists of the symbols appearing in these words.✦

A substring ss of a word TT is a word for which T=xsyT=xsy for some words xx and yy, either of which may be empty. Write s⊑Ts\sqsubseteq T for this relation. The set 𝒞(S)\mathcal C(S) of common superstrings of SS is defined by (1). 𝒞(S)={T∈Σ*:s⊑T for every s∈S}.\mathcal C(S) =\{T\in\Sigma^{*}: s\sqsubseteq T\text{ for every }s\in S\}.(1)✦ The optimum OPT(S)\mathrm{OPT}(S) is the minimum symbol length in (2); the minimization ranges over all words in Σ*\Sigma^{*}. OPT(S)=min⁡{|T|:T∈𝒞(S)}.\mathrm{OPT}(S)=\min\{|T|:T\in\mathcal C(S)\}.(2)✦

The substring graph has as vertices the empty word and all distinct substrings of the input words.✦

The maximal input words are the distinct nonempty input words that are not proper substrings of another input word.✦

The distinct substrings of a word include the empty word and all words obtained by taking a prefix after deleting an initial segment.✦

The Bit-machine Model

For a finite list X=(x1,…,xr)X=(x_1,\ldots,x_r) and a map ee from its entries to binary strings, the list representation Ee(X)E_e(X) is the binary string in (3). Juxtaposition denotes concatenation, and 00 and 11 denote single bits. Ee(X)=0e(x1)0e(x2)⋯0e(xr)1,Ee(())=1.E_e(X)=0e(x_1)\,0e(x_2)\cdots 0e(x_r)\,1, \qquad E_e(())=1.(3)✦ Starting with the identity map id\mathrm{id} on single bits, the symbol, word and instance representations eΣe_{\Sigma}, eWe_W and eIe_I are the successive applications of (4). eΣ=Eid,eW=EeΣ,eI=EeW.e_{\Sigma}=E_{\mathrm{id}},\qquad e_W=E_{e_{\Sigma}},\qquad e_I=E_{e_W}.(4) The input bit length NN and the total input symbol length LL are the distinct quantities in (5). N=|eI(S)|,L=∑i=1r|si|.N=|e_I(S)|,\qquad L=\sum_{i=1}^{r}|s_i|.(5)

A function ff from instances to words has a polynomial bit-machine implementation, denoted 𝖯𝗈𝗅𝗒(f)\mathsf{Poly}(f), if a deterministic Turing machine computes eW(f(S))e_W(f(S)) from eI(S)e_I(S) in time bounded by a polynomial in NN, with a finite alphabet on every machine stack.✦ The machine and its polynomial bound are fixed independently of SS.

A bit stack store on a set KK of stack names assigns each stack a finite sequence of bits, with the first bit at the top.✦

For a set KK of private stack names, the public and private stacks comprise two public stacks indexed by zero and one and one private stack for each member of KK.✦

A bit stack program on stacks named by KK is built from pushing a bit, popping a stack, doing nothing, branching according to whether a stack is empty or starts with zero or one, sequential composition, and loops that repeat a body while a designated stack is nonempty.✦

An execution with instruction count records a bit stack program, its initial and final stores and its primitive instruction count; a push, pop or do-nothing instruction costs one, and a push or pop changes only its designated stack.✦ A branch costs one plus its selected execution, sequential composition adds the two execution counts, an empty loop costs one, and a nonempty loop costs one plus the body and remaining loop counts.✦

A linearly parsable encoding ee of values in a set XX is an injective binary encoding that admits a linear prefix scanner.✦

A linear prefix scanner for an encoding ee is a fixed bit stack program with a constant cc that, for every value xx, suffix and accumulator, consumes the initial code e(x)e(x) from one public stack and prepends its reversal to the accumulator on the other, leaving the suffix untouched.✦ It uses at most c(|e(x)|+1)c(|e(x)|+1) instructions and has empty private stacks before and after the scan.✦

For an update FF, a value xx with a linearly parsable encoding and a bound BB, the space bounded update replaces xx by F(x)F(x) when the encoding length of F(x)F(x) is at most BB and retains xx otherwise; it retains the same bound BB.✦

Write AA for the executable superstring algorithm fixed by the library.

A substring graph walk PP is a finite list of words recording its successive visited vertices.✦

The substring graph adjacency test accepts a pair of words precisely when the second is obtained from the first by appending one symbol or deleting its first symbol.✦

The graph walk validity test accepts a nonempty walk precisely when every visited word is allowed and every consecutive pair passes the adjacency test.✦

The appending edge count of a walk is the number of consecutive pairs in which the symbol length increases; in a valid walk, an up step appends one symbol and costs one, and a down step deletes the first symbol and costs zero.✦

For words ss and tt, the appended edge symbol is the one-symbol word consisting of the last symbol of tt when |s|<|t||s|<|t|, and the empty word otherwise.✦

The walk output word consists precisely of the symbols appended on up steps, in traversal order.✦

The successive symbol appending walk from a word aa with appended word bb visits aa followed by every prefix of bb, in increasing prefix length.✦

The successive symbol deletion walk for words aa and bb visits the words obtained from abab by deleting zero through |a||a| initial symbols.✦

The concatenation of walks PP and QQ is PP followed by QQ with its first vertex omitted.✦

A rooted tour is a walk starting and ending at the empty word; rooted tour concatenation joins a list of such tours in order, starting with the tour consisting only of the empty word.✦

The rooted word excursion of ww appends its symbols successively from the empty word and then deletes its first symbols successively back to the empty word.✦

The cyclic rotation of a walk at index ii concatenates its suffix starting at ii with its prefix ending at ii, omitting the repeated junction vertex.✦

Tour splicing inserts a cyclic rotation of QQ into PP at their first shared vertex in PP, choosing the first occurrence of that vertex in QQ; an unsuccessful search uses index zero.✦

Tour insertion of QQ into PP at index ii concatenates the prefix of PP through ii, then QQ, then the suffix of PP starting at ii, omitting the repeated junction vertices.✦

Successive tour splicing inserts a list of tours into a walk from left to right.✦

Rooting a tour at a vertex ww appends ww from the empty word, traverses the tour cyclically from that vertex, and deletes ww back to the empty word; an absent vertex index uses the empty word.✦

Rooting a tour at a short word with bound pp roots it at the first visited word of length at most pp, using index zero if there is none.✦

The isolated symbol excursion of ww starts at the empty word and appends and deletes each symbol of ww separately.✦

The rooted walk test accepts a valid walk precisely when its first and last vertices are the empty word.✦

The computed word multiplicities m(w)m(w) come from a table initially zero on every graph vertex, updated simultaneously one more time than the maximum vertex length, with every update subject to the initial counting workspace bound.✦

The counting iteration bound uses maximum zero when the vertex list is empty.

For a multiplicity table mm, the left extension multiplicity of ww is the sum of m(cw)m(cw) over input symbols cc, with extensions outside the graph contributing zero.✦

For a multiplicity table mm, the right extension multiplicity of ww is the sum of m(wc)m(wc) over input symbols cc, with extensions outside the graph contributing zero.✦

Fix a default symbol; the candidate periodic text generated by a word vv with period parameter pp takes its symbol at integer coordinate xx from position xx modulo pp in vv, using that symbol for an absent position.✦

The periodic prefix test accepts a word ww when each of its symbols agrees with the corresponding position of the candidate periodic text.✦

A blocking occurrence of ss in rr at position jj has a nonempty part of rr on each side, every interior symbol of rr agrees with the candidate periodic text aligned at jj, and both endpoint symbols disagree with that alignment.✦

The blocking occurrence count is the number of starting positions satisfying the blocking occurrence test; overlapping occurrences are counted separately.✦

The weighted blocking count BA(s;m)B_A(s;m), with AA denoting the substring graph vertex set in this notation, is the sum over graph words rr of the number of blocking occurrences of ss in rr times m(r)m(r).✦

For positive integers pp and kk, a nonempty word ww and a graph word vv with |v|=|w|+kp|v|=|w|+kp, the periodic multiplicity constraint is BA(w;m)+k+1B_A(w;m)+k+1 if both words match the candidate periodic text generated by vv with parameter pp and BA(v;m)<m(v)B_A(v;m)<m(v); otherwise it is zero.✦

The constraints from one word vv take the maximum periodic multiplicity constraint over parameters pp and kk from zero through |v||v|.✦

The maximum periodic constraint for ww is the maximum of its constraints from all graph words, with zero included.✦

The word multiplicity update is zero for the empty word and for words outside the graph; otherwise it is the maximum of the indicator that the word is a maximal input word, the left and right extension multiplicities, and the maximum periodic constraint.✦

A multiplicity table update replaces every graph word count by its word multiplicity update, calculating all new values from the old table.✦

The downward edge multiplicity d(w)d(w) is the computed count m(w)m(w) minus its right extension multiplicity, with subtraction truncated at zero.✦

The downward edge word list repeats each graph vertex ww exactly d(w)d(w) times.✦

An indexed word token consists of a natural-number identifier and a word✦; the suffix matching requests retain the identifiers of the indexed downward edge words and delete the first symbol of each word.✦

The indexed word tokens of a word list pair each word with its position in the list, starting at zero, so equal words at different positions have different identifiers.✦

A greedy prefix matching update chooses the first longest outstanding request, matches it to the first available token whose word extends its prefix, removes every copy of each selected token from its corresponding list, and prepends their pair to the matching; an empty request list is unchanged and an absent extension uses the empty word with identifier zero.✦

Greedy prefix matching starts with request tokens, available tokens and no pairs, and applies the matching update once for every initial request.✦

When no request is available, the longest available request is the empty word with identifier zero.

The computed prefix matching greedily matches the suffix matching requests to the indexed downward edge words.✦

The computed permutation edges connect the identifiers of the two tokens in each computed matching pair.✦

A thread representation consists of a list of words and permutation edges connecting their indices.✦

For a list EE of permutation edges and an index ii, the permutation successor is the second coordinate of the first edge whose first coordinate is ii, or zero if there is no such edge.✦

The computed thread representation uses the downward edge word list and its computed permutation edges.✦

For a thread representation with nn words, the periodic signature at an index is the sequence of first symbols encountered in 2n2n successive permutation steps, using the default symbol when the indexed word is absent or empty.✦

Two thread indices pass the compatibility test when some permutation step count below the word count takes the first to an index with the same periodic signature as the second.✦

The representative of a thread index is the least compatible index below the word count, with zero as the fallback.✦

The thread group representatives are the indices equal to their own least compatible thread index.✦

The aligned thread indices of a group are the indices whose periodic signatures equal that of the group index.✦

The thread signature period is the least positive step count at most the word count that returns to the same periodic signature, or zero if no such step exists.✦

The thread period word is the prefix of the periodic signature whose length is the thread signature period.✦

The ranked thread word length at phase rr and rank jj is the least threshold from zero through the encoding length of the thread representation for which more than jj aligned indices have word length at most that threshold after rr permutation steps, with zero as the fallback.✦

The ranked layer exit lengths list the ranked thread word lengths over all phases below the thread signature period.✦

A periodic layer is specified by a period word and a list of exit lengths indexed by phase✦; the thread group layer data consist of the thread period word and the ranked layer exit lengths for ranks below the number of aligned thread indices.✦

Periodic layer group data consist of a period word and one list of exit lengths for each layer.✦

A collection environment consists of layer group data, active group indices and a stride for indexing layers globally✦; the thread collection environment lists the layer data at every thread index, uses the thread group representatives as its active groups, and takes the word count as its layer indexing stride.✦

A collection context specifies allowed graph vertices, a collection environment and a bound for completion searches✦; the computed collection context uses the substring graph vertices, the collection environment obtained from the computed thread representation, and the counting iteration bound.✦

For an integer-indexed text AA and integer endpoints a,ba,b, the finite text window A[a,b)A[a,b) lists its symbols from aa through b−1b-1 and is empty when b<ab<a.✦

An integer interval is specified by two integer endpoints and is interpreted as a half-open window.✦

The two-sided periodic text of a word UU takes its symbol at integer coordinate xx from position xx modulo |U||U| in UU, using the default symbol when absent.✦

A periodic text window of UU on [a,b)[a,b) is the word read from its two-sided periodic text at those coordinates, and is empty when b<ab<a.✦

The cyclic word shift of UU by displacement dd is its periodic text window of length |U||U| starting at −d-d.✦

For period words U,WU,W and an integer displacement dd, the periodic text inequality test compares the window of UU starting at zero with the window of WW starting at displacement dd, both of length |U||W||U||W|, and accepts precisely when they differ.✦

For a list ZZ of exit lengths, the periodic exit coordinate at integer position xx is xx plus the exit length indexed by xx modulo the length of ZZ, using zero for an absent entry.✦

The preceding exit coordinate at xx is the periodic exit coordinate at x−1x-1.✦

At phase rr, let aa be the preceding exit coordinate and bb the current exit coordinate; the layer contents at that phase are the periodic text windows starting at rr and ending at a+ia+i, for offsets ii from zero through the nonnegative part of b−ab-a.✦

The periodic layer contents concatenate the layer contents at all phases below the period word length.✦

The short layer words are the words in the periodic layer contents whose symbol lengths do not exceed the period word length.✦

The one-period layer tour starts at phase zero and follows successive single-position passages for as many positions as the period word length, appending to each current exit and deleting the first symbol to advance the start, using the layer exit lengths.✦

Selected layer saturation successively splices the one-period tours of the selected layers into a walk, using empty exit lengths for an absent layer.✦

Complete layer saturation successively splices the one-period layer tours of all listed layers into a walk.✦

The saturated rooted word tour of ww saturates its rooted word excursion with the selected layers.✦

For the short word layer tour, saturate the rooted excursion of the first short layer word with that layer, using the empty word when there is no short layer word.✦

Saturating the rooted excursion of the periodic text window from the specified phase to the preceding exit of the upper boundary layer with the selected layers gives the rooted upper layer tour.✦

For lower and upper exit functions l,hl,h, phase tt, period pp and displacement multiplier kk, put E=l(t)E=l(t) and H=h(t−1)H=h(t-1); the geometric band walk stays at A[t,E)A[t,E) when H≤EH≤E, and otherwise appends to HH and connects to the base window translated by kpkp.✦

For the saturated band walk, use the exit functions of the two boundary layers and the period word length to saturate the geometric band walk with the selected layers.✦

The geometric collective walk from A[a,b)A[a,b) first appends to the larger of bb and the upper exit immediately before aa, then connects to A[a+kp,b+kp)A[a+kp,b+kp).✦

The saturated collective walk is obtained from the geometric collective walk by saturation with the selected layers; this uses the upper boundary exit function and a translation of one period for each selected layer.✦

For an exit function zz, the geometric individual walk sets ee to the larger of bb and z(a+p−1)z(a+p-1), connects A[a,b)A[a,b) to A[a+p,e)A[a+p,e) and appends from ee to b+pb+p.✦

Saturating the geometric individual walk with its single selected layer gives the saturated individual walk, using that layer’s exit function and the period word length.✦

For an initial window A[a,b)A[a,b), an upper exit function hh, phase tt, period pp and layer count kk, the geometric short sweep puts K=kpK=kp, takes xx to be the smaller of tt and a+Ka+K, sets F=h(x−1)F=h(x-1), deletes to start xx, appends to stop FF and connects to A[a+K,b+K)A[a+K,b+K).✦

For the saturated short sweep, apply saturation to the geometric short sweep with the selected layers, using the upper boundary exit function and a translation of one period for each selected layer.✦

Layer band attachment splices the saturated band walk into the current walk, with displacement multiplier equal to the selected layer count.✦

The window prefix deletion walk successively deletes the window A[a,c)A[a,c) from the front of A[a,c)A[c,b)A[a,c)A[c,b), retaining A[c,b)A[c,b).✦

The window suffix appending walk starts at A[a,b)A[a,b) and successively appends the symbols of A[b,d)A[b,d).✦

The window connection walk from endpoints (a,b)(a,b) to (c,d)(c,d) first deletes to start cc and appends to stop dd when c≤bc≤ b; otherwise it deletes to the empty window at bb, makes the isolated symbol excursion on A[b,c)A[b,c), and appends A[c,d)A[c,d).✦

Successive window connections start at the specified initial window and concatenate the connection walks through the remaining windows in list order, omitting their repeated initial vertices.✦

Endpoint sum ordering stably orders a list of integer intervals by the sum of their endpoints.✦

Ordered window traversal connects the initial window through the list of windows in endpoint sum order and then to the specified final window.✦

For an integer translation qq, the host window excursion appends from the base window A[a,e)A[a,e) to stop bb, traverses the requested windows in endpoint sum order, and connects the last window to A[a+q,e+q)A[a+q,e+q), using (a,b)(a,b) as the last window when the list is empty.✦

For an integer displacement pp, the shifted window attachment connects A[s,h)A[s,h) to A[a+p,e+p)A[a+p,e+p) and then to A[s+p,h+p)A[s+p,h+p).✦

For an exit function zz, the single-position passage at xx appends from the preceding exit z(x−1)z(x-1) to z(x)z(x) while keeping start xx, and then deletes the first symbol to advance the start to x+1x+1.✦

For an initial position tt and a nonnegative step count nn, the periodic segment walk starts at A[t,z(t−1))A[t,z(t-1)) and concatenates the single-position passages at t,t+1,…,t+n−1t,t+1,…,t+n-1, omitting repeated junction vertices.✦

An overlap record consists of an integer alignment displacement and integer start and stop coordinates.✦

An overlap record with displacement dd and interval [a,b)[a,b) is valid for period words U,TU,T and target exit function zz when a≤ba≤ b, z(a+d−1)≤b+d≤z(a+d)z(a+d-1)≤ b+d≤ z(a+d), and the periodic text windows of UU on [a,b)[a,b) and TT on [a+d,b+d)[a+d,b+d) agree.✦

For displacement bound qq, phase tt and search bound MM, the bounded overlap record candidates have displacement from zero through q−1q-1, start t−M+it-M+i for 0≤i≤M0≤ i≤ M, and stop t+1+jt+1+j for 0≤j<M0≤ j<M.✦

The lexicographically greatest rotation phase is the first phase below |U||U| whose full-length periodic text window is at least every other such rotation, using zero if there is none.✦

A layer catalogue is a list of layers, each specified by a period word and its exit lengths.✦

Upper completion parameters consist of a selected layer count, a target catalogue index and an overlap record.✦

For layer count mm and cutoff cc, the upper layer indices are c,c+1,…,m−1c,c+1,…,m-1, with none when m≤cm≤ c.✦

The upper completion candidates list every selected count from zero through the layer bound, each specified target index, and every bounded overlap record for that target, using the target word length as the displacement bound.✦

The foreign periodic text test accepts when the group period word and the selected target word pass the periodic text inequality test at the recorded displacement.✦

For mm layers of period pp, cutoff cc, phase tt, selected count kk and record [a,b)[a,b), the upper completion admissibility test requires 0<k≤m−c0<k≤ m-c, a valid overlap record, a≤t<ba≤ t<b, top preceding exit at most b+kpb+kp, and top preceding exit minus the exit at tt of layer m−km-k at most (k−1)p(k-1)p.✦ It also requires every upper layer below m−km-k to have preceding exit at aa at most bb.✦

Admissible upper completion selection takes the first candidate satisfying both the upper completion admissibility test and the specified foreign predicate, using zero for every parameter if there is none.✦

A closure block specifies source and target identifiers, layer indices, an overlap word, a period, a cost reserve, an internal walk and candidate linking walks.✦

A block closing action specifies a list of blocks to remove and a proposed replacement walk.✦

A closure state consists of the current walk and the remaining closure blocks.✦

Closure block assembly shifts selected layer indices by the given offset, takes the overlap word from the periodic text window, and assigns a block of kk layers of period pp a reserve of 2kp2kp.✦

An individual closure block uses the one-period tour of its single layer internally and its saturated individual walk as its sole linking walk.✦

A collective closure block uses the saturated band walk with displacement multiplier one less than its selected layer count internally, and offers the saturated collective walk and saturated short sweep as linking walks.✦

The layer coverage test accepts a walk when it visits every word in the contents of each specified layer, treating an absent layer as empty.✦

A closure action is admissible when its new walk is rooted and valid, its cost is at most the current cost plus the reserves of the removed blocks, it retains every old visited word, and it covers all layers of each removed block.✦

The single-block actions remove one block and either concatenate its internal walk rooted at a word no longer than its period or splice one of its linking walks into the current tour.✦

A paired-block action removes two blocks, splices the second block’s internal walk into a linking walk of the first, roots the result at a word no longer than the second period, and concatenates it to the current tour.✦

The closure action candidates list each single-block action and each paired-block action for distinct blocks.✦

Admissible closure selection takes the first admissible candidate, or removes no blocks and keeps the current walk if there is none.✦

The block closure update replaces the current walk by the selected action’s walk and removes its selected blocks from the remaining list.✦

The block closure tour is the walk left after one block closure update per initial block, with every update subject to the initial closure workspace bound.✦

A layer distribution result consists of a walk, a list of closure blocks and a list of layer indices to transfer.✦

Single-layer distribution uses a short word layer tour when the layer has a short word; otherwise it creates an individual closure block when the overlap stop is at most the layer exit at the overlap start plus the period, and leaves the layer for transfer in the remaining case.✦ The last two cases use the tour consisting only of the empty word.✦

Multiple-layer distribution applies single-layer distribution to every selected layer, concatenates their rooted tours, and concatenates their block and transfer lists.✦

Overlap record distribution takes the selected layers at or above the lower boundary as a collective block when the overlap stop is at most the lower boundary exit at the overlap start plus their number times the period, distributing the lower selected layers individually.✦ Otherwise it distributes all selected layers individually.✦

With layer indexing stride hh, the global layer indices list the numbers gh+igh+i for each active group gg and each local layer index ii below the number of layers in that group.✦

A collection plan consists of a walk, closure blocks and layer transfer requests✦, each of which specifies a source group, a target layer, source layer indices and an overlap record.✦

The reserve of a layer transfer request for kk source layers of period pp is 2kp2kp.✦

A scheduler state consists of the unprocessed group indices and the current collection plan.✦

The group cost allowance for mm layers of period pp is 2mp2mp.✦

The collection plan budget is its walk’s appending edge count plus all its block reserves and request reserves.✦

The remaining collection budget is the current plan budget plus the cost allowances of all unprocessed groups.✦

The canonical group phase is the lexicographically greatest rotation phase of its period word.✦

Minimum-period group selection chooses the first remaining group whose period is no larger than every other remaining group period, using zero if the list is empty.✦

The initial collection state has every active group unprocessed, the tour consisting only of the empty word, and no blocks or requests.✦

The incoming group requests are precisely the requests whose target layer belongs to that group.✦

The global layer catalogue lists the period word and exit lengths at each global index below the number of group data entries times the indexing stride.✦

The global layer contents list the periodic layer contents of every layer in the global catalogue.✦

A host overlap entry consists of a source identifier, a period word, overlap start and stop coordinates, and a required coverage endpoint, all coordinates being integers.✦

Shifting a host entry by an integer displacement cyclically shifts its period word, adds the displacement to its three coordinates and retains its source identifier.✦

Request attachment data consist of a period word, a source window and an attachment window.✦

For host period qq, base entry bb and source entry ee, the entry attachment data use the period word of ee and its window from the overlap start to the coverage endpoint.✦ The attachment window starts at the smaller of the source start plus its period word length and the base start plus qq, and stops at the larger of the source coverage endpoint and the base stop.✦

The periodic request attachment is the shifted window attachment in the periodic text of its request period word, using that word’s length as the period and the two request windows.✦

For period qq and intervals [a,b)[a,b) and [a0,b0)[a_0,b_0), first choose the displacement taking aa to a0a_0 plus the nonnegative remainder of a−a0a-a_0 modulo qq; the periodic normalization displacement is this displacement if it moves bb to at least b0b_0, and one period more otherwise.✦

Entry periodic normalization shifts an entry by the periodic normalization displacement determined by its overlap interval and the base overlap interval.✦

The other source entries relative to a base entry are the entries whose source identifiers differ from its source identifier.✦

The rooted host excursion constructs the host window excursion in the host word’s periodic text, successively splices the periodic request attachments into it and roots the result at the first word within the specified length bound.✦

The normalized host tour uses the base entry’s overlap interval and coverage endpoint for the rooted host excursion, takes the base period word length as its rooting bound and obtains attachment data from the other source entries.✦

The normalized request tour first normalizes every entry relative to the chosen base with period equal to the host word length, then forms the normalized host tour.✦

The host request tour candidates take each host entry in turn as the base of a normalized request tour.✦

The saturated host tour candidates apply complete layer saturation to every host request tour candidate, including the host layer and all requested layers.✦

A request host entry carries the source group identifier, the source period word shifted by the recorded displacement, the displaced overlap endpoints and the source layer’s preceding exit at the overlap start shifted by that displacement.✦

A recipient tour is admissible when it is rooted and valid, covers the recipient layer and every requested source layer, and costs at most twice the recipient group period plus the sum of the request reserves.✦

The recipient tour candidates are the saturated host tour candidates for the target layer, with the host entries and layer data obtained from its requests.✦

Recipient tour selection takes the first admissible recipient tour candidate, using the default walk if there is none.✦

The recipient layer indices of a group are its local layer indices with at least one request targeting that layer.✦

The incoming request tour concatenates the selected rooted recipient tours for the recipient layers, using at each layer exactly the requests targeting it.✦

Hard-case distribution distributes the upper layers according to the selected overlap record, with lower boundary equal to the layer count minus the selected count and upper boundary equal to the top layer, using the canonical group phase.✦

The hard-case collection plan keeps the distributed tour and blocks and creates one transfer request for the unassigned layers if there are any.✦

Upper layer completion keeps the current tour when no upper layers remain; otherwise it uses a rooted upper layer tour when the top preceding exit minus the phase is at most the number of upper layers times the period.✦ If that fails, it attaches a layer band when the cutoff is positive and the top preceding exit minus the exit at the phase of the layer below the cutoff satisfies the same bound; in the remaining case it selects admissible foreign completion parameters and concatenates the resulting hard-case plan.✦

Lower layer preparation begins with the tour assembled from incoming requests and returns cutoff zero if no layer receives a request.✦ Otherwise it takes the largest index of a layer receiving a request, uses the first request there to attach the layers through that index that receive no request along its displaced overlap interval, and returns the cutoff immediately above that recipient.✦

The group collection plan applies upper layer completion to the cutoff and tour returned by lower layer preparation.✦

The group processing update leaves the scheduler state unchanged when no unprocessed group remains.✦ Otherwise it chooses the first remaining group of minimum period, forms its collection plan from its incoming requests, removes that group from the unprocessed list, concatenates the new tour, appends the new blocks and replaces the incoming requests by the new requests, retaining the other pending requests.✦

The group collection sweep starts from the initial collection state and performs one group processing update per active group, each subject to the initial scheduler workspace bound.✦

The completed collection tour applies block closure to the group collection sweep, using its accumulated tour and blocks, the allowed vertices and the global layer contents.✦

The requests at one layer are precisely the pending requests whose target is that layer.✦

The unprocessed group requests retain the requests whose target layer belongs to a different group.✦

Host entry expansion lists a request host entry for every source layer in every request.✦

The requested layer data list the catalogue layers at every source layer index specified by the requests.✦

The Claim

Theorem 1. There is a deterministic algorithm ff from instances to words with the properties in (6). 𝖯𝗈𝗅𝗒(f),f(S)∈𝒞(S),|f(S)|≤2OPT(S)for every finite instance S.\mathsf{Poly}(f),\qquad f(S)\in\mathcal C(S),\quad |f(S)|\leq 2\,\mathrm{OPT}(S) \quad\text{for every finite instance }S.(6)✦ For the fixed algorithm AA and every finite instance SS, the output satisfies (7). A(S)∈𝒞(S),|A(S)|≤2OPT(S).A(S)\in\mathcal C(S),\qquad |A(S)|\leq 2\,\mathrm{OPT}(S).(7)✦ The implementation property of this same algorithm is (8). 𝖯𝗈𝗅𝗒(A).\mathsf{Poly}(A).(8)✦

What Is Checked

The claims range over finite lists of words with arbitrary finite binary strings as symbols, using contiguous substring containment, the unrestricted optimum and the specified binary input and output representations.