Block-exchange descent improves minimum insertion runs in word shuffles
Block-exchange descent for insertion: commuting projections and minimum masks
Formal Languages and Automata Theory
Summary
When mixing two fixed words by shuffling, minimizing the number of inserted segments (runs) is important for efficient representations. The authors study how rearranging blocks (block exchanges) can reduce this number step-by-step. They prove that under certain conditions this reduction is predictable and exact, and identify cases where more improvement is possible. Their work includes computer checks for words of various lengths and shows some limits of simple approaches, explaining why alternative methods are necessary.
What this means in practice
- •For text processing engineers: Optimize algorithms that merge or interleave data streams by minimizing inserted segments for better efficiency.
- •For data compression developers: Improve string compression methods by understanding how to reduce and repair insertions in combined sequences.
A theory result. No direct application yet.
Authors
Haobo Ma, Wenlin Zhang, Charles E. Hughes
Abstract
For fixed nonempty words $u,v$, the minimum insertion degree of a shuffle is the least number of inserted-source runs among its representations. We prove that, after a block exchange from a minimum mask of degree $r$, the minimum over masks with commuting source projections is exactly $r-1$; a larger decrease occurs precisely when a noncommuting mask has fewer runs. If either source is unary, every such exchange is exact. We prove an explicit repair for an infinite periodic degree-three family. Computer-assisted results establish first-mask descent through combined length seventeen over every alphabet, degree-three first-mask descent through length thirty, and a uniform repair of all degree-three failures through length thirty, including all further letter identifications. Counterexamples to arbitrary, first, and last minimum-mask choices explain the need for alternative masks. Finally, we prove that minimum iteration depths have no gaps for arbitrary languages. General block-exchange descent and Singleton No-Gap remain open.