Generalized Star Height at Most Three

1 Introduction

The star operation permits a finite language expression to describe an arbitrarily long repetition. Its nesting depth measures how many layers of repetition an expression uses. Once complement is allowed, Boolean conditions can replace some of those layers. The question studied here is whether a fixed number of layers suffices for every regular language, independently of its alphabet and recognizing automaton.

Fix a finite alphabet \Sigma. A generalized regular expression over \Sigma uses 0, 1, the singleton letters of \Sigma, union, concatenation, complement, and Kleene star. The constants denote \emptyset and \{\eps\}, and complement is always taken in \Sigma^*. Its height is determined by

For a regular language L\subseteq\Sigma^*, write h_\Sigma(L) for the least height of an expression defining L. In particular, complement preserves the nesting already present in its argument. Finite Boolean combinations preserve a common height bound, and the full language \Sigma^*=\neg0 has height zero.

The expressions in the theorem use the letters of \Sigma itself. Their finite parameters and their lengths may depend on the language. The construction gives an upper bound on nesting, without a bound on expression size or running time.

1.1 The problem and its mathematical context

The corresponding ordinary star-height problem omits complement. Eggan connected ordinary star height with the cycle structure of transition graphs, and Dejean and Schützenberger established unbounded ordinary star height already over a two-letter alphabet [4, 5]. These results concern the operations allowed in ordinary expressions. Their lower bounds do not carry over merely by adding complement.

Generalized height zero already has a different character: its languages are the star-free languages, which need not be finite. A finite monoid M recognizes a language when membership depends only on the image of a morphism from \Sigma^* to M. Schützenberger characterized the star-free languages as exactly those recognized by finite aperiodic monoids [12]. Here a monoid is aperiodic if every element m satisfies m^r=m^{r+1} for some r\ge1. A simple language requiring one star is (aa)^* over \{a\}: its displayed expression has height one, while every star-free unary language is finite or cofinite, as induction under union, complement, and concatenation shows.

The algebraic approach has also produced substantial families of height at most one. Pin, Straubing, and Thérien proved this bound for languages recognized by finite nilpotent groups of class two, and for further classes of finite monoids [11, Theorems 7.3 and 7.8]. Another line of results concerns words in which a fixed nonempty factor occurs contiguously a prescribed number of times modulo an integer n\ge2, with overlapping occurrences counted. Bourne and Ruškuc proved height-one bounds for factors of length at most three [3, Proposition 2.5]; Bourne subsequently extended the result to arbitrary fixed factors in his thesis [2, Theorem 2.25]. These results explain how complement can simplify nontrivial counting languages, but their restricted families do not supply a bound for arbitrary regular languages.

A universal finite upper bound and a universal upper bound of one are different assertions; Straubing distinguishes them explicitly in his account of the problem [13, p. 537]. Theorem 1.1 gives a positive answer to the boundedness question. It does not exhibit a language of generalized height greater than one, and does not decide whether one always suffices.

Two companion constructions explain the setting of this proof. The paper Finite Monoid Computations and a Uniform Generalized Star-Height Bound proves a bound of thirteen by finite computations, a prediction argument, and a decision tree that retains the complete earlier history [9, Theorem 1.1 and Sections 2–7]. Generalized Star Height at Most Four proves a bound of four using constancy on affine coordinate lines, several marker scales, and product transport across moving periodic boundaries [10, Theorem 1.1 and Sections 2–6]. The present construction obtains three through two split steps. Each of the three papers gives its own complete proof; the numerical theorem of one is not used to prove another. The prediction and multiscale methods remain different constructions even though the bound here is smaller.

1.2 Computing a word value with independent tests

Every regular language has a recognizing morphism T:\Sigma^*\to M into a finite monoid. We therefore seek expressions for the fibers of T. The construction parses a word into complete pieces called episodes, followed by a final remainder. The episode language E is a prefix code, meaning that no member is a proper prefix of another. This makes the episode boundaries unique.

An episode will act on a finite vector space by an affine map. To propagate its state, we cut the episode and test the prefix for an input state and the suffix for an output state. The tests are languages placed in separate factors of a concatenation. Thus their auxiliary choices are independent. A valid split has to meet two separate obligations: every successful pair beginning at a true episode boundary must consume that entire first episode and transmit its update; for every input state, a successful pair must exist on each episode that is not assigned to a specified skipped class.

Section 2 proves a split identity that converts these obligations into expressions for arbitrary episode sequences. If the individual tests and the episode domain have height at most one and sequence computations on the skipped class have height at most H, the identity gives height at most \max\{2,H+1\}. The split and affine recovery methods are developed in the two companions [9, Lemmas 2.2–2.3] and [10, Lemmas 2.1–2.2]; all versions used here are proved locally. An affine correction does not destroy the original computation: the difference between the outputs on x and on zero recovers the linear part on x. Finite unions and intersections express this subtraction without another star.

1.3 Why two splits suffice

The first split uses later cuts in an episode and a finite set of tags. A tag is a tuple of states, interval products, and indices that a test proposes to use. The prefix and suffix choose their tags separately. A clock restricts the pairs they can jointly realize: either they agree, or there is only one possible unequal pair. In the second case we define the episode’s affine translation so that this one pair transmits the prescribed input to the prescribed output. To use the clock, however, both tests must calculate the same total time. A separate end guard establishes that fact; it is not a consequence of the clock.

The clock also needs room to realize its permitted choices at actual cuts. Outside an exceptional set of total times, every tag permits a whole neighborhood of compatible prefix times, with a common positive margin. The clock also supplies a finite list of candidate times for which the number of exceptional pairs is bounded uniformly under translation and sufficiently small simultaneous perturbations. These are the additional clock properties used here; Section 3 compares the quantitative bounds.

When tags agree, the first split has two ways to work. If all the marker boundaries are present, their successive intervals give a tuple of monoid products. A finite shift table makes one coordinate of this tuple irrelevant to the transmitted output. The prefix checks the earlier products, the suffix checks the later products, and a finite certificate checks every possible value of the product crossing their cut. If a marker boundary is absent, a long periodic stretch instead allows the cut to move through all clock residues while keeping its prefix product fixed. This argument uses eventual periodicity of powers in a finite monoid; it requires no cancellation.

