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

Bit-parallel — where it appears

Holding a state set in a machine word so that advancing all of it is a few word operations. It is a constant factor rather than a change of class, and on a construction whose free transitions point anywhere the closure is an iterated union rather than a shift.

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

—sitting—kitten111111101111110-1111110-1-111110-1-1-11110-1-1-10110-1-1-10-11one unit = one subproblem given a value-1, 0, 1 — 3 values, 2 bits each

A column computed in machine words

Adjacent cells of a distance table differ by at most one, so a whole column is two bits per cell — and thirty-two of them fit in one register. Fifteen word operations per character replace three cell evaluations per cell, and below a pattern of fifteen characters the trade is a loss.

machine · Machine 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

Named alongside it

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

AutomatonBranchlessCarry propagationCost modelCrossoverDeterministic automatonDynamic programmingEdit distanceEpsilon closureLazy constructionLocalityMachine word

All concepts