Relational semantics of a quotienting expression

Exact statement

Interpreting $0,1$ , letters, union, concatenation, and star respectively as the empty relation, identity, partial-derivative edges, union, relational composition, and reflexive-transitive closure on $Q_B$ gives $(P,Q)\in\llbracket A\rrbracket_B$ exactly when some $u\in L(A)$ satisfies $Q\in\partial_u(P)$ .

StatusProved by structural induction

External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

The lemma converts the language denoted by A into finite reachability among partial derivatives of B.

Definitions

Letter $c$ denotes the relation $\{(P,Q):Q\in\partial_c(P)\}$ .
On $N=|Q_B|$ states, reflexive-transitive closure is the union of path relations of lengths $0,\ldots,N-1$ .

Hypotheses and scope

Q_B is finite and closed under one-letter partial derivatives.

Proof or evidence

The cases for 0, 1, letters, union, and concatenation follow directly from the regular-expression and relational operations. The star case concatenates finitely many A-words; cycle deletion bounds the witnessing state path by N−1.

Relational semantics lemma →

Verification notes

The proof record checks both directions of every constructor and distinguishes a state-path bound from a bound on word length.

Limitations

The auxiliary relation is finite but is not itself a regular-expression subterm.

Open work

Obtain an independent check of the star case and its finite path bound.