The shift table is uniform in a stronger sense than a product-action statement. One tuple length, chosen using only the finite entry alphabet and state space, must work for every table from tuples to linear maps. A single correction table is chosen for each such map, independently of the input vector. The coordinate that can be omitted may depend on the tuple and vector. This quantifier order is proved by a finite avoidance argument of the local-lemma type of Erdős and Lovász [6].

The clock and marker conditions used to guarantee the first split’s completeness can fail on an intrinsic sublanguage D\subseteq E. The second split handles every episode in D, with no further skipped class. A suffix at an earlier cut can use the failed condition as a witness to the actual origin. Those early cuts form a fixed finite set, or stencil, containing many copies of every required tuple of metadata. The differences between distinct stencil positions have different residues. Marker searches with widths indexed by these residues make false witnesses sparse over all ordered pairs of positions, including pairs with incorrect metadata.

End detection needs special care in this count. A smaller bounded search fixes an episode’s end when it finds an end marker; otherwise a periodic seed is followed to its first mismatch. A larger bounded search supplies the clock anchor whenever possible. If that larger search is absent at one nearby proposed origin, all the smaller searches are absent, and their overlapping seeds have one common mismatch. If every larger search is present, all candidate clock anchors are already bounded data. In either case the true origin’s witness remains available before the suffix requires uniqueness. After identifying it, the suffix must separately check its exact endpoint. Counting over the whole stencil leaves a usable copy of every metadata tuple and supplies the second split.

1.4 From finite tests to height-three expressions

The local marker construction is a finite-window instance of the marker-versus-periodicity method [7, Lemma 2]; its full priority construction and periodic-overlap argument are given in Section 4. Section 3 proves the robust clock. Section 5 then chooses all finite parameters in dependency order. In particular, a provisional rational clock fixes the early stencil before the marker scale is chosen. A later rational approximation preserves those fixed trials and makes the final clock period coprime to all relevant short periods.

Sections 6 and 7 construct episodes, force a common end under independently chosen roles, and prove the first split. Section 8 establishes the bound on all false origins and the suffix decoder. Section 9 uses the remaining suffix to compute a total table indexed by every hypothetical prefix product in M, including values that no prefix realizes. Applying the shift-table lemma to this table gives the second split.

The last step, Section 10, controls expression height for each component on its own domain. A standalone suffix, even with false origin data, has its own exact-end test. It consequently lies in a finite union of fixed-word templates ac^ib. The accepted exponents are ultimately periodic, which gives height-one expressions over the original letters. The incomplete remainder has the same kind of expression. The inner split starts from empty skip computations and gives height two; recovery makes those computations the skips for the outer split, giving height three. Finite Boolean recovery and concatenation with the remainder add no star. Tags, states, and residues serve only as finite indices in these expressions.

2 Finite computations and split expressions

The language problem will be represented by a finite computation. This section supplies three interfaces for manipulating it: an expression identity that propagates an update through episodes, a Boolean operation that removes an affine correction, and a finite table that allows one unknown coordinate. Each interface will be used twice, with different state spaces. The related split and recovery constructions in [9, 10, Section 2] explain the method; the exact statements and proofs needed here are included below.

2.1 Monoid values and deterministic updates

If \Sigma=\emptyset, its only languages are 0 and 1, both of height zero. Assume henceforth that \Sigma is nonempty, and fix a morphism

into a finite monoid M. For a deterministic finite automaton, take M to be the finite monoid of state transformations induced by words, including the identity transformation. Its accepted language is a finite union of fibers of T. Thus it suffices to construct a height-three expression for each fiber of every such morphism.

Letters occupy intervals [a,a+1) with integer endpoints. For an available interval [a,b), a\le b, write T_{a,b} for its monoid value, with T_{a,a}=1_M. Products are in reading order:

Let V=\mathbf F_2^M have basis (e_m)_{m\in M}. Each d\in M acts linearly on the right by e_m d=e_{md}. This is the linearized right regular action [1, Section 3.1]. It is faithful because e_{1_M}d=e_d identifies d. Vectors are written on the left of their linear maps, so vLA means first apply L, then A. We will also use U=V\oplus\mathbf F_2; the additional coordinate will turn affine maps on V into linear maps on U. All vector spaces below are finite.

Put N_M=|M|!. Finiteness gives

Indeed two of c^0,\ldots,c^{|M|} agree, say c^a=c^b with 0\le a<b\le |M|. Powers are then periodic from exponent a, with period b-a, which divides N_M. This includes |M|=1.

A prefix code is a set E\subseteq\Sigma^+ containing no proper-prefix pair. Its members will be called episodes. Every word in E^* has a unique factorization into episodes: the first factors of two proposed factorizations are comparable by the prefix relation and therefore equal, after which induction applies. The empty word has the empty factorization.

For D\subseteq E, assign to each e\in D a deterministic total map G_e:S\to S on a fixed finite state set S. On w=e_1\cdots e_r, let G_w apply the updates in reading order; G_\eps is the identity. The graph language from x to y on D^* is

The indicated domain is part of this definition. The update is determined by the episode itself, independently of choices made by an expression that tests its graph.

Finite intersections can be expressed using union and complement and do not increase generalized star height. A finite language has height zero: write its words as concatenations of letters, use 1 for \eps, and take a finite union. Auxiliary finite indices below are never input letters.

2.2 The split identity

The next lemma separates two obligations. Every successful split must transmit the correct state and consume exactly one episode. Existence of a split is required only outside the domain that is to be skipped.

When D'=\emptyset, the skip language W_{x,y} is 1 for x=y and 0 otherwise. Its height is zero, so this case of the lemma has height bound two. Notice also that condition (i) rules out a successful pair on the empty word. Independent choices in P_x and Q_y must satisfy it even when their proposed metadata disagree.

2.3 Removing affine corrections

