Natural Boolean-product prefix automata are event-signature expansions

Exact statement

For a flat Boolean-product expression with marked ordinary components, the natural backward prefix automaton is isomorphic to the useful canonical product of the component prefix automata after splitting every noninitial product state $q$ into one copy for each incoming event signature $(a,S)\in\operatorname{Sig}(q)$ . Hence $|Q_{\mathrm{Pre}}|=1+\sum_{q\ne q_0}|\operatorname{Sig}(q)|$ .

StatusSelf-contained structural proof with exact projection audit

External reviewNo documented external or specialist review of these FPRD results is recorded.

Context

The component-prefix product records the current component states; the natural backward prefix construction additionally records which global event entered that product state.

Hypotheses and scope

The Boolean-product expression is flat and its components are ordinary regular expressions.
The event-support policy is memoryless.
The comparison uses states and edges lying on accepting runs.

Proof or evidence

The generalized final-event factorization removes the terminal marked letter in participating coordinates, preserves stuttering coordinates, and appends one global event. This gives mutually inverse state maps between natural prefixes and product-state/signature pairs and preserves every edge and final state.

Event-signature expansion theorem →

Verification notes

The exact checker audits 16,448 signature-expansion projections through arity three.

Limitations

Nested Boolean products are not included in the theorem statement.
Novelty is plausible but unconfirmed; no external review is recorded.

Open work

Compare the event-signature expansion directly with the 2026 paper's Glushkov and follow constructions.