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

Lazy construction — where it appears

Building a deterministic machine's states on demand rather than in full, with a bounded cache. It decides when an exponential is paid rather than whether: a text long enough reaches every state, and a cache below the reachable set is worth nothing at all.

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

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 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

Named alongside it

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

AutomatonDeterministic automatonCrossing pointNondeterministic automatonSubset constructionBit-parallelCacheEpsilon closureOperation countState explosion

All concepts