We will deliberately alter an episode’s translation term to make its split possible. The following identity explains why this is harmless. The output on zero isolates the translation of a whole composite, even when none of its linear factors is invertible. The two computations must be required on the same word, which is why the expression uses an intersection.

2.4 A shift table that hides one entry

A cut can leave one interval product unreadable by either factor. We will replace the demand to know that product by a finite certificate that checks all of its possible values. To make such a certificate available, we need a deterministic affine correction with a constant coordinate line through every tuple, for every input state.

The order of quantifiers matters: the length is selected first, uniformly in the table of linear maps; a correction is then fixed for each table; only afterward may a tuple and input state select a successful coordinate. The product-action version in [10, Lemma 2.3] motivates this step, but an arbitrary table is needed for the second split below.

Fix one successful \beta_f for each of the finitely many possible functions f at these dimensions. The resulting map x\mapsto xf(\mathbf a)+\beta_f(\mathbf a) is now determined by the tuple and table, before any splitting choices are made. A prefix can certify its output using the other entries by checking every replacement for the omitted coordinate. The lemma promises a usable coordinate for each actual input, not one coordinate usable for all inputs at once. Nor does it restrict f to tables obtained from feasible word prefixes. This unrestricted table domain will be essential when a suffix computes hypothetical prefix values in Section 9.

3 A robust tag clock

The shift table supplies compatible data when both factors use the same tag. The next construction limits the damage from independent tag choices. For each possible total time, it will permit only equal tags or exactly one unequal ordered pair. Later, the episode’s affine shift will accommodate that one exceptional pair.

We need more than this compatibility rule. A finite roster of candidate positions must encounter few exceptional totals, uniformly under every translation. Outside the exceptional set, each tag must admit a decomposition with a common positive interior margin, so a sufficiently fine grid can find one. The logarithmic estimate and its forest argument are developed in [9, Lemma 3.1], with constant 1{,}300{,}000. Here the estimate 10^7\log(2m) accompanies a torus construction whose common interior margin and perturbation tolerance let us postpone the final clock period.

Write \mathbb T=\mathbb R/\mathbb Z and \|x\|_{\mathbb T}=\min_{j\in\mathbb Z}|x-j|. A finite product \mathcal T=\mathbb T^C is given the maximum metric \operatorname{dist}(u,v)=\max_{c\in C}\|u_c-v_c\|_{\mathbb T}. Addition and subtraction are coordinatewise. For subsets, I+J denotes the set of sums of their elements, and z-J=\{z-j:j\in J\}. All logarithms in the clock estimate are natural.

To see how the clock will be applied, take a periodic additive map \varphi:\mathbb Z\to\mathcal T. A prefix ending at k can test \varphi(k-t)\in I_\alpha, and a suffix starting there can independently test \varphi(q-k)\in J_\lambda. Once t,q,k refer to the same positions, the pair lies in \mathcal E_{\varphi(q-t)}. The graph alternative then gives either equality of tags or a unique unequal pair. It says nothing by itself about whether the suffix chose the correct anchor q; that is the purpose of the end guard in Section 6. Finally, periodicity makes all clock membership tests finite tables on integer residues. The torus is used to construct the tables, not as an extra input alphabet.

4 Local markers and periodic continuations

The clock provides algebraic control of the two tests. We now arrange letter positions so that those tests can read enough information on opposite sides of a cut. A local priority rule distinguishes two cases: a nearby marker offers a boundary; the absence of nearby markers forces a periodic block. Overlap will make many such blocks part of one common repetition.

This is the finite-word marker principle associated with Krieger’s marker lemma [7, Lemma 2]. Related priority constructions are used in [9, Section 4] and [10, Section 4.1]; a general clopen merge formulation is presented in [8, Lemmas 3.2–3.4]. We prove the exact finite-window and overlap statements used here. They do not require an embedding or a change of alphabet.

Positions of letters are integers. Intervals of possible marker positions are inclusive integer intervals; a block of letters on [a,b) has length b-a. A positive integer p is a period of a finite block if its letters at positions differing by p agree whenever both positions belong to the block.

A later search may inspect several possible origins. It is not enough to know that each corresponding seed is periodic: they must describe the same continuation. The following elementary overlap estimate gives this agreement and also converts an interval without markers into a single periodic run.

We adopt a fixed convention for finite arguments. A required marker inspection is performed only when its entire window lies in that argument; otherwise the whole test rejects. In particular, an unavailable window never removes an origin from a comparison or uniqueness test. This convention is what permits the two-sided proof to establish facts about the actual letters read by a prefix or suffix.

5 Finite schedules for the two splits

We now turn the three preceding tools into fixed positions at which the prefix and suffix may read. There will be early cuts that encode metadata by prefix length, and later cuts that use the tag clock. Every set of cuts is finite and is fixed using only M and \Sigma, before the input word is read.

The order of selection is part of the construction. We first list all possible metadata and fix residue classes for their copies. A provisional clock then realizes the early positions. Those positions determine how widely markers must be separated. Only after this separation is known do we choose the prime factors of the final clock. Its approximation is made on already fixed finite sets, so no earlier length has to be enlarged. The remaining choices are successive lower bounds on search widths and gaps. This section verifies both existence and the reading-side properties of that schedule.

Recall that V=\mathbf F_2^M and U=V\oplus\mathbf F_2. The second space accommodates homogeneous lifts. Positions and cut offsets are integers; search intervals include both endpoints, while inspected letter intervals have the half-open convention of Section 4.

5.1 A finite set of metadata and positions

Apply Lemma 2.4 with entry alphabet M and state spaces V and U, and choose the resulting positive tuple lengths g and g', respectively. For the early schedule, a kind is a tuple

The list \mathbf d_{-j} retains the indices and order of all entries except j. The function \psi will record how later letters turn the monoid value of the early region into a linear update on U. There is no feasibility restriction on any field: in particular, every total function \psi of the indicated type occurs. Let \kappa count these kinds. Make \mu distinguishable copies of each kind, for a positive integer \mu to be fixed below, and call the resulting roster \mathcal P. It has N=\kappa\mu slots. Order them in consecutive blocks according to j=1,\ldots,g'. The copies will let us lose some positions to false-origin ambiguity without losing any kind altogether.

