FPRD LabShare an approach

← Claims

Definition · decision problem

FPRD-LT-D01

L-trivial transformation membership

Exact statement

Given a minimal DFA whose transition monoid M≤TQM\le T_Q is L\mathcal L-trivial and a target transformation f:Q→Qf:Q\to Q, the membership problem asks whether f∈Mf\in M.

StatusPrecisely stated; exact complexity remains open here
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

The input gives the monoid through its action on the DFA states, not by an explicit multiplication table. That representation distinction controls the available complexity bounds.

Definitions

  • M=⟨τa:a∈Σ⟩≤TQM=\langle\tau_a:a\in\Sigma\rangle\le T_Q, with transformations acting on the right.
  • MM is L\mathcal L-trivial when equality of principal left ideals Mx=MyMx=My implies x=yx=y.

Hypotheses and scope

  • The input DFA is minimal.
  • The target is supplied as an explicit total transformation of the state set.

Proof or evidence

This fixes the native compact input model used by the duality theorem, counterexample, and open complexity boundary below.

Problem statement and conventions →

Verification notes

The right-action convention, minimal-DFA promise, L-triviality promise, and explicit target representation were separated from later derived representations.

Limitations

  • No NP membership, PSPACE hardness, or completeness classification is asserted by this definition.

Open work

Determine whether positive instances always admit polynomial-length word witnesses in the supplied transformation action.