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

State explosion — where it appears

The exponential growth of a deterministic machine's state count with the expression it was built from. It is a property of the language rather than of the construction — a machine needing to remember the last k characters needs two to the k states — and it is met exactly by short expressions.

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

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 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 automatonSubset constructionCacheCrossing pointLazy constructionLower boundNondeterministic automatonRegular-expression

All concepts