Set

and reserve residue r_i for slot i. The ordered differences r_i-r_j, for i\ne j, are all nonzero and distinct modulo B. To check this, suppose first that i>j. As an integer the difference is

The second summand lies strictly between 0 and 2N^2, so division by 4N^2 determines i-j. The remaining summand then determines i+j, and hence i,j. Positive differences are distinct, as are their negatives. All signed differences lie in an interval of length less than B, and no positive difference equals a negative one. Reduction modulo B therefore preserves their distinctness and nonzero values.

The later clock uses a separate tag set \Lambda. A main tag has the form

where A,C\in M, \mathbf d_{-j}\in M^{g-1}, and X,Y\in V. A periodic tag has the form

where m_p\in M and X,Y\in V. The form itself is part of the tag. The fields X,Y of a tag \alpha are denoted X(\alpha),Y(\alpha). In particular, the clock period and all marker inspection radii are absent from the tag fields. If m=|\Lambda|, then

Choose \mu large enough that

where c_{\rm cl} is the constant in Lemma 3.1. Although m depends on \mu, this requirement is not circular. The numbers \kappa,g,g' and the spaces V,U were fixed before \mu. The displayed formulas make B polynomial in \mu and m a constant multiple of B. The right side of (17) thus grows logarithmically, while the left side grows linearly. Choose and fix one such \mu. From now on the roster, all residue classes, and the entire tag set are fixed; no clock period or inspection radius is a tag field.

5.2 The provisional clock and the early schedule

Apply Lemma 3.1 to \Lambda and the roster. Write its torus as \mathcal T, its sets as I_\alpha,J_\alpha,W, its roster targets as v_p, and its common ball radius as \rho>0. We first select a provisional additive map \varphi^0:\mathbf Z\to\mathcal T. In each circle coordinate choose its speed to be 1/n_i^0, where the n_i^0 are distinct sufficiently large primes greater than B, and put

The set

is the full product grid with coordinate orders n_i^0. Indeed, multiplication by B is invertible modulo every n_i^0, and the Chinese remainder theorem prescribes all coordinate residues independently. The same assertion holds for any R consecutive representatives of a fixed residue class modulo B. Choose these primes so large that the grid has covering radius less than \rho/3 in the maximum circular metric, and is fine enough to approximate each target v_p strictly inside the perturbation tolerances of Lemma 3.1.

Put w_0=BR. Realize the ordered roster by positive increasing integers p_1,\ldots,p_N such that

and all ordered nonzero differences p_i-p_j are at distance greater than 2w_0+2 from each other and from 0. These requirements can be met inductively. For each slot, the grid property supplies an admissible integer in its reserved class, and adding multiples of BR leaves both that class and its provisional clock value unchanged. At the next insertion, place the new point so far to the right that all new positive differences exceed every old positive difference by more than 2w_0+2. The differences between two of these new differences are differences of previous points, which already have the required separation. Their negatives satisfy the same conditions. Also leave an integer gap between successive blocks of slots.

From this point, \mathcal P denotes this set of integer offsets, with each offset still carrying its original kind and copy label. Write h=\operatorname{diam}\mathcal P. Choose fixed integer boundary offsets

so that every slot of block j lies strictly between \beta_{j-1} and \beta_j. For a word beginning at s, the corresponding early boundaries are

and its early candidate cuts are s+p, p\in\mathcal P.

5.3 The final clock and inner marker searches

The early positions are now fixed. We next choose the inner marker rule, and only then the prime factors of the final clock. Choose integers

and obtain an inner marker rule of radius r\ge K from Lemma 4.1. Put N_M=|M|!.

In each coordinate, approximate the provisional speed 1/n_i^0 by a_i/n_i, where the n_i are distinct primes greater than d,N_M,B and 1\le a_i<n_i. Arbitrarily accurate such approximations exist by taking the primes sufficiently large and rounding n_i/n_i^0 to an integer. Let \varphi be the resulting additive map and put

The map \varphi factors through \mathbf Z/n\mathbf Z. Approximate closely enough on the already fixed finite sets \mathcal P and \{aB:0\le a<R\} that

For the first assertion, keep every \varphi(p) within the clock’s single allowed perturbation tolerance of its target. For the second, keep every value at an argument aB, 0\le a<R, within the unused margin between the provisional covering radius and \rho. Only finitely many arguments are involved, so one sufficiently accurate approximation satisfies both requirements. Every translate of this fixed net meets every clock ball of radius \rho.

The construction now has the two properties it will use separately: the clock period has no small prime factors, while the useful R-term net and w_0=BR keep their earlier sizes. Replacing R by the final period here would lose this independence and is unnecessary.

Choose positive integers L_{\rm lag} and H_{\rm ext} with

Choose positive widths H_u, indexed by 0\le u<B, each divisible by B and greater than 2d, with pairwise distances

For each fixed anchor in the false-origin count, distinct displacement residues will give distinct width indices. This spacing will separate the right endpoints of searches whose left endpoints lie in one short interval. Finally choose a positive multiple G of 2B such that

All these requirements are lower bounds on successively chosen integers, so they are simultaneously satisfiable.

An episode beginning at s will have a sampling origin t=s+L, where the fixed positive lag L will be chosen after all bounded windows are known. For any integer origin t, define

for 0\le j\le g and 0\le u<B. The value is \bot when the search finds no marker. Equality of search values means equality of absolute positions, or that both values are \bot.

Let \mathcal H be the full finite set of offsets k-t in (29) and (30), over all their indicated indices. Choose an integer

The next observation records exactly how the periodic schedule will supply clock choices when an inner marker search is absent.

The schedule is now complete except for its placement inside an episode. Main cuts separate the required marker products, and periodic cuts provide a fixed prefix product while sweeping the clock image. Both schedules have offsets divisible by B. The next section puts all their windows, including the displaced windows used by false suffix hypotheses, strictly inside each episode. A separate marker rule there determines the end.

