Paper deep dive
Destination-Labeled Self-Looping Systems with Dwell: Intrinsic Characterization, Realization Cost, and Recognition
Reda Belaiche
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%
Last extracted: 7/5/2026, 4:46:36 AM
Summary
The paper introduces and characterizes Destination-Labeled Self-Looping (DLSL) systems with dwell, a model for finite-state symbolic controllers where each state has a minimum residence time. The authors prove that the phase-expanded realizations of DLSL systems are exactly the class of fiber-linear graph-respecting transducers. They establish that the state cost for a deterministic realization is exactly the sum of the dwell values across all visible states. Additionally, the paper provides an O(|Q||Ω|) time complexity algorithm for the recognition and reconstruction of these systems and extends the analysis to an edge-entry variant.
Entities (5)
Relation Signals (3)
Reda Belaiche → isaffiliatedwith → University Institute of Technology of Créteil-Vitry
confidence 100% · Reda Belaiche ... Department of Computer Science, University Institute of Technology of Créteil-Vitry
DLSL system → ischaracterizedby → fiber-linear graph-respecting transducer
confidence 100% · We show that the answer is exactly the class of fiber-linear graph-respecting transducers.
phase expansion → produces → deterministic transducer
confidence 90% · The forward construction is straightforward: once the residual dwell phase is carried explicitly, one obtains a deterministic finite-state controller immediately.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study a finite-state symbolic controller for systems in which the admissible visible transitions are fixed in advance and each visible state carries a minimum dwell requirement. The resulting model, which we call a destination-labeled self-looping system with dwell (DLSL system), records the visible graph together with local decision maps; dwell memory appears only after phase expansion. The main structural issue is that, once dwell is imposed, the current visible state no longer determines whether a departure is allowed. This leads to the converse problem: which deterministic transducers arise as phase-expanded realizations of DLSL systems over a fixed visible graph? We show that the answer is exactly the class of fiber-linear graph-respecting transducers. Under natural reachability and realizable-departure assumptions, equivalent accessible realizations over the same visible graph are isomorphic; in particular, the visible transduction determines the dwell vector and the local decision maps. We also prove that any graph-preserving deterministic realization enforcing dwell values $(d_i)$ requires exactly $\sum_i d_i$ control states. Finally, we give an $O(|Q||\Omega|)$ recognition and reconstruction procedure, and extend the analysis to an edge-entry variant in which transitions may enter interior phases of successor fibers.
Tags
Links
- Source: https://arxiv.org/abs/2607.00044v1
- Canonical: https://arxiv.org/abs/2607.00044v1
Trouble viewing inline? Open PDF directly →
Full Text
62,747 characters extracted from source content.
Expand or collapse full text
[orcid=0000-0002-8741-0349] [1] , Methodology, Formal analysis, Writing - original draft, Writing - review & editing 1]organization=Department of Computer Science, University Institute of Technology of Créteil-Vitry, Paris-Est Créteil University, addressline=122 rue Paul Armangot, city=Vitry-sur-Seine, postcode=94400, country=France [1]Corresponding author Destination-Labeled Self-Looping Systems with Dwell: Intrinsic Characterization, Realization Cost, and Recognition Reda Belaiche reda.belaiche@u-pec.fr [ Abstract Many physical state-transition systems — machinery wear cycles, human activity sequences, or physiological progressions — are naturally modeled by per-state classifiers rather than by a single global sequence model. Such architectures require a control skeleton that enforces hard graph constraints and minimum residence times. We study that skeleton in the form of destination-labeled self-looping systems with dwell (DLSL systems). Once dwell is imposed, visible states no longer suffice: two histories may end in the same visible state while differing in whether departure is already enabled. The structural question is therefore intrinsic: which deterministic transducers arise from DLSL phase expansion over a fixed visible graph? We show first that the phase-expanded realizations of DLSL systems are exactly the fiber-linear graph-respecting transducers. Second, under reachability and realizable-departure hypotheses, equivalent accessible fiber-linear transducers over the same visible graph are isomorphic, so the visible transduction determines the dwell vector and local decision maps uniquely. Third, enforcing dwell values (di)(d_i) requires exactly ∑idi _id_i control states in the deterministic graph-preserving setting. Recognition and reconstruction are polynomial-time, in O(|Q||Ω|)O(|Q|| |) time. We also treat an edge-entry extension in which decisions may enter designated interior phases of successor fibers; the same path-fiber analysis yields the corresponding converse and recognition results. keywords: finite-state automata transducers characterization -time complexity algorithms [2020]68Q45 68Q70 68Q19 1 Introduction and main structural results Many physical processes — machinery wear cycles, human activity sequences, and physiological state progressions among them — evolve through a discrete set of qualitatively distinct regimes. A natural modeling choice in such settings is to assign a separate classifier to each regime, trained on data generated within that regime, rather than to train a single global model on the full sequence. This per-state classifier structure requires a control skeleton specifying which regime changes are physically admissible and how long the system must remain in a regime before a departure is credible. The DLSL model is exactly that skeleton. A global sequence model — whether based on hidden-state inference, recurrent neural networks, or semi-Markov discrimination — learns transition structure from data, either explicitly or implicitly. When the transition graph and minimum dwell constraints are physically known in advance, it is more natural to encode them as hard structural constraints rather than as regularities that the learning algorithm must rediscover. That yields a model that is easier to interpret and, in principle, more data-efficient. The present framework isolates the finite-state control structure underlying that design: hard graph constraints, minimum dwell, per-state decisions, and deterministic execution in a single symbolic object. Once minimum dwell is imposed, visible states no longer suffice to describe the controller exactly. Two histories may end in the same visible state while differing in whether departure is already enabled. The standard resolution is to refine each visible state into a short internal chain that records the remaining forced-hold depth. This yields the familiar phase-expanded realization. The forward construction is straightforward. The main question of the paper is the converse one: which deterministic transducers arise in exactly this way over a fixed visible graph? The paper is organized around three questions. The first is constructive: how does one compile a DLSL system into a deterministic transducer, and what is the exact graph-preserving state cost? Sections 3 and 4 answer this; the compilation is immediate, and the lower-bound argument shows that the cost is optimal. The second question is intrinsic: which deterministic transducers arise from this construction without phase coordinates being assumed in advance? Section 5 answers this, establishing fiber-linearity as the complete characterization and rigidity as its structural consequence. The third question is algorithmic: can fiber-linearity be tested efficiently? Section 6 answers yes, in O(|Q||Ω|)O(|Q|| |) time, and reconstructs the underlying DLSL data. Section 7.2 extends the characterization to the edge-entry variant, in which decisions may enter designated interior phases of successor fibers. The visible-state trace formulation is collected in Appendix A. 2 Symbolic model, running example, and normal form We now formalize the symbolic skeleton and fix the notation used throughout. The development is purely symbolic, but the intended motivation remains the same: each local map gig_i may be viewed as the output of a per-state classifier, while the DLSL structure supplies the hard control constraints. No statistical assumptions are needed in the formal theory. 2.1 Destination-labeled self-looping visible graphs Let S be a finite visible-state set and let E⊆S×SE S× S be a directed graph of admissible visible moves. Let Σ be a finite alphabet and let ℓ:S→Σ :S→ be a visible-state labeling. Definition 2.1 (Destination-labeled graph). A directed graph (S,E)(S,E) equipped with ℓ:S→Σ :S→ is destination-labeled if every admissible edge (i,j)∈E(i,j)∈ E carries the label ℓ(j) (j). Equivalently, if we define lab(i→j):=ℓ(j),lab(i→ j):= (j), then the label of an edge depends only on its destination. Definition 2.2 (Self-looping). A destination-labeled graph is self-looping if every visible state has a self-loop: (i,i)∈Efor all i∈S.(i,i)∈ E all i∈ S. Definition 2.3 (Label-deterministic out-neighborhood). A destination-labeled graph is label-deterministic if for every visible state i and every label a∈Σa∈ , |j∈Out(i):ℓ(j)=a|≤1. |\j (i): (j)=a\ |≤ 1. Under label-determinism, a visible successor is uniquely identified by its destination label. We therefore define Σi:=ℓ(j):j∈Out(i), _i:=\ (j):j (i)\, together with the induced partial transition map δ(i,a)=j,if j∈Out(i) and ℓ(j)=a,undefined,otherwise.δ(i,a)= casesj,&if j (i) and (j)=a,\\ undefined,&otherwise. cases 2.2 Running example: activity recognition with minimum dwell We use a small running example throughout to keep the notation concrete. Let S=rest,walk,run.S=\rest,walk,run\. The visible graph allows rest→rest,rest→walk,walk→rest,walk→walk, , , , , walk→run,run→walk,run→run, , , , and forbids direct rest→runrest and run→restrun transitions. The dwell values are drest=3,dwalk=2,drun=2.d_rest=3, d_walk=2, d_run=2. One may view the visible states as symbolic activity regimes and the local maps gig_i as regime-dependent decision rules. This interpretation motivates the model; no statistical assumptions enter the formal development. The example is deliberately small. Its phase-expanded realization has 3+2+2=73+2+2=7 control states, so it is convenient for illustrating the constructions and converse results below. It is useful to distinguish the visible DLSL skeleton from its exact deterministic realization. The former has one visible state per label and records only the destination-labeled transition structure; the latter refines each visible state into a phase chain in order to make dwell memory explicit. restwalkrunrestwalkrunwalkrestrunwalk Figure 1: Implicit-dwell DLSL skeleton for the running example. There is one visible state per label, and every transition entering a state carries that state’s label. Minimum dwell is part of the symbolic semantics, not of the visible graph itself. Figure 1 shows the visible DLSL skeleton of the running example, before any phase expansion is introduced. There is exactly one visible state for each label, and the labeling is destination-based: every transition entering rest, walk, or run carries the corresponding destination label. The minimum dwell values drest=3d_rest=3, dwalk=2d_walk=2, and drun=2d_run=2 are not encoded by extra visible states in this figure. Instead, they are enforced by the operational semantics through the residual dwell phase. This distinction is important. The visible DLSL skeleton records the admissible labeled moves between regimes, while the phase-expanded realization introduced later makes the dwell memory explicit in the control state. In particular, when some di>1d_i>1, the one-state-per-label skeleton is not by itself an exact deterministic realization of the dwell-constrained behavior. 2.3 Symbolic DLSL systems with dwell Fix a finite symbolic input alphabet Ω , an initial visible state s0∈Ss_0∈ S, and a dwell map d:S→ℕ≥1,i↦di.d:S _≥ 1, i d_i. For each visible state i, let gi:Ω→Σig_i: → _i be a local symbolic decision map. Definition 2.4 (Symbolic DLSL system with dwell). A symbolic destination-labeled self-looping system with dwell consists of the data =(S,E,ℓ,s0,d,(gi)i∈S)A=(S,E, ,s_0,d,(g_i)_i∈ S) such that (S,E,ℓ)(S,E, ) is destination-labeled, self-looping, and label-deterministic. Its operational state is a pair (i,r)(i,r), where i∈Si∈ S is the visible state and r∈0,1,…,di−1r∈\0,1,…,d_i-1\ is the residual dwell phase. The operational update on input u∈Ωu∈ is (i,r)→(i,r−1),r>0,(δ(i,gi(u)),dδ(i,gi(u))−1),r=0.(i,r) u cases(i,r-1),&r>0,\\ (δ(i,g_i(u)),\,d_δ(i,g_i(u))-1),&r=0. cases (2.1) Thus, while r>0r>0, the machine is forced to remain in the current visible state. Once r=0r=0, it may apply the local decision map and move to the unique visible successor identified by the predicted destination label. In the running example, the operational state (walk,1)(walk,1) means: the current visible regime is walkwalk, and one forced-hold step remains before any proposal to leave walkwalk can be acted upon. By contrast, (walk,0)(walk,0) means that the next input may either keep the machine in walkwalk or send it to restrest or runrun, provided the corresponding destination label is proposed by gwalkg_walk. For an input word w=u1⋯un∈Ω∗w=u_1·s u_n∈ ^*, let (y0,r0)=(s0,ds0−1)(y_0,r_0)=(s_0,d_s_0-1) and define recursively (yt,rt)=δop((yt−1,rt−1),ut),t=1,…,n.(y_t,r_t)= _op((y_t-1,r_t-1),u_t), t=1,…,n. We write tr(w):=y0y1⋯yn∈Sn+1tr_A(w):=y_0y_1·s y_n∈ S^n+1 for the visible-state trace and Out(w):=y1⋯yn∈SnOut_A(w):=y_1·s y_n∈ S^n for the post-initial output word. Definition 2.5 (Standing assumptions). The symbolic DLSL system is: 1. destination-complete if, for every visible state i and every label a∈Σia∈ _i, there exists an input symbol u∈Ωu∈ such that gi(u)=ag_i(u)=a; 2. reachable if every visible state under discussion is reachable from s0s_0 by some input word. Destination-completeness is only needed when we want exact visible-trace realizability statements and lower bounds. It is not needed for the basic compilation into a deterministic transducer. Because the visible graph is self-looping and destination-labeled, every visible state automatically has its own label available as a hold action. Concretely, if (i,i)∈E(i,i)∈ E, then the self-loop into i carries label ℓ(i) (i), so ℓ(i)∈Σi (i)∈ _i. We use this simple observation only implicitly later, when a decision phase needs to realize a visible self-loop without augmenting the visible graph. 3 Realization preliminaries 3.1 Phase expansion into a deterministic transducer The forward realization is standard: once the residual dwell phase is carried explicitly, one obtains a deterministic finite-state controller immediately. We record it only to fix notation and to make the state count explicit before turning to lower bounds and intrinsic characterization. Proposition 3.1 (Phase expansion into a deterministic finite-state transducer). For every symbolic DLSL system with dwell, there exists a deterministic Mealy transducer T=(Q,q0,Ω,S,Δ,ω)T_A=(Q,q_0, ,S, ,ω) such that for every input word w∈Ω∗w∈ ^*, ω∗(q0,w)=Out(w).ω^*(q_0,w)=Out_A(w). Moreover, one may choose Q=(i,r):i∈S, 0≤r≤di−1,q0=(s0,ds0−1),Q=\(i,r):i∈ S,\ 0≤ r≤ d_i-1\, q_0=(s_0,d_s_0-1), so that |Q|=∑i∈Sdi.|Q|= _i∈ Sd_i. Proof. The construction is the phase expansion itself. Let Q=(i,r):i∈S, 0≤r≤di−1,q0=(s0,ds0−1),Q=\(i,r):i∈ S,\ 0≤ r≤ d_i-1\, q_0=(s_0,d_s_0-1), and define Δ((i,r),u)=(i,r−1),r>0,(δ(i,gi(u)),dδ(i,gi(u))−1),r=0, ((i,r),u)= cases(i,r-1),&r>0,\\ (δ(i,g_i(u)),\,d_δ(i,g_i(u))-1),&r=0, cases together with ω((i,r),u)=i,r>0,δ(i,gi(u)),r=0.ω((i,r),u)= casesi,&r>0,\\ δ(i,g_i(u)),&r=0. cases These formulas are exactly the operational semantics (2.1), with the next visible state emitted after each input symbol. Hence, by a direct induction on the input length, the transducer state after any prefix coincides with the operational state of the symbolic system, and the emitted word is precisely Out(w)Out_A(w). The determinism of the transducer follows from the fact that each gig_i is a function and label-determinism makes δ(i,gi(u))δ(i,g_i(u)) unique. Finally, |Q|=∑i∈Sdi|Q|= _i∈ Sd_i by construction. ∎ restrestrestwalkwalkrunrun2101010restrestwalkrunrestwalkrunwalkrestrunwalk Figure 2: A destination-labeled realization of the running example with visible dwell phases. Each fiber is associated with one visible label: every transition entering a rest-state is labeled rest, every transition entering a walk-state is labeled walk, and every transition entering a run-state is labeled run. The phase-0 states are the decision states; the higher-phase states are forced-hold states. This is the reset-to-top canonical form; the edge-entry variant, in which decisions may enter a designated interior state of the successor fiber rather than its top state, is described in Section 7.2 and illustrated in Figure 5. In Figure 2, the destination-labeled structure and the dwell refinement are visible at the same time. The automaton is organized into three fibers, corresponding to rest, walk, and run. Within each fiber, all transitions are labeled by the fiber label, so the visible symbol is determined by the destination side of the move. The phase index records the remaining forced-hold depth before a non-self departure becomes possible. For example, after entering the walk fiber, the controller first visits phase 11, and one further occurrence of walk is required before it reaches the decision state at phase 0. Only there can it either remain in walk or move to another fiber. This is the shape that will later be characterized intrinsically: path-like fibers with one decision state and destination-labeled transitions between fibers. The phase-expanded picture in Figure 2 is enough for the rest of the main line of the paper. A complementary behavioral description in terms of visible-state traces and run-length constraints is still useful, but it is secondary to the structural classification and is therefore deferred to Appendix A. 4 Exact graph-preserving state cost The phase-expanded realization uses extra control states to store the residual dwell phase. The next question is whether this is merely a convenient construction or the exact graph-preserving state cost of dwell. 4.1 Graph-respecting transducers Definition 4.1 (Graph-respecting labeled transducer). A graph-respecting labeled transducer for the visible graph (S,E)(S,E) is a deterministic transducer T=(Q,q0,Ω,S,Δ,λ),T=(Q,q_0, ,S, ,λ), where λ:Q→Sλ:Q→ S is a surjective visible-state labeling such that for every control state q∈Qq∈ Q and every input symbol u∈Ωu∈ , λ(Δ(q,u))∈Out(λ(q)).λ( (q,u)) (λ(q)). Its emitted symbol after reading one input is the visible label of the successor control state. We say that T is equivalent to A if for every input word w, the emitted output word of T equals Out(w)Out_A(w). 4.2 Why the visible graph alone is insufficient Proposition 4.2 (Visible states alone do not suffice in the presence of nontrivial dwell). Assume there exists a reachable visible state i∈Si∈ S such that di>1andOut(i)∖i≠∅.d_i>1 (i) \i\≠ . Assume further that at least one non-self destination from i is realizable, namely that there exist j∈Out(i)∖ij (i) \i\ and b∈Ωb∈ such that gi(b)=ℓ(j).g_i(b)= (j). Then there is no deterministic graph-respecting labeled transducer equivalent to A whose control-state set is exactly S and whose visible-state labeling is the identity. Proof. The idea is to compare two histories that end at the same visible state i but leave different amounts of dwell budget. Because i is reachable, there exists an input word α that brings the symbolic DLSL system to visible state i. By extending α, we may assume that the operational state after reading α is (i,di−1)(i,d_i-1), namely the state immediately after entry into i. Fix an arbitrary input symbol c∈Ωc∈ . Consider the two words w=αcdi−1,w′=αcdi−2.w=α c^d_i-1, w =α c^d_i-2. After reading w, the operational state is (i,0)(i,0): the machine is still visibly in i, but it is now allowed to leave. After reading w′w , the operational state is (i,1)(i,1): the machine is still visibly in i, but one forced-hold step remains. Now feed the same additional symbol b. By assumption, when the machine is in visible state i and residual phase 0, the symbol b triggers a move to j≠ij≠ i. Hence the visible output on the continuation b after history w begins with j. By contrast, after history w′w , the machine is still under forced hold. Here one uses (2.1) explicitly: for every input symbol u, if the residual phase is positive then the next operational state remains in the same visible state, namely (i,r)→(i,r−1)(i,r) u(i,r-1). Therefore the same continuation b keeps the visible state at i; the visible output begins with i. The two continuations thus produce different future visible outputs. Suppose now that an equivalent graph-respecting transducer existed with control-state set exactly S and visible-state labeling equal to the identity. After histories w and w′w , that transducer would be in the same control state i. By determinism, feeding the same next symbol b would then produce the same successor visible state after both histories, contradicting the previous paragraph. Thus no such transducer exists. ∎ In the running example, the same phenomenon appears inside the visible state walkwalk: two histories may both end in walkwalk, yet only the one that has already discharged its dwell budget can respond immediately to a proposal for runrun. That distinction is invisible on the visible graph alone. 4.3 A lower bound above each visible state Theorem 4.3 (Lower bound on required augmentation). Assume the symbolic DLSL system is destination-complete. Let T=(Q,q0,Ω,S,Δ,λ)T=(Q,q_0, ,S, ,λ) be any deterministic graph-respecting labeled transducer equivalent to A. Fix a reachable visible state i∈Si∈ S such that Out(i)∖i≠∅Out(i) \i\≠ and at least one non-self departure from i is realizable. Then |λ−1(i)|≥di.|λ^-1(i)|≥ d_i. Consequently, if every visible state is reachable and admits a realizable non-self departure, then |Q|≥∑i∈Sdi.|Q|≥ _i∈ Sd_i. Proof. This is the same separation idea, now used to distinguish all residual phases above a fixed visible state. Write m=dim=d_i. We show that the m residual phases above visible state i are pairwise distinguishable by future continuations. Let 0≤r<r′≤m−10≤ r<r ≤ m-1. Choose a non-self realizable departure symbol b∈Ωb∈ and destination j∈Out(i)∖ij (i) \i\ such that gi(b)=ℓ(j).g_i(b)= (j). Fix an arbitrary symbol c∈Ωc∈ , and consider the continuation x=crb.x=c^rb. Start from the operational state (i,r)(i,r). The prefix crc^r consumes exactly the remaining forced-hold budget and brings the machine to phase 0. The final symbol b is therefore read at decision phase, so the machine departs from i to j. Thus the output on continuation x begins with a block of i’s of length exactly r, followed by j. Now start instead from operational state (i,r′)(i,r ). After the same prefix crc^r, the residual phase is still r′−r>0r -r>0, so the final symbol b is read under forced hold. Hence the machine remains in visible state i throughout the whole continuation x. In particular, the resulting output word differs from the previous one. Therefore the future behaviors obtained from residual phases r and r′r are different. Any equivalent deterministic transducer must realize these distinguishable behaviors by distinct reachable control states. Since all these behaviors project to the same visible state i, the fiber λ−1(i)λ^-1(i) must contain at least m=dim=d_i distinct control states. If the assumption holds for every visible state, the fibers λ−1(i)λ^-1(i) are disjoint and summing the per-fiber lower bounds yields |Q|=∑i∈S|λ−1(i)|≥∑i∈Sdi.|Q|= _i∈ S|λ^-1(i)|≥ _i∈ Sd_i. ∎ Corollary 4.4 (Tightness of the phase expansion). Under the hypotheses of Theorem 4.3, the phase-expanded realization of Proposition 3.1 is optimal among deterministic graph-respecting labeled transducers equivalent to A. In particular, min|Q|=∑i∈Sdi. |Q|= _i∈ Sd_i. Proof. Proposition 3.1 constructs an equivalent graph-respecting deterministic realization with exactly ∑idi _id_i control states, while Theorem 4.3 shows that no equivalent graph-respecting deterministic realization can use fewer. The bounds match. ∎ So the dwell budget above each visible state has an exact deterministic state cost. The phase-expanded realization is not just sufficient; in the graph-preserving setting it is also minimal. 5 Intrinsic characterization: path fibers, chain monoids, and converse representation We now identify the class of deterministic transducers that arise from phase expansion, without assuming phase coordinates in advance. The strategy is to define an intrinsic structural property — fiber-linearity — purely in terms of the hold behavior inside each visible-state fiber and the reset behavior of decisions. We then show that this property characterizes exactly the compiled DLSL realizations and that it yields a unique canonical representative. 5.1 Fiber-linear transducers Recall that a graph-respecting labeled transducer is a deterministic transducer T=(Q,q0,Ω,S,Δ,λ),T=(Q,q_0, ,S, ,λ), where λ:Q→Sλ:Q→ S is a surjective visible-state labeling such that λ(Δ(q,u))∈Out(λ(q))for all q∈Q,u∈Ω.λ( (q,u)) (λ(q)) all q∈ Q,\ u∈ . Definition 5.1 (Forced-hold state). Let T=(Q,q0,Ω,S,Δ,λ)T=(Q,q_0, ,S, ,λ) be a graph-respecting transducer. A control state q∈Qq∈ Q is a forced-hold state if there exists a control state q′∈Qq ∈ Q such that λ(q′)=λ(q)andΔ(q,u)=q′for every u∈Ω.λ(q )=λ(q) (q,u)=q every u∈ . In that case, q′q is uniquely determined by determinism, and we denote it by hsucc(q).hsucc(q). A control state that is not forced-hold is called a decision state. Definition 5.2 (Fiber hold graph). For a visible state i∈Si∈ S, let Fib(i):=λ−1(i).Fib(i):=λ^-1(i). The fiber hold graph HiH_i is the directed graph with vertex set Fib(i)Fib(i) and an edge q⟶hsucc(q)q (q) for every forced-hold state q∈Fib(i)q (i). Definition 5.3 (Fiber-linear graph-respecting transducer). A graph-respecting transducer T=(Q,q0,Ω,S,Δ,λ)T=(Q,q_0, ,S, ,λ) is fiber-linear if, for every visible state i∈Si∈ S, the following hold: 1. Path condition inside the fiber: the fiber hold graph HiH_i is a directed simple path on the whole fiber Fib(i)Fib(i), ending at a unique terminal vertex pip_i. Equivalently, pip_i is the unique decision state in Fib(i)Fib(i), every other state in Fib(i)Fib(i) is forced-hold, and repeated application of hsucchsucc walks through the fiber in a single linear chain until pip_i is reached. 2. Reset-on-decision: let tit_i denote the unique initial vertex of the path HiH_i (so ti=pit_i=p_i when |Fib(i)|=1|Fib(i)|=1). Then for every input symbol u∈Ωu∈ , if λ(Δ(pi,u))=j,λ( (p_i,u))=j, we have Δ(pi,u)=tj. (p_i,u)=t_j. The point of Definition 5.3 is that it is intrinsic. It refers only to input-independent hold behavior inside visible-state fibers and to where decisions reset. No phase indexing is assumed at the outset. Figure 3 makes the geometry explicit. The positive panel shows the unique pattern allowed inside each visible-state fiber: a linear hold chain culminating in one decision state, with every inter-fiber decision entering the designated entry state of the successor fiber. The two obstruction panels anticipate Corollary 5.7: any internal cycle or any decision entering an interior state of a successor fiber immediately falls outside the DLSL class. (a) Fiber-linear fiber structuretit_i⋅·pip_iholdholdFib(i)Fib(i)tjt_j⋅·pjp_jholdholdFib(j)Fib(j)decision on uueach fiber is a single hold path, and each decision from pip_i resets to the entry state tjt_j(b) Forbidden: cycle inside a fiberq0q_0q1q_1holdholdnot a simple path(c) Forbidden: nonentry targettjt_jeepjp_jpip_iuudecision enters an interior state of Fib(j)Fib(j)instead of the designated entry state Figure 3: Fiber-linear structure and minimal obstructions. Panel (a) shows the geometric content of Definition 5.3: each visible-state fiber is a single directed hold path ending at one decision state, and every decision transition resets to the entry state of the successor fiber. Panels (b) and (c) show two immediate obstructions used later in Corollary 5.7. The same class can also be described in standard algebraic language. Each fiber carries a single unary “countdown” transformation whose powers form a finite chain monoid; the reset condition says that cross-fiber actions factor through the unique active state at the bottom of that chain. Proposition 5.4 (Transformation-monoid characterization). Let T=(Q,q0,Ω,S,Δ,λ)T=(Q,q_0, ,S, ,λ) be a graph-respecting transducer. Then the following are equivalent. 1. T is fiber-linear. 2. For every visible state i∈Si∈ S, there exist states ti,pi∈Fib(i)t_i,p_i (i) and a transformation hi:Fib(i)→Fib(i)h_i:Fib(i) (i) such that: (a) the transformation monoid ⟨hi⟩ h_i has size |Fib(i)||Fib(i)|, is generated by the single map hih_i, and is a finite chain monoid in the sense that its unique nonidentity idempotent is the constant map onto pip_i; (b) for every q∈Fib(i)∖piq (i) \p_i\ and every input symbol u∈Ωu∈ , one has Δ(q,u)=hi(q); (q,u)=h_i(q); in particular, every nonterminal fiber state is input-independent; (c) if λ(Δ(pi,u))=jλ( (p_i,u))=j, then Δ(pi,u)=tj. (p_i,u)=t_j. In particular, fiber-linear transducers are exactly the graph-respecting deterministic transducers whose per-fiber dynamics are governed by monogenic aperiodic chain monoids and whose cross-fiber actions factor through the unique active state of each fiber. Proof. Assume first that T is fiber-linear. For a fiber Fib(i)Fib(i), let pip_i be the terminal vertex of the hold path and tit_i its initial vertex. Define hi(q):=hsucc(q),q≠pi,pi,q=pi.h_i(q):= caseshsucc(q),&q≠ p_i,\\ p_i,&q=p_i. cases Because the fiber hold graph is a directed simple path on all vertices of Fib(i)Fib(i), repeated application of hih_i moves every state one step closer to pip_i, and the powers id,hi,hi2,…,hi|Fib(i)|−1id,h_i,h_i^2,…,h_i^|Fib(i)|-1 are pairwise distinct. The last power is the constant map onto pip_i, and it is the unique nonidentity idempotent. Clause (b) is just the definition of forced-hold, and clause (c) is the reset-on-decision property. Conversely, assume the transformation-monoid formulation. Since ⟨hi⟩ h_i is a finite chain monoid of size |Fib(i)||Fib(i)|, the orbit of every state under hih_i is linearly ordered and terminates at the unique image point pip_i of the nonidentity idempotent. Because the monoid has exactly |Fib(i)||Fib(i)| elements, there is exactly one state at each distance from pip_i, so the directed graph formed by the edges q→hi(q)q→ h_i(q) for q≠piq≠ p_i is a simple path on the whole fiber, with initial vertex tit_i and terminal vertex pip_i. Clause (b) then says that every nonterminal fiber state is forced-hold, and clause (c) is precisely reset-on-decision. Hence T is fiber-linear. ∎ Position inside classical deterministic transducers. Every compiled DLSL realization is a sequential transducer, hence belongs to the classical subsequential world. The inclusion is strict: an accessible deterministic graph-respecting sequential transducer may fail to be fiber-linear simply because one visible-state fiber contains a cycle instead of a single hold path, or because a decision transition enters a nonentry state of a successor fiber. Theorem 5.5 (Compiled realizations are fiber-linear). Let A be a symbolic DLSL system with dwell, and let T_A be the deterministic realization constructed in Proposition 3.1. Then T_A is fiber-linear. Proof. The phase-expanded realization has control states Q=(i,r):i∈S, 0≤r≤di−1,Q=\(i,r):i∈ S,\ 0≤ r≤ d_i-1\, with visible-state labeling λ(i,r)=iλ(i,r)=i. Fix a visible state i. For every state (i,r)(i,r) with r>0r>0, the operational update is Δ((i,r),u)=(i,r−1)for all u∈Ω, ((i,r),u)=(i,r-1) all u∈ , so (i,r)(i,r) is forced-hold and hsucc((i,r))=(i,r−1).hsucc((i,r))=(i,r-1). The unique state in the fiber Fib(i)Fib(i) that is not forced-hold is (i,0)(i,0), since from that state the successor depends on the input through gig_i. Therefore the fiber hold graph is exactly the directed path (i,di−1)→(i,di−2)→⋯→(i,1)→(i,0).(i,d_i-1)→(i,d_i-2)→·s→(i,1)→(i,0). Thus the path condition holds, with terminal vertex pi=(i,0)p_i=(i,0) and initial vertex ti=(i,di−1)t_i=(i,d_i-1). Now consider an input symbol u∈Ωu∈ read at the decision state (i,0)(i,0). By the operational semantics, Δ((i,0),u)=(j,dj−1),j=δ(i,gi(u)). ((i,0),u)= (j,d_j-1 ), j=δ(i,g_i(u)). But (j,dj−1)=tj(j,d_j-1)=t_j, the initial vertex of the path in the fiber over j. Hence the reset-on-decision condition also holds. Therefore T_A is fiber-linear. ∎ Theorem 5.5 shows that every compiled DLSL realization is fiber-linear. The next theorem establishes the converse: fiber-linearity is not merely a property of compiled realizations but characterizes them exactly. Theorem 5.6 (Intrinsic converse representation). Let T=(Q,q0,Ω,S,Δ,λ)T=(Q,q_0, ,S, ,λ) be a fiber-linear graph-respecting transducer. Then there exists an injectively labeled symbolic DLSL system with dwell T=(S,E,ℓ,s0,d,(gi)i∈S)A_T=(S,E, ,s_0,d,(g_i)_i∈ S) such that the phase-expanded realization of TA_T is isomorphic to T. Moreover, TA_T is unique up to injective relabeling of the visible states. Proof. For each visible state i, let pip_i be the unique terminal vertex of the path HiH_i, and let tit_i be the unique initial vertex of that path. Define di:=|Fib(i)|.d_i:=|Fib(i)|. Because HiH_i is a directed simple path on Fib(i)Fib(i), each state q∈Fib(i)q (i) has a unique distance to the terminal vertex pip_i. Write this distance as Phasei(q)∈0,1,…,di−1,Phase_i(q)∈\0,1,…,d_i-1\, so that Phasei(pi)=0,Phasei(ti)=di−1.Phase_i(p_i)=0, _i(t_i)=d_i-1. We now reconstruct a symbolic DLSL system. Let the visible alphabet be the visible-state set itself: Σ:=S,ℓ(i):=i. :=S, (i):=i. This labeling is injective. Define the visible edge set by E:=(i,j):∃u∈Ω such that λ(Δ(pi,u))=j∪(i,i):i∈S.E:=\(i,j):∃ u∈ such that λ( (p_i,u))=j\\;∪\;\(i,i):i∈ S\. The added self-loops make the visible graph self-looping. Because the labeling is injective, the graph is automatically destination-labeled and label-deterministic. For each visible state i, define gi(u):=λ(Δ(pi,u)).g_i(u):=λ( (p_i,u)). Since λ(Δ(pi,u))∈Out(i)λ( (p_i,u)) (i), we indeed have gi(u)∈Σig_i(u)∈ _i. Consider now the phase-expanded realization of this symbolic DLSL system. Its control states are pairs (i,r),0≤r≤di−1.(i,r), 0≤ r≤ d_i-1. Define Φ:Q→(i,r):i∈S, 0≤r≤di−1 :Q→\(i,r):i∈ S,\ 0≤ r≤ d_i-1\ by Φ(q):=(λ(q),Phaseλ(q)(q)). (q):= (λ(q),Phase_λ(q)(q) ). Because each fiber hold graph is a path, every fiber contains exactly one state at each phase depth r, so Φ is bijective. We show that Φ is a transducer isomorphism. First, suppose q∈Fib(i)q (i) is forced-hold. Then hsucc(q)hsucc(q) is the next state on the path toward pip_i, hence Phasei(hsucc(q))=Phasei(q)−1.Phase_i(hsucc(q))=Phase_i(q)-1. Since q is forced-hold, Δ(q,u)=hsucc(q) (q,u)=hsucc(q) for every u∈Ωu∈ . Therefore Φ(Δ(q,u))=(i,Phasei(q)−1), ( (q,u))= (i,Phase_i(q)-1 ), which is exactly the phase-expanded transition from (i,Phasei(q))(i,Phase_i(q)) when the phase is positive. Second, suppose q=piq=p_i is the decision state in fiber i. By fiber-linearity, for every u∈Ωu∈ , if λ(Δ(pi,u))=j,λ( (p_i,u))=j, then Δ(pi,u)=tj. (p_i,u)=t_j. Hence Φ(Δ(pi,u))=(j,Phasej(tj))=(j,dj−1), ( (p_i,u))= (j,Phase_j(t_j) )=(j,d_j-1), which is exactly the phase-expanded reset transition from decision phase 0 in the symbolic DLSL system defined above. Thus Φ intertwines the transitions of T and of the phase-expanded realization of TA_T, and it preserves visible labels by construction. Therefore the two transducers are isomorphic. Finally, the reconstruction depends only on the visible graph, the fiber lengths, and the injective naming of visible labels. Replacing ℓ(i)=i (i)=i by any other injective relabeling yields an isomorphic symbolic DLSL system. This is the claimed uniqueness up to injective relabeling. ∎ Figure 4 summarizes the logic of the converse theorem. Fiber inspection extracts the visible graph, the dwell vector, and the local decision maps; those data in turn determine a unique phase-expanded realization. This reconstruction viewpoint is what later supports both the obstruction test and the canonicality result. TTfiber-linear transducerreconstructed data(S,E,s0,d,(gi)i∈S) (S,E,s_0,d,(g_i)_i∈ S )C(T)C(T)canonical phase-expanded realizationreconstructphase expansionT′T fiber-linear transducerreconstructed data(S,E,s0,d′,(gi′)i∈S) (S,E,s_0,d ,(g _i)_i∈ S )C(T′)C(T )reconstructphase expansionsame visibletransductionsame canonicalrepresentative Figure 4: Reconstruction and canonical representative. A fiber-linear transducer determines its dwell vector and local decision maps by fiber inspection, and these data determine a unique phase-expanded realization. This is the mechanism behind Theorem 5.6, Theorem 5.8, and Corollary 5.9. Corollary 5.7 (Simple obstructions to DLSL representability). Let T=(Q,q0,Ω,S,Δ,λ)T=(Q,q_0, ,S, ,λ) be a deterministic graph-respecting transducer. If, for some visible state i∈Si∈ S, the fiber Fib(i)Fib(i) fails to form a single directed hold path with a unique decision state, or if some decision transition enters a noninitial state of a successor fiber, then T is not isomorphic to the phase-expanded realization of any injectively labeled symbolic DLSL system with dwell. Proof. Any such transducer is not fiber-linear. The claim is therefore immediate from Theorem 5.6. ∎ Theorem 5.8 (Behavioral rigidity and canonicality). Let T=(Q,q0,Ω,S,Δ,λ)andT′=(Q′,q0′,Ω,S,Δ′,λ′)T=(Q,q_0, ,S, ,λ) T =(Q ,q _0, ,S, ,λ ) be accessible fiber-linear graph-respecting transducers over the same visible graph (S,E)(S,E) and with the same initial visible state. Assume that every visible state is reachable and admits a realizable non-self departure in both transducers. If T and T′T induce the same visible-state transduction OutT(w)=OutT′(w)for all w∈Ω∗,Out_T(w)=Out_T (w) all w∈ ^*, then T and T′T are isomorphic. Proof. By Theorem 5.6, both transducers reconstruct to symbolic DLSL systems =(S,E,s0,d,(gi)i∈S)and′=(S,E,s0,d′,(gi′)i∈S),A=(S,E,s_0,d,(g_i)_i∈ S) =(S,E,s_0,d ,(g _i)_i∈ S), where we suppress the injective labeling because only the visible-state behavior matters here. The behavioral argument below is carried out on the reconstructed DLSL systems A and ′A , not directly on T and T′T . This is valid because Theorem 5.6 gives an isomorphism between each fiber-linear transducer and the phase-expanded realization of its reconstructed data; hence visible transduction equality for T and T′T implies visible transduction equality for A and ′A . Fix a visible state i∈Si∈ S. Since i is reachable, choose a word xix_i whose visible-state run enters i at its last step; if i=s0i=s_0, take xi=εx_i= . In a phase-expanded DLSL realization, reading xix_i places the machine at the top state of the fiber over i. Because i admits a realizable non-self departure, the set Di:=m≥1:∃y∈Ωm such that the visible run after xiy leaves i at its last stepD_i:=\m≥ 1:∃ y∈ ^m such that the visible run after x_iy leaves i at its last step\ is nonempty. Its minimum is exactly did_i: departure is impossible during the first di−1d_i-1 symbols after entry into i, while some departure is realizable on the did_i-th symbol. The same reasoning applied to T′T yields minDi=di′ D_i=d _i. Since T and T′T have the same visible transduction, the sets DiD_i coincide, and therefore di=di′for all i∈S.d_i=d _i all i∈ S. Now fix u∈Ωu∈ . Because the first di−1d_i-1 steps after entering i are forced holds, the visible successor chosen on the did_i-th step depends only on u. More precisely, for any word z∈Ωdi−1z∈ ^d_i-1, the visible state reached after reading xizux_izu is δ(i,gi(u))δ(i,g_i(u)) in T and δ(i,gi′(u))δ(i,g _i(u)) in T′T . Equality of the visible transductions implies δ(i,gi(u))=δ(i,gi′(u)).δ(i,g_i(u))=δ(i,g _i(u)). Since the visible graph is fixed, the destination visible state uniquely determines the local choice. Hence gi(u)=gi′(u)g_i(u)=g _i(u) for every u∈Ωu∈ , and therefore gi=gi′for all i∈S.g_i=g _i all i∈ S. Thus the reconstructed DLSL data coincide. Their phase-expanded realizations are therefore identical up to the canonical phase-state renaming, which yields an isomorphism between T and T′T . ∎ Corollary 5.9 (Canonical representative and equivalence test). Every accessible fiber-linear graph-respecting transducer has a unique canonical representative, namely the phase-expanded realization of its reconstructed DLSL data. In particular, equivalence of two accessible fiber-linear transducers over the same visible graph is decidable in polynomial time by reconstruction and comparison of the canonical data. Proof. The canonical representative is provided by Theorem 5.6. Uniqueness follows from Theorem 5.8, and polynomial-time reconstruction from Theorem 6.1.∎ Remark 5.10. Concretely, two fiber-linear transducers realizing the same visible-state transduction can be tested for equivalence by reconstructing their dwell vectors (di)i∈S(d_i)_i∈ S and local maps (gi)i∈S(g_i)_i∈ S using the algorithm of Theorem 6.1, and comparing the resulting DLSL data directly. No state-space exploration, product construction, or language-equivalence test is needed. In particular, the canonical representative is computed in O(|Q||Ω|)O(|Q|| |) time. 6 Recognition and reconstruction The converse characterization is constructive. It turns DLSL representability into a directly testable property of a deterministic transducer description, and the defining fiber structure can be checked algorithmically. Theorem 6.1 (Polynomial-time recognition and reconstruction). There is an algorithm that, given a deterministic graph-respecting transducer T=(Q,q0,Ω,S,Δ,λ),T=(Q,q_0, ,S, ,λ), decides in time O(|Q||Ω|)O(|Q|| |) whether T is fiber-linear. When the answer is yes, the algorithm reconstructs the unique underlying symbolic DLSL system of Theorem 5.6, up to injective relabeling of the visible states. Proof. The test is straightforward: identify forced-hold states, inspect each fiber, and then check whether decisions reset to the top of successor fibers. For each control state q∈Qq∈ Q, inspect the set of successors Δ(q,u):u∈Ω.\ (q,u):u∈ \. If all these successors coincide with a state q′q satisfying λ(q′)=λ(q),λ(q )=λ(q), then mark q as forced-hold and set hsucc(q)=q′hsucc(q)=q ; otherwise mark q as a decision state. This takes O(|Q||Ω|)O(|Q|| |) time. Now fix a visible state i∈Si∈ S. Build the fiber hold graph HiH_i on Fib(i)=λ−1(i)Fib(i)=λ^-1(i), with edges q→hsucc(q)q (q) for forced-hold states q∈Fib(i)q (i). We claim that T is fiber-linear if and only if, for every i, the following conditions hold: 1. HiH_i is a directed simple path on all vertices of Fib(i)Fib(i); 2. the unique terminal vertex of HiH_i is the unique decision state pip_i in Fib(i)Fib(i); 3. if tit_i denotes the unique initial vertex of HiH_i, then for every u∈Ωu∈ , Δ(pi,u)=tjwheneverλ(Δ(pi,u))=j. (p_i,u)=t_j λ( (p_i,u))=j. These are exactly the two clauses of Definition 5.3, rewritten in graph-theoretic language. Each of the three checks above can be carried out in time linear in the size of the fiber plus |Ω|| |. For the path condition, one does not merely test connectivity and acyclicity. One checks directly that, within each fiber HiH_i, every forced-hold vertex except one has indegree 11 and outdegree 11, the unique initial vertex has indegree 0, the terminal vertex pip_i has outdegree 0, and all vertices belong to the same weakly connected component. These conditions are exactly the directed simple-path conditions for the hold graph on the fiber. Summing over all fibers yields total time O(|Q|+|Q||Ω|)=O(|Q||Ω|).O(|Q|+|Q|| |)=O(|Q|| |). If every fiber passes, then the path order in each fiber is uniquely determined. The length of the fiber becomes the dwell value did_i, the terminal state becomes the decision state pip_i, the initial state becomes the top state tit_i, and the reconstructed local maps are gi(u):=λ(Δ(pi,u)).g_i(u):=λ( (p_i,u)). This is exactly the reconstruction used in Theorem 5.6. Hence the underlying symbolic DLSL system is recovered, uniquely up to injective relabeling. ∎ 7 Extensions beyond the canonical normal form The core converse theorem uses injective visible labels and exact reset-to-top because that is the cleanest canonical normal form. Neither restriction is conceptually fundamental. 7.1 Injective labels as a presentation choice The intrinsic reconstruction theorem is really about visible states, fibers, and entry structure. Injective visible labels are used only to choose canonical names for the reconstructed visible states. Concretely, once a fiber-linear graph-respecting transducer has been reconstructed to its canonical injectively labeled DLSL presentation, any alternative visible-state labeling that remains destination-labeled and label-deterministic on the same visible graph yields an equivalent presentation of the same visible-state dynamics. In that sense, injective labels are a presentation choice rather than part of the intrinsic structure. 7.2 Edge-entry DLSL systems A second extension relaxes reset-to-top. Instead of forcing every decision from i to enter the top state of the successor fiber j, we may allow the entry phase to depend on the visible edge (i,j)(i,j). Definition 7.1 (Edge-entry DLSL system). An edge-entry DLSL system consists of =(S,E,ℓ,s0,d,ρ,(gi)i∈S),A=(S,E, ,s_0,d,ρ,(g_i)_i∈ S), where (S,E,ℓ)(S,E, ) is destination-labeled, self-looping, and label-deterministic, where di≥1d_i≥ 1, where each gi:Ω→Σig_i: → _i is a local decision map, and where ρ:E→ℕρ:E satisfies 0≤ρ(i,j)≤dj−10≤ρ(i,j)≤ d_j-1 for every edge (i,j)∈E(i,j)∈ E. The operational update becomes (i,r)→(i,r−1),r>0,(j,ρ(i,j)),r=0 and j=δ(i,gi(u)).(i,r) u cases(i,r-1),&r>0,\\ (j,ρ(i,j)),&r=0 and j=δ(i,g_i(u)). cases The original DLSL model is the special case ρ(i,j)=dj−1ρ(i,j)=d_j-1 for every edge. Figure 5 shows exactly what changes in this extension. The internal geometry of each fiber remains a directed hold path, but the target of a visible decision no longer has to be the top state of the successor fiber. What matters instead is that each visible edge (i,j)(i,j) determines a designated entry state inside Fib(j)Fib(j), which is the structural condition captured next by entry-consistency. (a) Standard reset-to-toppip_itjt_j⋅·pjp_jholdholduuρ(i,j)=dj−1ρ(i,j)=d_j-1:decision enters the top phase(b) Edge-entry resetpip_itjt_jeije_ij⋅·pjp_jholdholdholduuρ(i,j)=Phasej(eij)ρ(i,j)=Phase_j(e_ij):the entry phase may depend on the visible edge (i,j)(i,j) Figure 5: Reset-to-top versus edge-entry semantics. The original DLSL model always resets a decision from fiber i into the top state of the successor fiber j. The edge-entry extension of Theorem 7.3 allows the target state to be a designated interior entry state eije_ij depending on the visible edge. Definition 7.2 (Entry-consistent path-fiber transducer). A graph-respecting transducer is entry-consistent path-fiber if every visible-state fiber is a directed simple hold path with a unique decision state and, for every visible edge (i,j)(i,j), there exists a distinguished entry state eij∈Fib(j)e_ij (j) such that every decision transition from the decision state of fiber i into visible state j lands in eije_ij. Theorem 7.3 (Converse theorem for edge-entry systems). The phase-expanded realizations of edge-entry DLSL systems are exactly the entry-consistent path-fiber graph-respecting transducers. Moreover, the edge-entry parameters did_i and ρ(i,j)ρ(i,j) are reconstructed uniquely from the fiber lengths and designated entry states. Proof. The forward direction is immediate from the operational semantics: each fiber remains a directed hold path, and a decision from i to j lands in the designated state (j,ρ(i,j))(j,ρ(i,j)). For the converse, let T be entry-consistent path-fiber. Reconstruct the visible graph, dwell values, and decision states exactly as in Theorem 5.6. For each visible edge (i,j)(i,j), let eije_ij be the designated entry state of Fib(j)Fib(j), and define ρ(i,j):=Phasej(eij).ρ(i,j):=Phase_j(e_ij). The same bijection Φ(q)=(λ(q),Phaseλ(q)(q)) (q)=(λ(q),Phase_λ(q)(q)) used in Theorem 5.6 remains well-defined because each fiber is still a directed simple hold path, so Phaseλ(q)(q)Phase_λ(q)(q) is the unique distance from q to the terminal decision state of its fiber, independent of the entry point. The operational semantics of the reconstructed edge-entry system match the transitions of T under Φ : for a decision from visible state i to visible state j, the operational update lands in (j,ρ(i,j))(j,ρ(i,j)), while entry-consistency ensures that T lands in the distinguished state eij∈Fib(j)e_ij (j) with Phasej(eij)=ρ(i,j)Phase_j(e_ij)=ρ(i,j). Thus Φ intertwines the two dynamics exactly. Uniqueness of the parameters follows because the path order in each fiber is unique and the designated entry states are part of the transducer itself.∎ Corollary 7.4 (Recognition of the edge-entry extension). Accessible entry-consistent path-fiber transducers can be recognized and reconstructed in polynomial time by the same fiber inspection used in Theorem 6.1, augmented with the check that all decision transitions from a fixed source fiber into a fixed successor fiber land in a unique designated entry state. Proof. The path test is the same as before. Once the unique decision state pip_i in each fiber is known, inspect all transitions Δ(pi,u) (p_i,u) such that λ(Δ(pi,u))=jλ( (p_i,u))=j. Entry-consistency requires that all such transitions land in the same state eij∈Fib(j)e_ij (j). If two such transitions land in distinct states of Fib(j)Fib(j), the transducer is not entry-consistent. This check is performed by a single scan of the decision transitions, hence in time linear in |Q||Ω||Q|| |.∎ 8 Related work The closest background is classical deterministic automata and transducer theory, especially sequential and subsequential transducers, minimization, and algebraic structure [HopcroftMotwaniUllman2006, Sakarovitch2009, Choffrut1979, Choffrut2003, Mohri2000]. The present paper does not propose a new general model of regular functions. Its contribution is structural: it isolates a rigid subclass of graph-respecting deterministic transducers and characterizes that subclass intrinsically. There is also a natural relation with the broader theory of regular word functions and their machine models [FiliotReynier2016]. That literature studies equivalences between transducer formalisms, logical definability, and algebraic characterizations of regular functions. The present setting is narrower: the visible graph is fixed, graph-preserving realization is required, and the main outcome is a canonical internal decomposition. From that viewpoint, fiber-linearity should be read as a recognition criterion for a specific transducer subclass rather than as a general expressiveness result. The DLSL framework is also motivated by the limitations of global sequence classifiers for systems with per-state structure. Hidden semi-Markov models [Yu2010] encode dwell probabilistically and generatively but do not address deterministic realization, exact state cost, or hard graph constraints. Semi-Markov conditional random fields [SarawagiCohen2004] are discriminative but globally trained, with no per-state classifier structure and no hard transition constraints. LSTM-based sequence classifiers [HochreiterSchmidhuber1997] likewise learn transition structure implicitly from data. When transition graphs and minimum dwell values are physically known in advance, encoding them as hard structural constraints yields a more interpretable and structurally grounded model. The present paper provides the formal foundation for that encoding: it identifies the exact transducer class induced by those constraints, proves that the class is rigid, and gives a polynomial-time recognition procedure. The timing aspect is related, but not identical, to timed automata and hybrid-system abstractions [AlurDill1994, AlurEtAl1995]. Timed automata work over dense time and are analyzed through clocks, regions, or zones, whereas the present model uses discrete symbolic time and finite phase counters attached to visible states. The resulting questions are correspondingly different: exact deterministic realization on a fixed visible graph, exact state cost, canonicality, and recognition of the induced subclass. There is also a conceptual connection with dwell-time conditions in switched and hybrid control [Morse1996, HespanhaMorse1999, HespanhaLiberzonMorse2003, LiberzonMorse1999, Liberzon2003]. In that literature, dwell is imposed to control switching behavior of continuous dynamics. Here dwell is purely symbolic: it constrains when visible departures may occur and forces a specific finite-memory architecture inside a deterministic transducer. 9 Conclusion We identified an exact structural subclass inside deterministic transducer theory. The phase-expanded realizations of DLSL systems are precisely the graph-respecting transducers whose visible-state fibers are linear hold paths with a unique decision state; equivalently, each fiber carries a monogenic aperiodic chain monoid and cross-fiber actions factor through its distinguished active state. This characterization has three immediate consequences. First, the phase-expanded realization has exact graph-preserving state cost: enforcing dwell values did_i requires exactly ∑idi _id_i control states in the deterministic graph-preserving setting. Second, the class is rigid: under natural reachability and realizable-departure hypotheses, equivalent accessible fiber-linear transducers over the same visible graph are isomorphic. Third, the same reconstruction perspective remains valid beyond the canonical normal form: injective labels are only a presentation device, and the edge-entry variant is handled by the same path-fiber analysis and admits its own converse and recognition theorem. Two natural directions remain. One is to identify broader classes of graph-respecting deterministic transducers that admit comparable canonical decompositions. The other is to measure, in structural terms, how far a general graph-respecting transducer lies from the DLSL or edge-entry regimes. Appendix A Visible-state run-length formulation The main body of the paper is organized around the internal structure of graph-respecting deterministic transducers. There is also a complementary behavioral view, stated directly on visible-state traces. Since it is not part of the intrinsic converse route, we collect it here. For a visible-state word τ=y0y1⋯yn∈Sn+1τ=y_0y_1·s y_n∈ S^n+1 and an index 0≤t≤n0≤ t≤ n, define the current run length by runτ(t):=maxℓ′≥1:t−ℓ′+1≥0 and yt−ℓ′+1=⋯=yt.run_τ(t):= \ ≥ 1:t- +1≥ 0 and y_t- +1=·s=y_t \. To avoid confusion with the visible-state labeling ℓ , we use ℓ′ here only as a local dummy variable. Theorem A.1 (Characterization of realizable visible-state traces). Assume that the symbolic DLSL system is destination-complete. Let τ=y0y1⋯yn∈Sn+1with y0=s0.τ=y_0y_1·s y_n∈ S^n+1 y_0=s_0. Then there exists an input word w∈Ωnw∈ ^n such that τ=tr(w)τ=tr_A(w) if and only if the following two conditions hold: 1. Graph-feasible adjacency: yt+1∈Out(yt)for every t=0,…,n−1;y_t+1 (y_t) every t=0,…,n-1; 2. Minimum dwell before departure: whenever yt≠yt+1y_t≠ y_t+1, runτ(t)≥dyt.run_τ(t)≥ d_y_t. Proof. Necessity is immediate from the operational semantics. Suppose τ=tr(w)τ=tr_A(w) for some input word. At each time step the visible successor is either the current visible state itself, during forced hold, or a visible successor selected by the local decision map. In either case yt+1∈Out(yt)y_t+1 (y_t), so condition (1) holds. Now assume yt≠yt+1y_t≠ y_t+1. Let i=yti=y_t, and let s be the first time index of the maximal block of i ending at time t. Then ys=ys+1=⋯=yt=i,ys−1≠iif s>0.y_s=y_s+1=·s=y_t=i, y_s-1≠ i s>0. When the machine enters visible state i at time s, its residual phase is reset to di−1d_i-1. Each subsequent time step spent in i decreases this phase by one. A non-self departure at time t is possible only if the symbol read at time t+1t+1 is processed from phase 0. Thus the phase must have gone from di−1d_i-1 down to 0 over the interval from entry at time s to the departure point at time t, which requires at least di−1d_i-1 steps after entry: t−s≥di−1.t-s≥ d_i-1. Equivalently, t−s+1=runτ(t)≥di,t-s+1=run_τ(t)≥ d_i, which is condition (2). For sufficiency, assume that τ satisfies conditions (1) and (2). We construct an input word w=u1⋯unw=u_1·s u_n inductively so that the induced visible trace is exactly τ. At time t, suppose the currently realized visible state is yty_t. Let rt:=maxdyt−runτ(t), 0.r_t:= \d_y_t-run_τ(t),\,0\. This is the residual phase that should be present at time t if the earlier part of the trace has already been realized. There are three cases. Case 1: yt+1≠yty_t+1≠ y_t. By condition (2), runτ(t)≥dytrun_τ(t)≥ d_y_t, hence rt=0r_t=0. Since the graph is destination-complete and yt+1∈Out(yt)y_t+1 (y_t), there exists an input symbol ut+1u_t+1 such that gyt(ut+1)=ℓ(yt+1).g_y_t(u_t+1)= (y_t+1). Reading this symbol causes the visible state to move to yt+1y_t+1, as required. Case 2: yt+1=yty_t+1=y_t and rt>0r_t>0. Then the dynamics force the visible state to remain equal to yty_t regardless of the input. Choose any ut+1∈Ωu_t+1∈ . Case 3: yt+1=yty_t+1=y_t and rt=0r_t=0. Here the machine is free to decide, but we want it to stay at the same visible state. Because the visible graph is self-looping and destination-labeled, the self-label ℓ(yt) (y_t) belongs to Σyt _y_t, and by destination-completeness there exists an input symbol ut+1u_t+1 such that gyt(ut+1)=ℓ(yt).g_y_t(u_t+1)= (y_t). Reading this input triggers the self-loop and again realizes yt+1=yty_t+1=y_t. In every case we can choose ut+1u_t+1 so that the prefix u1⋯ut+1u_1·s u_t+1 realizes the prefix y0⋯yt+1y_0·s y_t+1. Induction on t completes the construction. ∎ (a) Legal visible-state traceiijjkkjj2≥di2≥ d_i3≥dj3≥ d_j1≥dk1≥ d_k3≥dj3≥ d_j(b) Illegal early departureiijjkk1<di1<d_ideparture from i occurs too early Figure 6: Visible-state traces as run-length constraints. Theorem A.1 can be read directly on the visible trace: each maximal block of a visible state must have length at least the dwell value attached to that state before a departure to a different visible state is allowed. Corollary A.2 (Regularity of the visible-trace language). Assume destination-completeness. Then Ltr():=tr(w):w∈Ω∗⊆S∗L_tr(A):=\tr_A(w):w∈ ^*\ S^* is a regular language. Proof. By Proposition 3.1, the symbolic DLSL system is realized by a finite-state transducer on the phase-expanded state set. By Theorem A.1, the visible traces are exactly those visible-state words satisfying a finite-memory condition: graph-feasible adjacency together with a minimum dwell requirement before each departure. Either description yields a finite automaton recognizing the trace language. Hence the language is regular [HopcroftMotwaniUllman2006]. ∎ Corollary A.3 (Injective-label version). If the visible-state labeling ℓ:S→Σ :S→ is injective, then minimum dwell is equivalent to a state-dependent minimum run-length condition on the emitted label stream (ℓ(yt))( (y_t)). Proof. When ℓ is injective, maximal visible-state blocks and maximal emitted-label blocks coincide. Apply Theorem A.1. ∎ References