WorksComputer Science
Quadratic reset bounds for finite maximal prefix codes
Abstract
Let be a finite maximal prefix code of maximum codeword length . We prove that, whenever the literal decoder of is synchronizing, it has a reset word of length at most . The bound is independent of the alphabet and the number of decoder states. Its main ingredient is a short-detection theorem: a linear observation of the decoder, with terminal weight constant on states of depth , is either identically zero or nonzero on a word of length at most . The proof uses a first-return decomposition in noncommuting variables and cancellation of a highest-degree coefficient. For codes whose codeword lengths are and , we prove the sharper bound and characterize equality. The binary code with the single short word attains this bound for every ; an age representation and a potential on circular arcs give the matching lower bound. Both upper bounds yield polynomial-time constructions in the explicit code size. The mathematical results and the algorithms are formalized in Lean, with polynomial work bounds in a specified binary cost model.
Introduction
A prefix code can be decoded as soon as a complete codeword has been read. If the starting position is unknown, however, different parsings may persist. A reset word removes this uncertainty: after reading it, every possible state of the decoder is the same. For the code , the letter is a reset word. The decoder is either at the root or has just read , and in both cases completes a codeword. For the code , no word resets the decoder, since the two possible depth parities remain different.
We ask how long a shortest reset word can be when all codewords have length at most . This parameter measures the depth of the prefix tree. It can be much smaller than the number of states: a full tree on letters can have internal vertices. Thus even a polynomial bound in the number of states need not give a polynomial bound in .
Throughout, is a finite alphabet with at least two letters, and is a finite nonempty maximal prefix code. Its literal decoder has as states the proper prefixes of the codewords, including . A transition extends the current prefix by one letter, except that completing a codeword returns the decoder to . Maximality makes every transition defined. Write
where the second quantity is used only when a reset word exists.
Theorem 1.1. If and the literal decoder of is synchronizing, then
A reset word satisfying this bound can be constructed in time polynomial in the explicitly listed code and alphabet.
The next result treats all full prefix trees with leaves at two consecutive depths. For and , set
Thus each word at depth is either a leaf in or has all its children as leaves at depth .
Theorem 1.2. The code is maximal, has height , and is synchronizing. Moreover,
with equality if and only if for some nonempty proper subalphabet . A reset word satisfying (1.3) can be constructed in polynomial time in the explicit input size.
The equality cases reduce, by identifying letters, to the following binary family.
Theorem 1.3. For every , the binary code
has reset threshold . The word
is a shortest reset word. Inverse images under surjective letter maps give the same threshold over every finite alphabet with at least two letters.
Let denote the largest reset threshold among synchronizing finite maximal prefix codes of height on a fixed -letter alphabet. There are only finitely many such codes, and Theorem 1.3 ensures that the class is nonempty.
Corollary 1.4. For every and ,
In particular, .
Earlier work. Synchronization of prefix codes is part of the classical theory of codes; Schützenberger’s work [8] studies synchronizing properties of a particular family of prefix codes. The shortest-reset-word problem for finite automata goes back to Černý [4]. Pin [6] develops the approach of bounding the length needed to reduce the image of a subset. The complementary approach enlarges preimages. Rystsov [7] uses this construction with linear algebra and averaging for regular automata; Steinberg [9] gives a general averaging lemma. Our universal bound combines preimage expansion with a word-length estimate specific to prefix trees.
Carpi and D’Alessandro [3] explicitly study synchronization in terms of maximum word length. They relate bounds for synchronizing pairs of complete finite codes to bounds for incompletable words of finite languages. Their result is a conditional route to a quadratic bound in this parameter.
State bounds for prefix-code decoders also follow from results on one-cluster automata: automata in which repeated use of one letter leads every state to the same cycle. Béal, Berlinkov, and Perrin [1] prove a quadratic state bound for this class and apply it to finite prefix codes. Berlinkov, Ferens, Ryzhikov, and Szykuła [2] obtain an reset bound for literal automata of finite prefix codes, where is the number of states. Theorem 1.1 gives a bound directly in the height of a complete literal decoder.
The distinction between the automata matters. Here a reset word must merge every proper-prefix state, without minimizing the decoder. The related theorem on uncompletable words and matrix mortality [5] concerns incomplete codes. A finite maximal prefix code has no uncompletable word: every input can be extended on the right to a concatenation of codewords. Its reset problem therefore requires a different argument.
The proofs. For the general bound, repeated use of one letter first sends the decoder into a cycle of at most states. We then construct a reset word backwards, enlarging the preimage of a chosen state. Cyclic averaging supplies an enlargement as soon as some short word changes a preimage’s cardinality. § 3 carries out this construction using the short-detection theorem proved in § 4. The latter replaces a bound depending on the dimension of a state space by one depending only on tree depth.
For consecutive depths, the next codeword boundary is a nondecreasing function of the current boundary. § 5 uses this order to advance the least remaining offset between two parsings. A closure property of the short codewords describes the only obstruction to the simplest advance. § 6 proves the exact binary lower bound by assigning a potential to sets of possible ages. § 7 gives the algorithms. Appendix § 9 contains the arc calculations, and Appendix § 10 describes the formal verification.
The literal decoder
Words act on states on the right. Thus . For a set of states, write . A word is a reset word if .
Let
The prefix tree of a finite nonempty prefix code is full if and only if the code is maximal. Indeed, a missing child of an internal vertex could be added as a codeword. Conversely, in a full finite tree, every word either meets a leaf or ends at a vertex having a leaf below it, so it is comparable with a codeword. Consequently, for and , exactly one of and holds, and
Figure 1 shows the passage from the tree to the decoder.