6 Episodes and a common end for independent guesses

A correct clock calculation needs a common clock anchor. A suffix may propose a different origin or even a different role from the prefix, so its own local description cannot be assumed to give that anchor. We therefore define episodes by a rule that can be checked from later letters, and require a guard comparing every possible outer origin.

Two end searches have different responsibilities. The smaller search helps define the episode endpoint; the larger search supplies a bounded clock anchor whenever possible. Their distinction also makes the later decoder able to evaluate false origins without seeking a new mismatch past the actual end. Before defining episodes, we place every bounded inspection for every allowed displacement inside the eventual episode.

6.1 Two bounded end searches

Use Lemma 4.1 independently of the inner markers, with integer parameters

Call the resulting markers end markers and their inspection radius r_\bullet\ge K_\bullet. For 0\le u<B set

The center of an end search is z_\bullet(t)=t+o_\bullet, where the fixed offset o_\bullet will be placed below. At an integer origin t, define \eta(t) and \zeta(t) by the following rule, using \sigma=0 and 1, respectively: return the leftmost end marker m_e such that

Return \bot if there is no such marker. Residues used as indices always have representatives in \{0,\ldots,B-1\}. These are bounded searches: the whole inspection is contained in the interval obtained by enlarging [z_\bullet(t)-\max_uD_u^\sigma,z_\bullet(t)+\max_uD_u^\sigma] by r_\bullet on each side.

The eligible set for \eta(t) is contained in that for \zeta(t). This does not say that their returned markers coincide: the larger search may have an earlier eligible marker. The implication we will need also holds across nearby origins:

Indeed, the marker returned at t' is within \max_uD_u^0+2h of z_\bullet(t), whereas

It is therefore eligible at t regardless of its new residue index. This implication is why two search sizes are used.

If \eta(t)=\bot, there is no end marker in [z_\bullet(t)-d_\bullet,z_\bullet(t)+d_\bullet]. The seed

then has a period less than d_\bullet by Lemma 4.1. Its two-sided continuation with a period less than d_\bullet is unique: any two such continuations agree on the seed, whose length exceeds the product of their periods, so Lemma 4.2 identifies them. We shall use this continuation only when \eta(t) is absent.

6.2 Margins and the episode rule

We first identify every bounded window that must remain inside a complete episode. This prevents an incorrect origin or endpoint from making a required check disappear. Set

The first difference set contains every displacement of an outer suffix origin from the true origin at a genuine outer cut, even if the two factors choose different roles. The second contains all origin displacements used to decode an early cut. Both are fixed finite sets.

For inner data allow every origin displacement in \Delta, followed by every additional integer shift in [-w_0,w_0]. Include all indices 0\le u<B, all inner marker inspections, the extended searches through H_u+H_{\rm ext}, the short-period blocks and the finite portions of their continuations used in Lemma 5.2, and the finite cut schedules. This gives a bounded integer offset interval [A_{\rm in},B_{\rm in}] relative to t. For example, it may be chosen to contain every enlarged interval

and every cut offset; enlarge it further if necessary to contain the |M| periods before the base cuts in Lemma 5.2. All these enlargements are finite and fixed at this point.

For end data allow every displacement in \Delta and every additional integer shift in [-w,w]. Include both end-search inspection windows, every seed, every possible bounded marker return, and the right endpoint of every seed. Collect them in a bounded integer interval [A_{\rm end},B_{\rm end}] relative to z_\bullet(t). For clarity, an interval containing the following sets, over all \delta\in\Delta and |v|\le w, is sufficient:

In particular these intervals cover full sweeps of the allowed shifts, not merely the finitely many nominal origins. Neither interval depends on the still unchosen L,o_\bullet,L_{\rm tail}.

Choose positive integers L,o_\bullet,L_{\rm tail} in this order so that

Now fix t=s+L for a word beginning at s. Define its end anchor q_0 as follows. If \eta(t) is present, put q_0=\eta(t). Otherwise use the unique periodic continuation of the seed in (37), and let q_0 be the first letter position at or beyond the seed’s right endpoint where the word differs from that continuation. If that mismatch has not yet occurred in a finite word, the rule supplies no complete episode in that word. When q_0 exists, the required endpoint is

All bounded end inspections and seed data required by the rule must be available, as must the letters through b-1. A word is a complete episode if its own endpoint is exactly this b. Let E be the language of such words, with their beginning normalized to s=0. For each complete episode define the clock anchor

These two anchors have different roles and may coincide. The endpoint is always q_0+L_{\rm tail}. The clock instead uses q, which is a bounded marker return whenever \zeta is present. For example, \eta may be absent and \zeta present; then the endpoint can occur arbitrarily late at a first mismatch while its clock anchor remains bounded. No later argument identifies q with q_0 in this case.

Figure 1 summarizes the order just established. The large gaps also accommodate the false origins; they are not chosen anew after a suffix has made its guesses.

For every prefix or suffix test below, the letters needed for a check must be present in that test’s own argument and on its own reading side. An unavailable inspection or an invalid required product interval causes rejection; it never removes an origin from a universal check. The unbounded portions of the episode rule are continuation tests up to a proposed end. They do not require moving an unbounded inspection window before a cut. Lemma 5.1 supplies the more precise division of inner data between the two sides of an outer cut.

All these definitions commute with translation of positions. A standalone prefix reads from its beginning s to its end k. A standalone suffix begins at k; an origin specified as an offset from k need not itself carry a visible letter in that suffix. Applying the end rule at such an origin requires the end searches and seed in the suffix and its prescribed exact endpoint. It does not ask the suffix to validate omitted prefix letters.

6.3 A guard that forces the true end

At a proposed outer cut k, let the suffix test all origins

Choose once and for all a reference offset in \mathcal H. The common end guard requires both \eta and \zeta to be constant across \mathcal O_k, with equality of absolute positions or of the value \bot. Require all the associated bounded inspections and seed blocks. The suffix must end exactly where the episode rule at the reference origin prescribes, and uses the clock anchor calculated there by (40).

