For a line-rate stream sensor, how do you choose between simulating a nondeterministic acceptor per symbol and determinising it ahead of time?

## Three strategies, one language All three accept exactly the same strings. The choice is purely about resource placement, which is what makes it a design decision rather than a correctness one. 1. **Simulate.** Keep the live subset explicitly. Per symbol: union the successors of every live state, close under epsilon moves, test for an accepting member. 2. **Determinise eagerly.** Run the subset construction to completion before any traffic arrives, then match with one table lookup per symbol. 3. **Determinise lazily.** Start with only the initial subset. On a symbol with no row yet, compute the successor subset once, store it, and continue. Subsets that traffic never reaches are never built. | | Simulate | Eager table | Lazy table | |---|---|---|---| | Build cost before traffic | none | full construction, up to `2^n` subsets | none | | Per-symbol work | proportional to live set and edges | one lookup | one lookup, plus a construction step on a miss | | Memory | `n` bits of live set | table for every reachable subset | table for the subsets traffic actually reaches | | Worst case | predictable, bounded | table may be unbuildable | cache growth or thrash under hostile input | | Latency shape | steady, higher | flat and lowest | flat once warm, spikes on misses | ## The questions that actually decide it **How big can the table get for the machines you generate?** The `2^n` figure is a bound, not a forecast: the construction builds only reachable subsets, and for ordinary machines that is a small number. If your machines are generated from a fixed catalogue, measure the reachable subset count for the real catalogue and you may find the eager table is a few thousand rows, which settles the argument. If machines are supplied by users, you cannot measure in advance and must assume the worst. **What does the latency budget care about — the mean or the tail?** At line rate the tail usually wins. Simulation has a *higher but steady* per-symbol cost. An eager table has the flattest cost of the three. A lazy table has the eager cost once warm, with a spike whenever it misses. If your budget is expressed as a high percentile, a warm lazy table and an eager table look alike, and simulation's steady overhead may still be acceptable while a cold lazy table's spikes are not. **Who chooses the input?** This is the question that most often flips the decision. Lazy construction's memory is driven by the *subsets the input reaches*, so an adversary who can steer the stream can walk it through fresh subsets on purpose, forcing either unbounded growth or constant eviction and rebuilding. That turns an amortised win into a sustained cost exactly when you least want it. **What happens when the ceiling is hit?** A lazy strategy needs an answer, decided up front: - **Evict and rebuild** — bounded memory, but a thrashing workload pays construction repeatedly; - **Fall back to simulation** — the subset is always computable directly, so correctness is never at risk and the degradation is a slowdown rather than a failure; - **Reject the machine at build time** — refuse to accept a machine whose bound you cannot meet. The second is usually the right default: simulation is the floor that every other strategy is an optimisation over, so keeping it available makes the cache a pure performance device. ## A defensible default For a sensor at line rate over machines you generate yourself: **measure the reachable subset count, and if the eager table fits your memory budget with headroom, build it up front.** The flat per-symbol cost is worth real money and the failure mode is a build-time error rather than a production surprise. Move to lazy construction when the catalogue is large enough that most subsets are never touched, and pair it with a hard cache ceiling and a simulation fallback. Choose pure simulation when machines arrive from outside your control, when memory is the scarce resource, or when predictability matters more than the last few nanoseconds per symbol. ## What a good answer sounds like The weak version argues abstractly for "the fastest one". The strong version names the measurement that would settle it — reachable subsets for the real catalogue, the percentile the budget is written against, and who controls the input — then commits to a default and states the fallback for when the assumption behind it breaks.