Figure 1. The code . Rectangles are leaves. Each transition into a leaf becomes a return to ; the letter sends both decoder states to .
Lemma 2.1. Every state has depth at most . Starting from a state , every input of length completes a codeword. If at least one completion occurs while reading , the final state is the suffix of after the last completion and has length at most .
Proof. A path of length from that avoids all leaves would end at an internal vertex of depth , which is impossible. At the last completion the decoder returns to . Every subsequent letter extends the current prefix, since otherwise a later completion would occur. Those letters are therefore exactly the final state.
Lemma 2.2. If , every state in is a suffix of , and . If begins with a codeword, then .
Proof. Every nonroot initial state completes a codeword during , by Lemma 2.1. The root either does the same or ends at the state . Thus all outputs are suffixes of , one for each possible length in . If begins with a codeword, every initial state completes at least once, so all output lengths are at most .
Reading from the root gives a unique factorization of any input into complete codewords followed by a proper prefix. This follows directly from (4): the returns to mark the codeword boundaries. In particular, extending the final prefix to a leaf extends the input to a word of .
If all leaves have depth , fullness gives . Every letter then increases depth by one modulo , so states of different depths cannot merge. For , a synchronizing code must therefore contain a shorter leaf. At height one, and the decoder has only the state ; its reset threshold is zero.
A cycle reached by one repeated letter
Fix . Following the -path from the root meets a unique leaf , where . The states
form a cycle under . Identify with , and let be the rotation . Set and define
The map takes into . The root already lies on the cycle, and every other state completes a codeword within letters, after which all remaining letters are 's.
For later use, record the composition rules
The first follows by writing the input as . For the second, interchange the adjacent powers and and use the action of on . In particular, is a permutation.
A universal bound from preimage expansion
We first explain how the decoder's height enters the reset construction. The only algebraic input is the following theorem, whose proof occupies § 4.
Theorem 3.1 (Short detection). Let be a field and . Suppose , with constant on the states of depth . Put
If is not identically zero, then for some .
To use this statement, take the cycle and the maps from (5). We need to enlarge the preimage of any proper nonempty subset of . It is enough first to find a word for which . Call such a word unbalancing for .
Lemma 3.2. Assume that the decoder is synchronizing and . For every , there is a word of length at most such that
Proof. Work over and set
A state of depth returns to on its next letter. Thus every such state has the same image under , and satisfies the hypothesis of Theorem 3.1. Its observation is
If resets the decoder, is constant. Its preimage of has size either or , so . Short detection gives the required .
Lemma 3.3 (Cyclic averaging). For any map and subset ,
If , some satisfies .
Proof. Each point belongs to exactly of the rotations of . Counting over proves (7). The summands have average . If one differs from that average, one must exceed it.
This is the averaging principle in the form needed here [9]. In view of (6), the rotation is realized by appending at most letters . The first step can avoid this cost: a map that changes a singleton’s preimage size is not a permutation, and hence has some fiber of size at least two.
Proposition 3.4. Suppose that and every proper nonempty is unbalanced by some word of length at most . Then the decoder has a reset word of length at most
Proof. Choose an unbalancing word for a singleton. Since is not a permutation, choose with at least two preimages, and put
While , choose unbalancing . Lemma 3.3 gives such that, with ,
These sets need not be nested; only their cardinalities increase. After steps, .
The word
resets the decoder. Its initial power of sends into . The rest acts there as , which sends into . Notice that the maps are applied in the reverse order to their construction.
There are copies of . Also and for . Hence