We can now use the clock with genuinely independent prefix and suffix metadata. Even if their proposed roles differ, the guard ensures that the two clock arguments add to the true total \varphi(q-t).

7 The first split: transmitting a state with a clock

The schedule and end guard now permit the first split on the episode code E. We will define its update before its tests, so that successful choices cannot change which computation an episode performs. The update is affine on V and always has the original monoid action as its linear part. Completeness of the tests is required outside an intrinsic domain D\subseteq E; soundness is required for every successful pair on E^*.

The clock makes that soundness feasible. Equal tags let the two factors verify a single consistent table certificate. If their tags differ, the clock leaves only one possible ordered pair, and the affine translation is chosen to realize its prescribed input and output. This choice is made on the episode’s actual clock graph, including episodes for which no split will be available.

Throughout the section an episode is [s,b), with t=s+L and anchors q_0,q as in Section 6. The outer cut offsets form \mathcal H\subset B\mathbb Z. All inspections obey the reading-side and rejection conventions fixed there.

7.1 The exceptional domain and a total affine update

Define Z(t) to mean that at least one of \eta,\zeta is not constant on

For a position Q, let u=(Q-t)\bmod B, with residues represented in \{0,\ldots,B-1\}. Define A_*(t,Q) to be the disjunction of the following three conditions:

1. 1.

   \varphi(Q-t)\in W;

2. 2.

   for some 0\le j\le g and some integer v with |v|\le w_0, f_j^u(t+v)\ne f_j^u(t);

3. 3.

   for some 0\le j\le g, f_j^u(t)=\bot, but the inclusive interval [z_j(t),z_j(t)+H_u+H_{\rm ext}] contains an inner marker.

In the second condition the index u is held fixed as t is shifted. The search values are absolute positions, with \bot equal only to \bot. Set

The episode determines both predicates without choosing a split. Thus D is a fixed language. In particular, failure of a particular choice of tag is not its definition; the same D must serve every input state and every pair of independently chosen tags.

For A,C\in M, write

This is a map from M^g into \operatorname{End}_{\rm lin}(V). For every such map, use the shift table \beta_{f_{A,C}} fixed in Lemma 2.4. We define F_e\colon V\to V on every complete episode, including every episode in D:

1. 1.

   If \mathcal E_{\varphi(q-t)} is the singleton off-diagonal edge \{(\alpha,\lambda)\}, put

   F_e(v)=vT_{s,b}+Y(\lambda)-X(\alpha)T_{s,b}. \tag{44}
2. 2.

   Otherwise put u=(q-t)\bmod B. If at least one f_j^u(t) is absent, put F_e(v)=vT_{s,b}.

3. 3.

   In the remaining case let l_j=f_j^u(t) for 0\le j\le g. Their order is l_0<\cdots<l_g by the schedule. Set

   A=T_{s,l_0},\qquad C=T_{l_g,b},\qquad d_i=T_{l_{i-1},l_i}\quad(1\le i\le g).

   Then put

   F_e(v)=v f_{A,C}(\mathbf d)+\beta_{f_{A,C}}(\mathbf d). \tag{45}

These three cases define exactly one map on every episode. The first case is unambiguous by the clock alternative. The other cases cover all graphs contained in the diagonal, including the empty graph, with the actual residue and actual marker data. In the third case, A d_1\cdots d_g C=T_{s,b}, so all three formulas have the same prescribed linear part. Hence F_e is total and deterministic even on D, and no cancellation or inverse in M has entered its definition.

7.2 The two independently chosen tags

For each x,y\in V we define languages P_x,Q_y by finite unions over tags. A prefix factor is read on [s,k), and a suffix factor on [k,b). These positions describe the tests in their own relative coordinates; they do not give either factor access to the other one.

Every prefix test chooses a tag \alpha, requires x=X(\alpha), chooses a cut of the form specified by that tag, and requires

Every suffix test chooses an independent tag \lambda. It performs the shared-end guard of Lemma 6.3, using all origins k-a, a\in\mathcal H. More explicitly, both end searches \eta,\zeta must be constant over these origins; the suffix must end exactly as prescribed at one fixed reference origin; all the required seed and inspection data must be present. Let q denote the clock anchor so obtained. The suffix requires

The field u(\lambda) is part of the suffix’s tag. The additional tests depend on the tag’s form as follows.

Main tags. A main tag has fields (j,u,A,C,\mathbf d_{-j},X,Y). Its prefix chooses one of the cuts

Using the tag’s fixed index u, it requires the boundary searches f_0^u(t),\ldots,f_{j-1}^u(t) to be present. It checks A and the listed products d_i for i<j against the intervals on its side of the cut. For a\in M, let \mathbf d[j\leftarrow a] denote the tuple formed by inserting a into position j of the tag’s listed entries. The prefix also checks the finite table certificate

The fields used in this certificate are the tag’s fields, not an assumption about the unseen half of the episode.

A suffix with main tag (j,u,A,C,\mathbf d_{-j},X,Y) requires all searches with labels j,\ldots,g, with this fixed u, to be present and to have identical absolute positions at every origin

Using those common positions, it checks d_i for i>j and C against the suffix. Every inspection is required at every origin in (49); an unavailable inspection rejects the suffix instead of discarding that origin. The reading-side separation in the main-cut schedule ensures that these are suffix tests even when the tag is not the tag chosen by a paired prefix.

Periodic tags. A periodic tag has fields (j,u,m_p,X,Y), where 0\le j\le g. Its prefix chooses a cut

checks f_j^u(t)=\bot, and checks m_p=T_{s,k}. A suffix with this tag requires

where b is its own exact endpoint, as required by the shared-end guard. It does not presume that the independently chosen prefix has the same tag.

These rules completely specify P_x and Q_y. All choices of tags, cut offsets, table entries, and origins belong to previously fixed finite sets. In particular, the universal certificate in (48) is a finite Boolean test.

7.3 Correctness for arbitrary successful pairs

