FPRD LabShare an approach

← Claims

Theorem and reusable lower-bound criterion

FPRD-T79

Gradient regions lower-bound ambiguity

Exact statement

Restrict a kk-ambiguous max-plus automaton to a1∗⋯ad∗a_1^*\cdots a_d^*. On every sufficiently fine eventual product-congruence cell, its value is the maximum of at most kk affine functions of the block lengths. Therefore a cell containing mm full-dimensional regions with mm distinct affine gradients forces ambiguity degree at least mm.

StatusProved and independently audited
External reviewNo documented external or specialist review of this FPRD result is recorded.

Context

Cutting an accepting run at block boundaries turns a path problem into a finite family of sums of unary max-plus sequences. Ambiguity bounds the number of active boundary-state tuples.

Hypotheses and scope

  • The series is max-plus rational and realized by a k-ambiguous automaton.
  • The input is restricted to a fixed letter-bounded language.

Proof or evidence

Unary max-plus rational sequences are eventually affine on residue classes. After taking one common cell refinement, each active boundary-state tuple supplies one affine form and distinct tuples give distinct runs.

Letter-bounded gradient criterion →

Verification notes

Gaubert's theorem carries the universal unary normal form. Independent evidence adds 19,600 boundary factorizations and 1,950 full-rank cone/cell intersections; the five-state period-six control refutes any state-count bound on the common modulus.

Limitations

  • Bell and Bell–Semukhin study bounded-language probabilistic automata, but do not supply this max-plus gradient criterion; the comparison does not establish novelty.
  • No bound on the common eventual modulus in terms of state count is asserted.

Open work

Compare the gradient lower bound with broader tropical and bounded-language ambiguity criteria before making any novelty claim.

Notes

The unary eventual residue-affine theorem is the classical input. The automata and tropical-geometric halves are separately standard; only their coupling is a possible novelty candidate. The comparator pass is scout-grade, so no novelty claim is made.