Papers for

text algorithms developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Binary word patterns precisely identified by letter counts and smoothness

Shuffle Squares in Differentiable Words

Abstract: Experiments on binary run-length differentiability lead to sharp computer-assisted criteria for shuffle squares. Every $C^3$-word of length greater than $16$ is a shuffle square exactly when both letter multiplicities are even. All $34$ nonempty even-Parikh exceptions are smooth and persist in every higher differentiability class. For $C^2$ the sharp threshold is $48$, with $212$ nonempty exceptions. At level $C^1$ no global parity threshold exists, but every even-Parikh non-shuffle-square of length at least $36$ has proper nonempty shuffle-square prefixes and suffixes. Exactly $230$ nonempty even-Parikh $C^1$-words have no nonempty shuffle-square prefix. The full tree avoiding such prefixes eventually consists of $422$ periodic rays. Consequently, a nonempty Kolakoski prefix is a shuffle square exactly when both multiplicities are even, apart from lengths $4$ and $8$. We also characterize classes of morphisms reflecting shuffle squares. For doubly binary words, we determine the exact deletion distance and largest twins, and prove sharp bounds for single local repairs. Exact recurrences, residual-state checks, and separate Python programs make the finite computations reproducible.

Tue 6 OctFormal Languages and Automata Theory
The gist
This paper finds exact rules to tell when a string made of two letters can be formed by mixing together two copies of another string (called shuffle squares). The authors show that for very smooth patterns, the only requirement is that the count of each letter is even. For less smooth patterns, some special exceptions exist, but these can be clearly described and checked by a computer. They also explain when parts of these strings can be broken down into smaller shuffle squares. The work includes exact formulas and computer programs to verify their findings.
Open → 2610.07828v1