We now have the first split interface on all of E, with the same updates F_e reserved for its skipped episodes. To complete the sequence computation, it remains to handle D^*. The defining exceptional predicate, which was an obstruction to the clock construction, will serve as a witness to the origin at an earlier stencil cut. The next section proves that this witness is usually unique across the entire stencil.

8 Recovering the cut on exceptional episodes

Every episode in D satisfies Z(t)\lor A_*(t,q). This is useful information for a suffix: if its prefix ended at k=s+p, the true origin is one of the finitely many candidates k+L-p', p'\in\mathcal P. We will use the exceptional predicate to identify it.

Two issues must be resolved separately. First, false candidate origins must be sparse over all stencil slots, not just those whose metadata might be correct. Second, a suffix proposing an incorrect end must not make the true witness disappear. We first count using actual episode data. We then give a suffix test that obtains precisely enough of those data before it asks for uniqueness, and checks the decoded origin’s end afterward.

8.1 A bounded list of possible clock anchors

Fix a complete episode [s,b) and its actual origin t=s+L. For every pair p,p'\in\mathcal P, set

The distinct-slot differences are distinct as integers and modulo B, are separated from one another by more than 2w_0+2, and satisfy |\delta|\le h. The identical-slot pairs all give t. Evaluate the bounded larger end search \zeta(\tau) on the actual episode.

If one of these larger searches is absent, then every smaller search \eta(\tau) in this collection is absent. Indeed, a marker eligible for a smaller search at any one origin has distance at most \max_u D^0_u+2h from the end-search center at any other origin. The inequality

makes it eligible for that larger search, whatever residue index it has at the latter origin. This would contradict the absent larger search.

In this absence case the seeds at all these origins have short periods. Their starting positions differ by at most 2h; the seed length and marker separation ensure an overlap of at least d_\bullet^2. Lemma 4.2 gives the same two-sided periodic continuation for all seeds. They agree with the episode on their union, so their first subsequent mismatch is the same position q_0. This is the actual episode’s mismatch anchor, because its own smaller search is absent. Define

The second case is used only when a larger search is absent, so the preceding argument always supplies its q_0. In particular Q_t=q.

8.2 Counting every false origin in the stencil

We now count the ordered pairs with p\ne p' for which the translated origin satisfies the exceptional predicate. All marker decisions can be made in one common two-sided extension: the margin construction makes every inspection used below internal to the episode, including the shifted searches.

There are two levels to this estimate. At a fixed anchor Q, distinct displacement residues give distinct width indices, so right-end failures are sparse. The anchor list then permits at most twenty such counts. The estimate includes all ordered pairs; no knowledge of the correct kind was used to obtain it. We can now turn it into a decoder without assuming that a suffix’s proposed endpoint is correct.

8.3 A decoder that also verifies its endpoint

We next give an actual test on a suffix beginning at k. For each slot p'\in\mathcal P form the candidate origin

These are positions relative to the suffix; the origin itself need not be a visible letter. All of the following inspections, including every shifted search needed to evaluate Z and A_*, are mandatory. If a required window is absent from the suffix, the test rejects.

