OctoInformBeta

OpenAI preprint, September 2026 · §4. Connection operations · §4

Lemma 4.1: Exact costs for finite chains and a short visited word for two windows

Connecting ordered windows by hierarchical walks.

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

Two occurrences in a common text determine window words that may overlap or be separated by a gap. A connection between these words is a walk that appends symbols on the right and deletes symbols on the left.

Let α\alpha be an alphabet. An integer-indexed text AA over α\alpha is a function A:ℤ→αA\colon\mathbb Z\to\alpha. For an integer-indexed text AA over α\alpha and integers a,ba,b, the finite text window Ta,bT_{a,b} of AA is the word on the half-open interval [a,b)[a,b), with reversed endpoints giving the empty word, as defined in (1): Ta,b=(A(a+i))0≤i<max⁡{0,b−a}.T_{a,b}=\bigl(A(a+i)\bigr)_{0\le i<\max\{0,b-a\}}.(1)✦

A substring-closed vertex set V⊆α*V\subseteq\alpha^* is a set of words containing every contiguous substring, including the empty word, of each of its words.✦

A hierarchical walk PP in VV is a finite directed walk with all vertices in VV, whose up steps append one symbol on the right and whose down steps delete the first symbol.✦ Stationary walks at vertices of VV are allowed. Two walks can be concatenated when the last vertex of the first is the first vertex of the second.

The cost c(P)c(P) of a hierarchical walk PP is its number of up steps.✦ A stationary walk and a down step have cost zero, and costs add under concatenation. The visited set Vis⁡(P)\operatorname{Vis}(P) of a hierarchical walk PP is the set of its actual vertices, including both endpoints.✦

The Claim

Theorem 1. Let V⊆α*V\subseteq\alpha^* be substring-closed, and let A:ℤ→αA\colon\mathbb Z\to\alpha be a text such that the one-letter word [A(x)][A(x)] belongs to VV for every x∈ℤx\in\mathbb Z.

Let a,b,c,da,b,c,d be integers with a≤ba\le b, c≤dc\le d, a≤ca\le c and b≤db\le d, and suppose Ta,bT_{a,b} and Tc,dT_{c,d} belong to VV. There are a hierarchical walk PP from Ta,bT_{a,b} to Tc,dT_{c,d} and a word ww satisfying (2): c(P)=d−b,w∈Vis⁡(P),|w|≤max⁡{0,b−c}.c(P)=d-b,\qquad w\in\operatorname{Vis}(P),\qquad |w|\le\max\{0,b-c\}.(2)✦

Let ai,bi∈ℤa_i,b_i\in\mathbb Z, indexed by i∈ℕi\in\mathbb N, be two nondecreasing sequences, and let n∈ℕn\in\mathbb N. Suppose ai≤bia_i\le b_i and Tai,bi∈VT_{a_i,b_i}\in V for every 0≤i≤n0\le i\le n. There is a hierarchical walk QQ from Ta0,b0T_{a_0,b_0} to Tan,bnT_{a_n,b_n} satisfying (3): c(Q)=bn−b0,Tai,bi∈Vis⁡(Q)(0≤i≤n).c(Q)=b_n-b_0,\qquad T_{a_i,b_i}\in\operatorname{Vis}(Q)\quad(0\le i\le n).(3)✦

What Is Checked

The statements concern hierarchical walks in a substring-closed vertex set and windows of an integer-indexed text whose one-letter words belong to that set, with the window starts and ends ordered in the direction of the walk.