Figure 2. The reset word reads from left to right. Its construction runs backwards: each is the full preimage of under , and has larger cardinality.
Proof of Theorem 1.1. If , already resets . Otherwise Lemma 3.2 permits in Proposition 3.4, giving
For , the product on the right increases with : both factors are nonnegative and increasing. Substituting gives (1). The algorithmic assertion is proved in Section 7. □
Corollary 3.5. If the decoder is synchronizing, , and some pure-letter codeword satisfies , then .
Proof. The case is immediate. Otherwise put and . The preceding estimate gives
where the last inequality uses . □
Short detection from the height of the tree
We now prove Theorem 3.1. A first-return decomposition expresses every decoder observation using four word polynomials of degrees controlled by . The difficulty is that these polynomials do not commute. We retain word order by embedding the free algebra in a division ring, where a finite linear system supplies a common right denominator. One further cancellation saves a degree and gives .
Keeping the order of letters
Write for the free associative algebra on . Its elements are finite -linear combinations of words, and multiplication is concatenation. Its completion consists of all formal word series. Products are well-defined because a word has only finitely many factorizations into two words.
Lemma 4.1. There is a division ring , with central, and an injective -algebra homomorphism . If is the homogeneous component of degree of a word series , then
is an injective multiplicative map into , where is central. Its order is the least length of a word with nonzero coefficient in .
Proof. Let be a rational function field in commuting algebraically independent variables. The assignment defines an automorphism of fixing . Form the skew Laurent-series ring
Its series have exponents bounded below. Each coefficient of a product is therefore a finite sum. Every nonzero series has an invertible lowest term . Factoring out that term leaves with of positive order, whose inverse is the well-defined series . Thus is a division ring, and is central in it.
Send to . Then
Distinct words of the same length give distinct monomials in the position-indexed variables. These monomials are linearly independent over ; different lengths have different powers of . This proves injectivity. The additional variable records homogeneous degree. Multiplicativity follows by homogeneous convolution, and injectivity and the order assertion follow degree by degree.
Lemma 4.2 (Common right denominator). Let , with , , and . There are polynomials such that
Proof. Write and . Equating coefficients in gives at most homogeneous equations in unknowns. This is a linear system over the right vector space : all fixed coefficients multiply the unknowns on the left. It has a nonzero solution. If , then , forcing , since the product of the leading coefficients of two nonzero polynomials is nonzero. Hence .
The side of multiplication in (10) is essential. It gives with precisely the order needed below.
The first completion
For each , define
The empty suffix contributes to . A word read from either completes no codeword or has a unique first completion. In the first case it contributes to . In the second it consists of a suffix counted by , followed by an input read from the root. Hence
Set , , and . Since has no constant term, exists as a formal word series. Taking in (11) gives . Thus the observation series is
where
The tree gives the degree bounds
For example, a suffix in has length at most , and uses only nonroot states. A suffix in has length at most .
Cancellation of the highest coefficient
Proof of Theorem 3.1. Use Lemma 4.1 to encode the polynomials and series by a central variable , retaining their names. Lemma 4.2 gives
The constant coefficient of is 1, so it is invertible in . Multiplying (12) on the right by gives
By (13), . We show that its coefficient of degree vanishes. Let be the common value of at depth . Before encoding, put
There is a leaf at depth , so . Every child of a state counted by is a leaf. Consequently the highest homogeneous components satisfy
The last two equalities use the same paths: a nonroot initial state can contribute at those degrees only if it has depth one. The relevant path ends at a deepest internal vertex for , and takes one additional letter for . This also covers , when the path contributing to is empty.
Now read (15) as equalities in . The coefficient of degree in is
Since is central, cancelling on the left yields
Therefore the coefficient of degree in is
We have proved .
If , then . Orders of nonzero power series over a division ring add, because the product of their first nonzero coefficients is nonzero. Hence
As , the first nonzero homogeneous part of has degree at most . Injectivity of the encoding gives an actual word of that length with .
The terminal-depth condition is used exactly in (15). It makes both highest terminal coefficients scalar multiples of the corresponding path sums, allowing the cancellation. The conclusion concerns a linear observation; the extra compression and rotation costs in § 3 are needed to turn it into a reset word.
Codes with two consecutive lengths
Fix and . The tree of in (2) is full: every word of length either belongs to or has all its children as leaves. Nonemptiness and properness ensure that both lengths and occur.
The direct construction in this section uses a property special to these two lengths. Along a fixed input, later codeword boundaries cannot have earlier next boundaries. We first describe this order and then show how to advance all surviving offsets between two parsings.
Order of parsing boundaries
Consider an infinite input . At a possible boundary , set
The codeword starting there has length , so its next boundary is
Since
the map and all its iterates are nondecreasing. Let be the boundaries of a reference parsing, so . If is an alternative boundary, then
Equality at either endpoint means that the two parsings meet and agree thereafter. Otherwise the alternative boundary remains inside the next reference word. If its offset is , the current reference word has length , and the alternative word has length , the next offset is
In particular, when the reference word is short, the offset stays fixed or increases by one.

