Tag: automata

For a canonical positive linear recurrence numeration system with threshold-reset legality automaton and maximal boundary block

P = p₁···p_L,

we give an exact local grammar for the reset-depth sequence produced by lexicographic succession. Every positive reset depth determines its predecessor’s branch-point state and depth exactly (Theorem A); every carry-depth excursion collapses to depth 0 in at most L deterministic steps (Theorem B); and every realized excursion skeleton admits every periodic lift of its initial depth, with width increased accordingly, and with no gaps (Theorem C).

Together these give an exact decomposition of the carry-depth sequence into a finite deterministic skeleton and an unbounded periodic lift parameter. We further show that carry-depth structure depends critically on which of two natural residual-state conventions is used: the source-word residual state is exactly depth-determined,

σ(w) = q_{T(w) mod L},

while the branch-point state is maximally mixed,

R^*_t = B   for every   t ≥ 0.

We apply this grammar to state-dependent carry-cost decoders, obtaining an exact single-edge observability criterion, exact backward resolving radii throughout the deterministic predecessor chain, including its first forced depth-zero endpoint, and a sharp characterization of the multivalued obstruction that governs that endpoint’s own predecessor.

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.

Canonical positive linear recurrence sequence numeration systems admit a natural deterministic threshold-reset automaton for their legality languages. Paper IV showed that, after minimization, every presentation of a fixed system yields the automaton of the canonical reduction. The present paper studies the internal transition structure of that canonical automaton. We introduce anchored deficient-block languages and prove a Generalized Endpoint Decomposition describing every live computation from an arbitrary starting state as either a forced threshold march or an anchored first reset followed by a universal restart grammar. We then identify an exact aperiodicity criterion. If

$P = c1c2 · · · cL−1(cL − 1)$

is the primitive maximal boundary block of the canonical reduction, then the canonical threshold-
reset automaton is aperiodic if and only if $P$ is lexicographically maximal among its nontrivial cyclic rotations, equivalently, if and only if $P$ is anti-Lyndon. The forward implication follows from a total
order on live states induced by the rotations of $P ∞$, under which every digit acts monotonically. For the converse, the least rotation exceeding $P ∞$ yields an explicit word whose induced transformation has a nontrivial periodic orbit. Since the canonical automaton is minimal over its finite natural digit alphabet, this is also equivalent to star-freeness of the legality language. Exhaustive computations for all canonical reductions of order at most six with coefficients at most four agree exactly with the
theorem and recover the previously observed cycle families as concrete manifestations of the same restart structure.