{"id":"arxiv/2609.30817","url":"https://arxiv.org/abs/2609.30817","tags":["cs.FL","math.CO"],"score":0,"title":"Quadratic bounds for uncompletable words and matrix mortality","domain":"cs.FL","source":"arxiv","authors":["Rahul Chandelkar","Samrath Singh Chadha"],"reviews":0,"subject":"cs.FL","summary":"Every finite nonempty incomplete uniquely decipherable code with maximum word length $k$ has an uncompletable word of length at most $4k^2-3k$. The bound is independent of the number of codewords and their total length. Deleting a complete codeword cycle gives a finite path-counting identity; Kraft equality then supplies a short word of deficient compressed mass. Cyclic averaging and padding turn it into an uncompletable word. Conditional expectation makes the construction polynomial-time and also decides completeness. First-return words extend the bound to mortal families of nonnegative…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{}}