Relative degree in a linear representation

Exact statement

Let $\Sigma=\{a,b\}$ and let $f:\Sigma^*\to\mathbb Q$ have an explicit $d$ -dimensional linear representation $f(w)=\lambda M_w\gamma$ . Its relative degree is the unique $r\in\mathbb N$ , when one exists, for which $\operatorname{supp}(f)\subseteq a^r\Sigma^*$ and $f(a^rb)\ne0$ .

StatusPrecisely stated for explicit rational linear representations

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

Context

The input model matters: the polynomial-time statement below measures arithmetic and linear-algebra operations on an explicitly supplied rational representation. Converting a rational expression to that representation is a separate cost.

Definitions

The support is $\operatorname{supp}(f)=\{w\in\Sigma^*:f(w)\ne0\}$ .
The convention here permits $r=0$ ; if $\mathbb N$ is intended to begin at one, delete that candidate without changing the argument.

Hypotheses and scope

The matrices and vectors are given explicitly over the rationals.
The alphabet is exactly $\Sigma=\{a,b\}$ , as in the posted problem.

Proof or evidence

This definition fixes the encoding and the zero-index convention used by the criterion and algorithm below.

Definitions and input model →

Verification notes

The definition was compared with Clemente's posted problem statement and Berstel--Reutenauer's standard explicit linear-representation model.

Limitations

It does not assign a relative degree when the support condition or the nonzero witness fails.
It does not include the cost of translating every possible syntax for rational series.

Open work

Ask the problem author to check that the explicit linear-representation input model matches the intended encoding.