Papers for

text algorithm designers

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.

Net occurrences in morphic words precisely counted in new study

Exact Net-Occurrence Counts in Purely Morphic Regular Epistandard Words

Abstract: Finite Fibonacci words have recently been shown to contain exactly three net occurrences---occurrences of repeated factors whose one-letter left and right extensions are unique. This unexpectedly small constant raises a natural question: is it peculiar to the Fibonacci recurrence, or part of a broader morphic phenomenon? We study a family over the alphabet $\{0,1,\ldots,d-1\}$ determined by positive integers $e_0,\ldots,e_{d-1}$. For each letter $a$, let $L_a$ be the morphism that fixes $a$ and maps every other letter $b$ to $ab$; we consider the finite approximants $S_m=μ^m(0)$ generated by $μ=L_0^{e_0}\cdots L_{d-1}^{e_{d-1}}$. These words are the period-aligned finite approximants of the purely morphic regular epistandard family considered here. We prove a sharp dichotomy: for every $m\ge2$, $S_m$ has exactly three net occurrences when $e_{d-1}=1$, and exactly two when $e_{d-1}\ge2$; the initial approximant is also completely classified. The proof combines palindromic prefixes, return-word factorizations, and overlapping net-occurrence covers. As a consequence, when all exponents are equal to one---the standard $d$-bonacci case---every noninitial period-aligned finite approximant has exactly three net occurrences, placing the Fibonacci phenomenon in a wider epistandard framework.

Sat 3 OctFormal Languages and Automata Theory
The gist
Some special sequences of letters, like the famous Fibonacci words, have repeated patterns with unique ways to extend them on both sides. The authors found that the number of these special repeats is always small and follows a clear rule in a wider family of sequences generated by certain letter substitutions. They proved that depending on a parameter, these sequences have exactly two or three such net occurrences, extending the known Fibonacci case to more general ones. Their work uses ideas about palindromes and how parts of the sequence return repeatedly.
Open → 2610.04298v1