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

Regular-expression — where it appears

A small program describing a set of strings, compiled at run time into a machine whose size is therefore a measurement rather than a constant. Matching one against a text is linear in the text on every automaton, and the folklore about it being slow is about backtracking implementations.

Named by 3 essays across 3 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 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 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.

AutomatonNondeterministic automatonBacktrackingDeterministic automatonEpsilon closureExponential timeLower boundState explosionState setSubset constructionThompson constructionWorst case

All concepts