Paper IV showed that every presentation of a canonical positive linear recurrence sequence (PLRS) numeration system determines a threshold-reset automaton, and that this automaton minimizes
to the threshold-reset automaton of the canonical reduction. Left open there was the converse recognition problem: given an arbitrary minimal deterministic automaton over an ordered digit
alphabet, with no numeration system attached to it in advance, when is it the legality automaton of some canonical PLRS, and how is the coefficient vector recovered? We answer this completely.
We give five intrinsic structural conditions on a pointed DFA — a unique absorbing rejecting sink, a cyclic threshold-reset structure with a common restart state, coincidence of the initial and
restart states, an initial-positivity condition, and closure of the threshold orbit of the restart state — and prove that a minimal DFA satisfies them if and only if it is the legality automaton of a canonical PLRS. The coefficient vector is then recovered uniquely and constructively from the transition table. We further prove, as an independent proposition, that minimality of such an
abstract cyclic threshold-reset automaton is equivalent to primitivity of its threshold-boundary word. Closely related threshold automata occur in Parry and Bertrand numeration, while classical work characterizes regularity of representation languages starting from a given numeration system.
The direction here is converse and PLRS-specific: the only input is the pointed minimal DFA, from which PLRS realizability and the unique canonical coefficient vector are decided. Sharpness
examples show that the principal structural hypotheses cannot be omitted or replaced by several natural weaker conditions.
Leave a Reply