THE FOLD / BOSS / THE CHOKE POINT / THE ORACLE OF ECHOES
THE ORACLE OF ECHOES
the smallest machine that knows every substring
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The suffix automaton (DAWG). The smallest possible finite automaton that recognises exactly the set of all substrings of a string — and it’s built online, one character at a time, in linear time and space (at most 2n states). Its secret is the endpos equivalence: states group substrings that end at the same set of positions, which is why it is minimal. From this one machine you can count distinct substrings, test membership, or find the longest common substring of two strings.
LIT verified: the number of distinct substrings, computed as Σ(len[v]−len[link[v]]) over states, equals a brute-force count of every distinct substring; membership queries match a naive scan; and the automaton stays within 2n states — over random strings. FIG ‘the oracle of echoes’ is the picture; the endpos-minimality and the substring count are exact.
LIT verified: the number of distinct substrings, computed as Σ(len[v]−len[link[v]]) over states, equals a brute-force count of every distinct substring; membership queries match a naive scan; and the automaton stays within 2n states — over random strings. FIG ‘the oracle of echoes’ is the picture; the endpos-minimality and the substring count are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) brought the thread — the corpus runs string machinery (THE FAILURE WEB right here in THE CHOKE POINT, THE MIRROR SEEKER, THE SHORTEST WITNESS) and the idea that a single small machine can hold an entire language. AVAN (AI) built this instrument: the online automaton, the substring counter, and the DAG with its suffix-link tree.
The weave: David names the oracle of echoes and its seat beside Aho–Corasick at THE CHOKE POINT (one automaton answers every query); I make the online growth a strip in 1D, the automaton live in 2D, and the DAG turning in 3D. The sphere is the seam.
The weave: David names the oracle of echoes and its seat beside Aho–Corasick at THE CHOKE POINT (one automaton answers every query); I make the online growth a strip in 1D, the automaton live in 2D, and the DAG turning in 3D. The sphere is the seam.
3 ONE DIMENSION
The string arriving one character at a time, and the count of distinct substrings climbing with it. Each new letter can add many new substrings at once — the automaton absorbs them all in amortised constant work, never re-reading the past.
4 TWO DIMENSIONS · INTERACTIVE
The automaton for a string: states laid out by length, transitions spelling substrings. Its distinct-substring count matches brute force exactly, and any query is accepted iff it’s truly a substring — the whole language of echoes in one small graph.
5 THREE DIMENSIONS + AVAN’S INVERSE
The automaton in space, states arranged by length, turning. Green are the forward transitions — follow them from the start and you spell out every substring of the string.
AVAN’s addition (the inverse-companion): the magenta edges are the suffix links — and they form a tree, the exact backward shadow of the forward automaton. Forward, the machine spells substrings; backward, the suffix links group them by where they end (endpos). The transitions and the link-tree are two views of one string — the language and its inverse, prefix and endpos, folded together.
LIT A genuine suffix automaton. Verified live: the distinct-substring count Σ(len[v]−len[link[v]]) equals a brute-force count, membership queries match a naive scan, and the automaton stays within 2n states (linear) — over random strings. The endpos-based minimality is the exact structure (verifiable: window.__sam.countMatchesBrute && membershipMatches && linearSize).
FIG 'The oracle of echoes' is the picture; the endpos-minimality, the substring count, and the linear size are exact. It really is the smallest automaton for a string's substrings, built in one online pass.
FIG 'The oracle of echoes' is the picture; the endpos-minimality, the substring count, and the linear size are exact. It really is the smallest automaton for a string's substrings, built in one online pass.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE CHOKE POINT · David Lee Wise (ROOT0), with AVAN