FPRD LabShare an approach

← Claims

Theorem · canonical target observer

FPRD-LT-T04

Canonical target-residual observer

Exact statement

For f∈M=η(Σ∗)f\in M=\eta(\Sigma^*), let Pf(x)={z∈M:zx=f}P_f(x)=\{z\in M:zx=f\} and df=∣{Pf(x):x∈M}∣d_f=|\{P_f(x):x\in M\}|. The minimal DFA of Kf={wR:η(w)=f}K_f=\{w^R:\eta(w)=f\} has exactly dfd_f states. If MM is L-trivial, this DFA is partially ordered, so every generated target has a representative of length at most df−1d_f-1.

StatusSelf-contained Myhill–Nerode proof; no external review
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

Membership needs an exact recognizer of one target fibre, not a faithful action of the whole opposite monoid and not equality of a full observer transformation.

Definitions

  • Pf(x)={z∈M:zx=f}P_f(x)=\{z\in M:zx=f\} is the left-context profile of xx.
  • The target-residual degree dfd_f is the number of distinct profiles.

Hypotheses and scope

  • The transition monoid is finite; the partial-order conclusion additionally assumes L-triviality.
  • Transformations act on the right, so reversed prefixes update by left multiplication.

Proof or evidence

A continuation distinguishes two reversed prefixes exactly when their induced transformations have different left-context profiles. The syntactic monoid of the target language divides the R-trivial opposite monoid. Removing self-loops from an accepting path in its minimal poDFA leaves at most d_f−1 transitions.

Canonical observer and path bound →

Verification notes

The proof was checked for targets inside and outside the generated monoid, and the d_f−1 accepted-path argument was separated from the stronger published quadratic bound for preserving a whole poDFA transformation.

Limitations

  • No polynomial upper bound on d_f in the original state degree is proved.
  • Constructing the canonical observer by enumerating M may take exponential time.

Open work

Determine whether target-residual degree is polynomially bounded in the degree of every supplied L-trivial transformation action.