Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Automaton — where it appears

A machine of states and labelled transitions consuming one symbol at a time, so a query costs its own length and nothing about what was indexed. A query costs its own length whatever was indexed, which is the property that separates an automaton from a structure searched by comparison.

Named by 8 essays across 6 fields — each of them below, with the objects they name alongside it.

roothseirhesssolid: a transition on a character · dashed: a suffix or failure link10 states for 12 pattern characters

One pass for every pattern at once

Sixty-four patterns, one text, twenty thousand characters read. Running this site's KMP once per pattern reads 1,595,445 — and an implementation missing one kind of link finds fewer occurrences, reads exactly as much, and looks better on every counter.

text · Automaton —1234152abcbcbccbsolid: a transition on a character · dashed: a suffix or failure link8 states ≤ 9, 9 transitions ≤ 11

Every substring, in fewer states than substrings

A text of 512 characters has 129,416 distinct substrings. A machine that recognises every one of them, and nothing else, needs 831 states — and the bound it is under, 2n − 1, is reached exactly by a string one line long.

structures · Automaton Thompson's NFA, a set of states43.724 to buildthe subset DFA, built in full1.011,297 to buildthe subset DFA, built on demand41.824 to buildthe state set in machine words37.224 to buildoperations per character; the note is what was paid once, before the first character4,096 characters · k = 643.7 down to 1

What a character costs on four machines

Forty-four operations, one, forty-two, and a number that moves. Four machines for one language, with the construction charged separately from the steps, because a machine that is free per character paid eleven thousand operations before the first one.

machine · Automaton 110100k, the operators after the alternationstatesits DFA: 512its NFA: 30a literal's DFA: 11alphabet ab2^(k+1), exactly

The exponential is in the expression

The subset construction on one family reaches two to the k plus one states, exactly and not approximately. A literal of the same length gives eleven. Both are regular expressions and the difference is that one of them asks the machine to remember something.

bounds · Automaton 0a1b2split3split4a5a6b7split8a9b10split11a12b13split14accept9 character tests · 5 splits · 1 accepting(a|b)*a(a|b)(a|b)(a|b)15 states

Two states per operator

Thompson's construction adds a bounded number of states per rule and no rule copies a sub-machine, so the machine is linear in the expression and is built in linear time. Every exponential in this field is somewhere else.

structures · Automaton 10010³10⁴10³10⁴10⁵characters of textoperations, construction includedcrosses at 256the NFAthe DFA64 DFA statescrosses at 256 characters

Where the table starts paying

Five thousand and sixty-five operations before the first character, then one per character. Against nothing before the first character and thirty-nine per character. They cross at two hundred and fifty-six characters, and that crossing is what an engine's compile decision actually is.

practice · Automaton 10100states the cache holdsoperations a characterthe plain NFA: 52.5the whole set fits: 19.94,096 characters · k = 8the knee is at 512 states

A cache below the reachable set

A lazy machine with a cache of two hundred and fifty-six states costs fifty-one operations a character and a plain non-deterministic simulation costs fifty-three. At five hundred and twelve it costs eleven. The line is flat across two orders of magnitude and then falls off a cliff.

wrong · Automaton 1010³10⁴10⁵10⁶characters of textstepsbacktrackingThompson's NFAopen points: capped at4,000,000(a|a)*b12,158x at 20 characters

The folklore is about a matcher

Four million steps against three hundred and twenty-nine, on a twenty-character expression matched against twenty characters. One of the two machines doubles with every character of the input and the other does not, and only one of them is what a regular expression is.

wrong · Automaton

Named alongside it

The objects these essays reach for when they reach for this one.

Nondeterministic automatonDeterministic automatonLazy constructionRegular-expressionSubset constructionAlphabetAmortised analysisCrossing pointEpsilon closureIndexMeasured countState explosion

All concepts