First compute every \zeta(\tau_{p'}). If at least one is absent, require all \eta(\tau_{p'}) to be absent, read every candidate seed, and require the suffix to end exactly according to the end rule at one fixed reference candidate. This includes agreement with that reference seed’s periodic continuation up to its first subsequent mismatch, and exactly L_{\rm tail} letters from that mismatch to the proposed endpoint. Denote its verified mismatch position by q_{\rm ref}. For candidate origins with absent \zeta, use Q_{\tau_{p'}}=q_{\rm ref}. For every candidate with present \zeta, always use Q_{\tau_{p'}}=\zeta(\tau_{p'}). If all the larger searches are present, no reference mismatch test is needed at this step; all these Q’s are bounded search returns.

Now require that exactly one slot p' satisfy

This is uniqueness over all slots, without any restriction to particular kinds or guessed table values. Finally, after decoding this slot, require exact consumption according to the end rule at its candidate origin in all cases, including the case where all larger searches were present.

Figure 2 separates the two anchor roles and records the order of these end checks. The reference guard belongs only to the branch with an absent larger search. The decoded origin’s exact end is checked in both branches.

The two end-search sizes are essential to this test. If a false origin has absent larger search, all the smaller searches, including the true one, are absent and the shared mismatch is already the actual endpoint anchor. Otherwise every candidate clock anchor is bounded data. Thus the decoder never needs to look for an unverified future mismatch beyond a short true episode merely to decide a false origin’s witness.

9 The second split: transmitting a table through the stencil

At a successful early cut, the suffix can now recover the actual stencil slot and hence its metadata. That removes the problem of independently chosen kinds, but an interval crossing the cut is still unreadable. We handle it using the arbitrary-function form of the shift-table lemma.

The suffix first describes the later computation by a table indexed by the monoid product of the entire early region. The table has an entry for every monoid value, not just values realized by prefixes. Composing this table with the product of the early block values yields a total function of the tuple. The shift-table lemma supplies a deterministic affine correction for that function, and one block can then be omitted for each input state.

9.1 A total table computed from later letters

Write b'_*=b'_{g'}, the last fixed stencil boundary, and let e=[s,b)\in D. The homogeneous lift of F_e is the linear map \widehat F_e\colon U\to U, where U=V\oplus\mathbf F_2. If F_e(v)=vL_e+\gamma_e, then

All marker searches, outer boundaries, and end data occur after b'_* by Lemma 6.1. Hence the suffix of the episode starting at b'_*, together with its origin and anchors, determines the following table for every m'\in M.

Set D_b=T_{b'_*,b} and m_b(m')=m'D_b. Define an affine map H_{e,m'}\colon V\to V by the same three cases as F_e:

1. 1.

   If the actual clock graph is the singleton off-diagonal edge \{(\alpha,\lambda)\}, put

   H_{e,m'}(v)=v m_b(m')+Y(\lambda)-X(\alpha)m_b(m').
2. 2.

   Otherwise use u=(q-t)\bmod B. If at least one actual f_j^u(t) is absent, put H_{e,m'}(v)=v m_b(m').

3. 3.

   In the remaining case all these searches are present; write their values as l_0<\cdots<l_g, and put

   A(m')=m'T_{b'_*,l_0},\qquad C=T_{l_g,b},\qquad d_i=T_{l_{i-1},l_i}.

   With f_{A(m'),C} from (43), put

   H_{e,m'}(v)= v f_{A(m'),C}(\mathbf d) +\beta_{f_{A(m'),C}}(\mathbf d).

Define

The hat denotes the homogeneous lift in (59). For every m', including an impossible prefix product, associativity in the third case gives

Thus the affine formula and its linear lift are defined for every entry. Only after the table has been defined do we substitute the actual early product, obtaining

Every letter-dependent quantity here is read after b'_*: marker positions, anchor data, inter-boundary products, and products from b'_* to later positions. The hypothetical value m' is simply a finite algebraic input. The calculation does not search for omitted prefix letters, and it does not query graph languages for sequences of episodes.

Apply exactly the same formulas under a proposed suffix origin once its end rule and all necessary data are available. If a required interval is missing or its endpoints are in the wrong order, reject the entire suffix test. Do not discard that origin, and do not discard individual values of m' from the table. This separates the availability of actual suffix letters from the total algebraic domain of \psi_e. At the true origin all required intervals are available by the margin lemma.

9.2 The affine update on the exceptional domain

For 1\le i\le g' put

For any table \psi\colon M\to\operatorname{End}_{\rm lin}(U), define

Use the fixed shift table \beta_{f'_\psi} supplied by Lemma 2.4 with state space U and dimension g'. On every e\in D define

This is a deterministic total affine map on U. Its linear part is \widehat F_e, because d'_1\cdots d'_{g'}=T_{s,b'_*} and (61) applies.

The kinds in the stencil were chosen to contain all tuples

where 1\le j\le g', x,y\in U, \mathbf d'_{-j}\in M^{g'-1}, and \psi\colon M\to\operatorname{End}_{\rm lin}(U) is arbitrary. The \mu copies of a kind have distinct cut offsets but the same fields. A cut of block j lies strictly inside (b'_{j-1},b'_j), so all listed block products except the omitted jth product can be checked on one side or the other.

For x,y\in U define inner prefix and suffix languages \widetilde P_x,\widetilde Q_y as follows. A prefix chooses a slot p\in\mathcal P and has exactly length p, so its endpoint is k=s+p. If the slot’s kind is (j,x_p,y_p,\mathbf a_{-j},\psi), it requires x_p=x and checks all listed earlier block products a_i=d'_i for i<j. For a\in M, write \mathbf a[j\leftarrow a] for the tuple formed by inserting a into the listed entries at position j. The prefix also checks the finite certificate

The prefix does not try to check the later entries or the table \psi against letters it cannot see.

A suffix beginning at k performs the complete decoder of Lemma 8.3, including its reference end guard when called for and its final decoded-origin end guard. Let p be its decoded slot and use its kind (j,x_p,y_p,\mathbf a_{-j},\psi). At the decoded origin the suffix computes the actual searches, anchors, and all entries of (60). It requires that resulting table equal the slot’s \psi, checks a_i=d'_i for i>j, and requires y_p=y. The comparison of tables is equality on every input m'\in M. Each required interval starts on or after the suffix’s beginning: in particular, the displacement of b'_* from k is the fixed positive offset (b'_*-s)-p, since every stencil slot precedes the last stencil boundary. The margin lemma places all the data for the table after that boundary.

We have now obtained both split constructions with their full all-input guarantees. The inner updates G_e have linear parts \widehat F_e, and the outer updates F_e have linear parts equal to the original monoid action. The remaining task is to express each domain and each individual prefix or suffix test with the claimed height over the original alphabet, and then apply affine recovery and the split identity in this order.

10 Expressions over the original alphabet

Both split interfaces have been proved, including their universal soundness under independent guesses. We have not yet assigned a height to any of their component languages. Finite-state decidability of a test would establish regularity, but would not give the height-one expressions that the split identity needs.

The relevant restriction comes from each component’s own end rule. A marker return gives a bounded end. Otherwise a fixed periodic seed is continued until its first mismatch, followed by a bounded tail. Hence there is only one unbounded repeated word, and finitely many choices of its fixed surrounding words. We first give the exact compilation lemma for that situation, including additional end comparisons made at false origins. This develops the template method of [9, Lemma 8.1 and Proposition 8.2] and [10, Lemma 7.1 and Proposition 7.2] for the present guards.

10.1 Periodic templates and exact-end checks

An exact end check at a fixed candidate origin provides precisely the template cover required by this lemma. If the smaller end search \eta returns a marker, that marker has a bounded offset and the end is bounded. Otherwise its seed is a fixed-length word at a fixed position, with a short-period continuation. Let a be the bounded word from the argument’s own beginning to the seed’s right endpoint. Make finite choices of a, the continuation’s period and phase, and the tail of length L_{\rm tail} starting at the first mismatch. If the mismatch follows i full copies of the period word and one partial copy, put the fixed partial copy and tail into b in (65). Require the first letter of the tail to differ from the periodic continuation. These choices give a finite template cover, with bounded cases handled separately.

This is a statement about the suffix language itself. Its proposed origin is one of finitely many offsets from its own beginning, and its own end check yields the cover whether or not that origin could belong to a successful paired split. There is no ambient-episode assumption here.

Multiple end guards also cause no additional unbounded search. Every guard that uses a mismatch requires that mismatch at the proposed argument end minus L_{\rm tail}. After choosing its seed and period in finite cases, it tests agreement up to that position and disagreement there. The reference guard and decoded-origin guard are therefore both among the comparisons of Lemma 10.1. A missing seed or window rejects the test, rather than making the template argument conditional on inaccessible letters.

10.2 The individual component languages

10.3 Words with no complete episode prefix

Define the final remainder language

Since \neg0=\Sigma^* has height zero, this language has height at most one by Proposition 10.2. We also need to retain the monoid product on a remainder.

10.4 Two splits and the main theorem