Figure 3. For lengths and , monotonicity keeps an alternative boundary between the next two reference boundaries. A boundary reaching either endpoint has joined the reference parsing.
When every splice remains short
Use zero-based slices: is the suffix of a word after position , and is its prefix of length . For , call closed at x if
This is precisely the situation in which every length- window at offset across two short reference words is itself short.
Lemma 5.1. If is closed at and , then
for a nonempty proper subset . Conversely, such a product is closed at every offset divisible by .
Proof. Taking in (18) shows that rotation by maps into itself. Since is finite, it is invariant under this rotation and its inverse. The rotations generated by modulo are exactly the multiples of , so rotation by also preserves .
Rotating the splice in (18) back by gives
Thus the first coordinates of one word can be copied independently into another word of . Say that a set of coordinates is replaceable if every word formed from one member of on and another on its complement still belongs to . Replaceable sets are closed under complement by interchanging the two words. They are closed under intersection as well: first copy into of , then copy the resulting word into of a fresh copy of . The final word uses exactly on .
Partition the coordinates into consecutive blocks of length , and put . The first blocks are replaceable. Rotation invariance makes every cyclic interval of blocks replaceable. These intervals separate distinct blocks: the incidence patterns of two distinct positions in all proper, nonempty cyclic intervals of a fixed length are different. One way to see this is that the indicator of a single proper cyclic interval has exactly one change from 0 to 1; it cannot be invariant under a nonzero rotation. Therefore the Boolean algebra generated by the intervals contains each individual block. Each block is replaceable.
Let be the projection of onto block . Replacing one block at a time shows that all choices from the projections are independent, so . Rotation by permutes the blocks and preserves , forcing all to be the same set . Since is nonempty and proper, so is . The converse follows because a splice at a multiple of joins whole blocks belonging to .
Advancing the least remaining offset
At the end of a round, the last reference word is a short word . Any parsing that has not met the reference has its most recent boundary at an interior offset of . We append two codewords, the last of which is again short, and follow these boundaries through two applications of .
Lemma 5.2. Suppose the least surviving offset in is , where . There are two codewords, the second short, whose concatenation has length at most and leaves every surviving offset at least . If is not closed at , the length is at most .
Proof. Suppose first that closure fails. Choose with , and append . In moving from to , an offset either increases or stays fixed, by (17). If it increases, the next transition cannot decrease it, since is short. If it stays fixed, the window at offset across lies outside , so the alternative word has length and its offset increases at the next transition. An endpoint is removed as soon as it meets the reference. Monotonicity of gives the same lower bound for all larger surviving offsets. The cost is .
Now suppose closure holds. By Lemma 5.1, write
Choose , , and . Form
Its length is , and its first length- block is , so its length- prefix is outside . Thus . Append followed by any . Place , , and on the half-open intervals , , and , respectively. The boundary at sees the length- window
It contains the forbidden block at an aligned block position, and hence lies outside . The alternative word is long, ending at inside . Its next window is
which again contains an aligned forbidden block. The next alternative word is long too, and ends at , at offset in . If , it meets the right endpoint of . Monotonicity of controls the larger offsets. The appended length is .

