A gateway holds an allow rule and a deny rule, each already a finite automaton: when do you precompute one combined recogniser instead of running both per message?

## The two shapes The policy is *accept when the allow rule matches and the deny rule does not*, so mathematically you want the **difference** of two languages: a product of the two machines where a pair accepts when the first component accepts and the second does not. There are two ways to run that. - **Combine ahead of time.** Build the product once, materialise its reachable pairs as a table, and ship one machine that scans each message a single time. - **Compose at runtime.** Keep the two machines as they are and step both on every symbol, combining their verdicts at the end. The important observation before comparing them: composing at runtime **is** the product construction, executed lazily and thrown away after each message. There is no third algorithm. The decision is about *when* the pairs are computed and *whether* they are stored, not about which mathematics you use. ## What actually decides it - **Rule churn.** If rules change hourly, every change pays the build cost again and the combined table is stale between builds. Composing absorbs a change for free. - **Message volume relative to rebuilds.** Combining amortises: one build, many messages. The break-even moves with how many messages a rule version sees in its lifetime. - **Whether the negated side is nondeterministic.** Complement needs a deterministic total machine, so a nondeterministic deny rule must be determinised first, and that step is the one with an exponential worst case. Composing never pays it, because at runtime you can simulate the nondeterministic side as a set of current states. - **Diagnostics.** Operators ask *which* rule rejected a message. A product state is a pair and still carries both answers — but a compiled or reduced table often renames states and loses that structure, so the ability to explain a rejection is something you must deliberately preserve. - **Memory and locality.** One combined table can be larger than two small ones, and a table that no longer fits in cache can cost more per symbol than two that do. The state-count bound is a product, so this bites when both rules are large. - **Blast radius.** A combined artefact is one thing to verify, sign and roll back. Two independently updated tables are two things that can be out of step with each other. ## The cost that surprises people Engineers expect the pairing to be the expensive part and are surprised that it is polynomial and usually much smaller than its bound, because only pairs consistent with a common prefix are reachable. The expensive primitive is **negation**, and only when its operand is nondeterministic. A rule algebra that allows *not* anywhere in an expression can be forced to determinise repeatedly on intermediate results; one that pushes negation to the leaves, or requires negated rules to be written deterministically, keeps build times predictable. That is a design decision about the rule language, not about the engine, and it is the kind of call a lead is expected to own. ## Comparing the two shapes | dimension | combined machine | both machines in lockstep | |---|---|---| | build cost | product, plus a determinisation if the deny side is nondeterministic | none | | per-message work | one state lookup per symbol | one lookup per machine per symbol | | rule churn | rebuild per change | free | | rejection reason | only if pair labels are preserved | naturally available | | verification | check the artefact once, offline | check the inputs, trust the runtime | | memory | one table, up to the product bound | two smaller tables | ## How to gain confidence in the artefact Whichever you choose, the combined machine is a derived artefact and deserves to be checked rather than trusted. Treat the lockstep simulation as the reference implementation and decide equivalence against the compiled table by the standard route: pair the two, mark a pair accepting when exactly one side accepts, and search the reachable pairs for one. An empty search is a proof of agreement, and any witness it finds is a concrete message that the build step got wrong — which goes straight into the regression suite. Doing this in the release pipeline converts "the optimiser probably preserved semantics" into a checked property. ## There is no single right answer A high-volume path with rules that change on a weekly release wants the combined table; a policy console where an operator edits rules interactively and expects an explanation for every block wants the lockstep form; a system with both wants to compose while editing and combine at publish. What an interviewer is listening for is not a verdict but the axes — build versus per-message cost, where negation sits, what you lose in diagnostics, and how you prove the compiled artefact still means what the rules said.