Figure 4. The long–short round. The two copies of force two long alternative codewords. Their boundaries advance from offset in to offset in . Positions are schematic; the displayed coordinates give the exact lengths.
Proof of the upper bound in Theorem 1.2. If , any letter in resets the decoder, and the threshold is one because is proper and the decoder has a nonroot state.
Let . Begin with any . Every initial state completes a codeword during these letters, so Lemma 2.1 shows that every output is a suffix of of length at most . The root’s parsing ends at the root and serves as the reference. Every other output corresponds to a boundary at an interior offset in .
Apply Lemma 5.2 to the least surviving offset. Its conclusion raises that offset by at least one and leaves the last reference word short. Repeat until no offset remains. This takes at most rounds, since the possible offsets are . At each round end, an alternative parsing either has met the reference or has its last boundary in the last short word: its next word has length at least , so it cannot complete again strictly inside that word. Thus the same representation applies at every round. When all alternatives have met the reference, the input resets to .
The total length is at most
All windows used in the construction lie in the chosen words. An arbitrary infinite continuation used to define cannot affect them. Polynomial-time implementation is discussed in § 7.
Equality and changes of alphabet
Lemma 5.3. Let be a surjective letter map, let be a finite maximal prefix code, and set . Then is a finite maximal prefix code. A word resets its literal decoder if and only if resets the decoder of . Consequently the thresholds agree whenever the decoders synchronize.
Proof. The state set is , and the induced map is onto and respects transitions. Prefix-freeness and fullness are preserved, so is a finite maximal prefix code. A reset word projects to a reset word.
Conversely, if resets, all states in have the same image, and thus the same length . If one initial state completes a codeword while reading , Lemma 2.1 gives . Any thread that completes none would end at length , a contradiction. Hence all threads complete, and all outputs are the same length- suffix of .
If no thread completes, all output lengths are . They cannot be equal when contains both the root and a nonroot state. The remaining case is immediate. This proves the converse. Every word over has a lift of the same length, giving equality of thresholds.
Proof of the equality assertion in Theorem 1.2. Suppose and is not a subalphabet power. Then is not closed at : otherwise Lemma 5.1, with , would give .
If the construction uses rounds, their least offsets must be . The last round costs at most , saving one letter from the bound. If it uses fewer rounds, the saving is larger. Thus
Conversely, if , send the letters of to and all remaining letters to . Then is the inverse image of . Lemma 5.3 and Theorem 1.3, proved in the next section, give . For , every nonempty proper is itself a subalphabet, and the threshold is one.
An exact extremal family
Put and consider
The states of its decoder are
Every word of length less than is an internal vertex; at depth , only is a leaf. Thus
A reset word of length
Lemma 6.1. The word resets to .
Proof. Let . Reading fixes each state of . From a state containing , of length , the first letters complete a long codeword and the remaining letters leave . Hence .
For , reading from completes a long word after letters and leaves . Reading from then leaves if , and leaves if . The block therefore acts on by
After copies, every state reaches . The length is .
For the converse, a reset word may end at any state. We must bound all such words, not just those returning to . Once the states are suffixes of a common input, their lengths determine them. We use these lengths to follow every possible reset word.
Ages and the first short completion
Call the length of a suffix state its age. Ages lie in . On this set define
On the smaller circle , let .
Suppose the current states are suffixes of a common word of length at least . Let be the trailing run of a’s, capped at . A letter acts on ages by and sets the counter to zero. A letter acts by if the prior counter is at most , and by if it is at least . In the latter case the counter becomes . Call such an a special letter.
These rules are exact. Age always returns to zero on the next letter. Age returns to zero on exactly when its suffix is , which is equivalent to the common input having at least trailing a’s. Every other transition increases age by one. In each case the new state is the suffix of the enlarged input of the new age. Distinct ages represent distinct states.
Two initial state sets fit this description:
For , take the common context , all small-circle ages, and counter . For , take the context , all big-circle ages, and counter zero. These contexts represent the sets; they are not charged as part of a subsequent input.
Let be the minimum length needed to send to a singleton. It is finite by Lemma 6.1.
Lemma 6.2. The reset threshold satisfies .
Proof. Since , we have . Conversely, let reset . It also resets . Until the first special letter, the age action on is a permutation of all ages. A special letter must therefore occur.
Let be the number of letters consumed up to and including that first special letter. Because the initial counter is zero, the consumed prefix ends with , so . Immediately after this letter, the age set is exactly and the counter is . The actual states are the corresponding suffixes of , namely . The remaining suffix of must synchronize , and has length at least . Thus .
For , and , so the threshold is one. Assume from now on that .
Excursions away from the small circle
After a special letter the ages lie on the small circle and the counter equals . Further special letters are a’s, acting as . To leave such a run requires a . Before the next special letter there must be ordinary a’s after the last . Thus the intervening block of nonspecial letters starts with , ends with , and has length .
Suppose this block is followed by special letters. Put . Let include the small circle in the big one, and let fix and send to . Since , the whole excursion acts on small-circle ages as
For , define
The only nontrivial fiber of is , which maps to zero. Its image omits . Splitting according to whether crosses or gives the following three possibilities:
Figure 5. The slip on five ages. The ages 1 and 2 merge at 0, and age 3 is omitted. The target circle is cut immediately after 3 and displayed in the order 4, 0, 1, 2, 3. This makes the increasing lift used in Appendix § 9 visible.
| Excursion map | Necessary length | |
| 0 | ||
Table 6.
For completeness, in the middle range put . If , the big-circle age is at most and the first special letter sends it to . If or , it sends it to zero. If , reduction modulo occurs before applying , and the result is . These are exactly (21). The remaining letters rotate. The cases follow directly from and .
Assign cost 1 to and cost to . Each excursion can be replaced by these operations at no greater cost. The first two rows require only or rotations. In the third row,
Here and imply .
An initial run of special letters is already a sequence of rotations. A final unfinished block of nonspecial letters acts by a power of , so it cannot change cardinality and can be discarded when testing synchronization. Consequently, if is the minimum total cost of rotations and slips sending to a singleton, then
We only need this direction: allowing additional sequences of slips can lower the minimum, which is harmless for (23).
A potential on circular arcs
Cardinality alone does not give the sharp cost: slips at different positions have different prices. We also keep track of where a shortest covering arc starts.
For and , let
For , this range selects a unique integer representative of the starting point of each arc. For , all starts describe the full circle, and the least value occurs at .
For a nonempty subset of the circle, put
In particular,
Lemma 6.3. An arc of smaller size has smaller than every arc of larger size. For , the minimum in (24) selects a unique covering arc of minimum size. Its size is at most , and both its endpoints lie in .
Proof. At size , the maximum possible value is . The minimum at size is , larger by . Iterating gives the first assertion. A proper subset is covered by an arc of size , obtained by omitting a point outside it. Among the minimum-size covers, different canonical starts give different potentials, so one is selected uniquely. If an endpoint were absent from , deleting it would give a smaller cover. The only possible reduction to a singleton would contradict .
Write for this selected arc. The word “selected” matters: a set may have several shortest covering arcs, and resolves that choice.
Lemma 6.4. For and ,
Proof. For rotation, the full circle is immediate. Otherwise reverse-rotate . If , its canonical start decreases by one and its potential increases by one. At , the new canonical start is , and the potential changes by . The reverse-rotated arc covers , proving (26).
If is a singleton, the only possible is . This is the arc and has potential , including the case , of the full circle. Thus (27) holds with equality.
Suppose . Its image omits , so its selected covering arc is proper. Neither endpoint is , by Lemma 6.3. The preimage is a circular arc of size at least two, and
The calculation is given in Appendix § 9. It uses the increasing lift of obtained by cutting the target circle at its omitted point. An interval avoiding that point lifts to an interval; one crossing it has preimage formed by the two end intervals, which together give a wrapping arc. Since covers , inequality (28) proves (27).
Proof of Theorem 1.3. The case follows from Lemma 6.2. For , take any sequence of rotations and slips from the full small circle to its first singleton. At each step Lemma 6.4 bounds the decrease of by the cost of that step. Summing gives total cost at least
By (23) and Lemma 6.2,
Lemma 6.1 gives equality. For any alphabet with at least two letters, a surjective map onto and Lemma 5.3 transfer the exact threshold.
Proof of Corollary 1.4. Theorem 1.1 gives the upper bound. The lifted binary family gives the lower bound at every weight over each fixed alphabet. Both are quadratic with positive leading coefficient.
Constructing the reset words
Both proofs give algorithms on an explicit prefix tree. The short-detection proof uses infinite series only to establish the length bound; the algorithm itself uses finite rational linear algebra.
A basis of short observations
Let , , and . For each letter , let be the deterministic transition matrix, with when . Set for , and let be the row vector that is one on and zero elsewhere. For , define the column vector
Then
We can test all words of length at most by testing a basis of their row vectors.
Lemma 7.1. There is an algorithm that constructs at most words such that the rows , , form a basis of
It tests at most candidate rows for independence.
Proof. Start with , represented by . Process retained rows in nondecreasing word length. For each retained word with , test the rows represented by , , retaining just those independent of the rows already retained. At most rows can be retained, and each has at most tested extensions.
To check that discarding a row loses nothing, induct on length. Suppose every row represented by a word of length at most lies in the span of retained rows whose represented lengths are at most . Multiplying such an expression by expresses each length- row in terms of extensions of those retained rows. These extensions are tested by depth and either retained or expressed in previously retained rows of at most that depth. This proves the assertion up to the cutoff . □
Theorem 7.2. Given an explicitly listed finite maximal prefix code of height and its alphabet, one can decide synchronization and, when it holds, construct a reset word of length at most in polynomial bit complexity.
Proof. Construct the tree and transition table, choose a letter , and find its pure leaf . If , output . Otherwise compute the basis of Lemma 7.1 once.
For each set encountered in the preimage construction, evaluate for . If all values vanish, then (29) vanishes for every word of length at most . Theorem 3.1 makes it vanish for all words. A reset word would give a nonzero value, as in Lemma 3.2, so this certifies nonsynchronization.
Otherwise a basis word supplies the required short unbalancing word. For the first singleton test, choose a fiber of size at least two. At later steps, test the rotations to find a larger preimage. There are at most expansions. If the procedure does not return a nonsynchronization certificate, it outputs (9). Proposition 3.4 proves that this word resets and satisfies the length bound. Thus both answers are sound, and the procedure terminates on every input.
For the bit bound, entries of count the images of starting states, so they are integers between 0 and . There are at most candidate rows of dimension . Rational Gaussian elimination can be implemented with intermediate coordinates given by ratios of minors of the integer input matrix. A minor of order has absolute value at most by Hadamard’s inequality. Numerators and denominators therefore have bits; the same polynomial estimate applies to the actual residual and normalized pivot coordinates. Integer arithmetic and reduction of fractions then take polynomial time. The number of arithmetic operations, row evaluations, rotations, and transition simulations is polynomial in , , . The output has letters. All these parameters are bounded by the explicit alphabet and code listing size.
At height one the decoder is a singleton and the algorithm returns . The procedure constructs a reset word within the bound; it does not compute a shortest reset word in general.
The consecutive-depth construction
Lemma 5.2 can be implemented directly. Test closure at by examining the pairs . A failed test supplies the short–short round. If closure holds, compute and project onto a block of length to obtain . Choose and enumerate to find . The long–short round is then given by (19).
These searches are polynomial in the input size. Indeed,
since every word of length contributes either one short leaf or long leaves. There are at most rounds, and all decoder images and offsets can be updated by direct simulation.
An equivalent implementation avoids computing : enumerate pairs and test whether the pair advances all currently eligible offsets. The forcing lemma guarantees a successful pair of total length at most . When closure fails, short–short pairs already suffice. This is the finite-search formulation used by the verified implementation.
The remaining gap
Does every synchronizing finite maximal prefix code of height satisfy
The consecutive-depth theorem and the binary family show that this would be the exact bound over every alphabet with at least two letters. Corollary 3.5 also proves it when a sufficiently short pure-letter codeword is present, under the synchronization hypothesis.
The two upper-bound proofs indicate where the gap arises. In the general construction, each preimage enlargement requires a short unbalancing word, a return to the pure-letter cycle, and possibly a rotation. In the consecutive-depth construction, order along the input lets one control all alternative parsings by the least surviving offset. This avoids the repeated cycle-compression cost.
That order need not hold in an arbitrary prefix tree. If the next codeword length at position is , then
which can be negative. Thus the proof for two lengths cannot simply be applied after replacing the other lengths by consecutive ones. A sharper general bound would need either a cheaper preimage construction or a way to control parsings without this monotonicity.
Example 8.1. For , the extremal code is
and is a shortest reset word, of length seven. In contrast, gives
Here is not a subalphabet square, so Theorem 1.2 gives the strict upper bound .
Preimages of arcs under a slip
We prove (28), completing Lemma 6.4. Fix and let . Let be a proper arc with , neither endpoint equal to . The increasing lift
is defined by
It takes every value in once except zero, which has preimage . Reduction modulo gives . The single missing residue is .
The arc avoids . There is a unique lift of . Its preimage is an ordinary integer interval. The three possible positions of this interval relative to zero give Table 1. All displayed starts of are canonical. In the first row the start of is ; in the second it is also ; in the third it is . Substitution into gives the stated differences. If the first row gives , the preimage is the full circle and its displayed start is necessarily zero.
| Position of the lifted interval | ||
Table 1. The preimage of an arc avoiding the omitted point. The first case gains one point by containing the doubled fiber.
The arc contains . Since is not an endpoint, write
The part after lifts to , and the part before lifts to . Their preimages are an initial and a final integer interval in . The gap has a nonempty preimage because , so their union is a proper wrapping arc.
There are three cases, according to which lifted interval contains zero; see Table 2. The first two cannot occur together: and would imply . The implications in the first column follow from . The canonical start of is in the first row and in the other two. The displayed starts of are canonical as well. These values give the potential differences in the table.
| Position relative to the doubled fiber | ||
| (so ) | ||
| (so ) | ||
| , |
Table 2. The preimage of an arc crossing the omitted point. In the last case the arc loses the point and contains no doubled fiber, so its size decreases by one.
The preimage has size at least two in every case. In the last row this follows from . All six differences are at most . This proves (28).
Formal verification and reproducibility
The Lean development uses proper-prefix states and proves all four main results, including short detection, the parsing and forcing lemmas, the age reduction, and the arc-potential inequality. The main results are collected in HeightSync.Manuscript:
| Paper statement | Lean declaration |
| Theorem 1.1 | universal |
| Theorem 1.2 | consecutive |
| Theorem 1.3 | binary |
| Corollary 1.4 | growth |
Table 3.
The complete statement index is provided in MANUSCRIPT_COVERAGE.md. Short detection is formalized over arbitrary fields. For the embedding lemma, the development constructs a division ring through skew-polynomial Ore fractions; the Laurent-series construction in Lemma 4.1 is a direct alternative proof of the same embedding statement.
Both reset constructions have executable implementations with correctness proofs. The declarations VerifiedAlgorithms.universal and VerifiedAlgorithms.sharp also bound their work by fixed polynomials in the explicit input size. The cost model charges binary integer arithmetic, rational normalization, and finite list and table operations. Arithmetic bounds apply to the actual intermediate values and executed elimination stages; list and table operations receive specified conservative bulk charges. These are bounds in that model, not theorems about Lean’s compiler or elapsed machine time. The definitions and scope are documented in COST_MODEL.md.
The checked source uses Lean 4.28.0 and mathlib v4.28.0. The verification run builds all 97 source modules, checks the manuscript index against the compiled environment, runs executable checks, and audits the dependencies of all 2,970 declarations in the project namespace. The audit permits only the standard logical axioms propext, Classical.choice, and Quot.sound; there are no admitted proofs or additional axioms. From the formalization directory, the full check is
python3 checks/verify.py
The complete Lean sources, verification report, source hashes, and axiom log are included as ancillary files with the arXiv submission.
OpenAI Codex assisted with the exposition, figures, and Lean formalization.
References
- [1]M.-P. Béal, M. V. Berlinkov, and D. Perrin, A quadratic upper bound on the size of a synchronizing word in one-cluster automata, International Journal of Foundations of Computer Science 22(2) (2011), 277–288. doi:10.1142/S0129054111008039.DOI
- [2]M. V. Berlinkov, R. Ferens, A. Ryzhikov, and M. Szykula, Synchronization of strongly connected partial DFAs and prefix codes, Discrete Mathematics & Theoretical Computer Science 28(2), article 34 (2026). doi:10.46298/dmtcs.16465.DOI
- [3]A. Carpi and F. D’Alessandro, On incomplete and synchronizing finite sets, Theoretical Computer Science 664 (2017), 67–77. doi:10.1016/j.tcs.2015.08.042.
- [4]J. Černý, Poznámka k homogénnym experimentom s konečnými automatmi, Matematicko-fyzikálny časopis 14(3) (1964), 208–216. DML-CZ:126647.
- [5]R. Chandelkar and S. S. Chadha, Quadratic bounds for uncompletable words and matrix mortality, arXiv:2609.30817v2 (2026).arxiv.org/abs/2609.30817
- [6]J.-É. Pin, On two combinatorial problems arising from automata theory, Annals of Discrete Mathematics 17 (1983), 535–548. doi:10.1016/S0304-0208(08)73432-7.DOI
- [7]I. K. Rystsov, Quasioptimal bound for the length of reset words for regular automata, Acta Cybernetica 12(2) (1995), 145–152. Szeged repository.
- [8]M. P. Schützenberger, On the synchronizing properties of certain prefix codes, Information and Control 7(1) (1964), 23–36. doi:10.1016/S0019-9958(64)90232-3.DOI
- [9]B. Steinberg, The averaging trick and the Černý conjecture, International Journal of Foundations of Computer Science 22(7) (2011), 1697–1706. doi:10.1142/S0129054111008970.DOI
