CS Paper Radar

Exact Net-Occurrence Counts in Purely Morphic Regular Epistandard Words

Simone Faro, Arianna Pavone

cs.FL ·submitted 2026-10-03 05:16 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Boxes in Infinite Words: Complexity, Automata, and Point Modules

cs.FL math.LOmath.RA ·2026-11-16 ·Jason Bell
theory similarity 0.58
Abstract · 23 pages

Motivated by the geometry of point modules over monomial algebras, we introduce a box-counting function associated to a right-infinite word over a finite alphabet. An extendable box is a family of finite words obtained by choosing letters independently at each position, subject to the condition that all choices admit a common infinite right continuation in the associated subshift. We prove several results for these functions for words of linearly bounded complexity. For $k$-automatic words, we show using techniques from first-order logic that the total box-counting function is $k$-regular. Finally, we apply our results to prove eventual affine growth of the number of positive-dimensional irreducible components in finite projections of point-module spaces associated to semiprime monomial algebras of at most quadratic growth.

0.35

Shuffle squares in smooth binary words and the Kolakoski sequence

cs.FL math.CO ·2026-10-01 ·Kory Kilpatrick
similarity 0.56
Abstract · Includes an exact finite certificate and standalone Python verifier. Research, computation, and writing performed by GPT-5.6 Sol and GPT-6-A…

A binary word is a shuffle square if its positions can be partitioned into two identical subsequences. A finite word over $\{1,2\}$ is smooth if repeated finite run-length differentiation remains binary until the empty word is reached. This paper proves that every smooth binary word in which both letters have even multiplicity is a shuffle square once its length is at least $18$. There are exactly $34$ exceptions, all of length at most $16$. The infinite part of the proof is a parity-return atom induction: a smooth even-Parikh word factors uniquely into smooth parity atoms, and every such atom has length at most $8$. A finite, independently checkable certificate handles lengths $18$ through $40$. As a consequence, a nonempty prefix of the classical Kolakoski sequence is a shuffle square if and only if both symbols occur an even number of times and its length is not $4$ or $8$. There are infinitely many such prefixes. In fact, the entire infinite Kolakoski sequence can be partitioned into two identical infinite subsequences with monochromatic blocks of uniformly bounded length.

0.54

Subsequence Analysis Problems for Binary Parikh Matrices

cs.FL cs.CC ·2026-10-05 ·Szilárd Zsolt Fazekas, Xinhao Huang, Robert Mercaş
publishedtheory similarity 0.56
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

The universality index corresponding to a word is the largest integer k such that every word of length k over the given alphabet occurs in it as a subsequence. Relative to languages this notion can be investigated with respect to both existential and universal quantifiers, with the former corresponding to the existence of a word in the language with universality index at least k, while the latter considers the index across all words that the language contains. In this work we study the existential (exists-universality) and universal (forall-universality) subsequence universality (as introduced in [Adamson et al., ISAAC 2023]) for binary languages consisting of all words with a fixed number of letters a, letters b, and subsequences ab. We prove that both exists- and forall-universality admit exact arithmetic characterizations for these languages. Extending the above notions, we end the paper by initiating the analysis of the probability of a fixed word occurring as subsequence of the words in such a language. To this end, we prove that, for every fixed pattern word w and an error tolerance, given as input the subsequence counts describing a language, the ratio of words in the language having the pattern w as a subsequence admits an additive approximation scheme that is polynomial-time in the binary encoding of the input counts.

0.49

Jumbled Simon's Equivalence and Embeddings

cs.FL cs.DS ·2026-10-13 ·Pamela Fleischmann, Annika Huch, Sungmin Kim, Tore Koß, Emil Wiards
similarity 0.55
Abstract

\emph{Jumbled scattered factors} are a generalisation of scattered factors (or subsequences) where a jumbled scattered factor is obtained from another word by deleting and rearranging letters. For limiting the number of rearrangements, we distinguish $\ell$-jumbled scattered factors where $\ell$ limits the number of letters that may occur rearranged. For instance, $\mathtt{car}$, $\mathtt{start}$, $\mathtt{rat}, \mathtt{cat}$ are jumbled scattered factors of $\mathtt{abstract}$ even though $\mathtt{car}$, $\mathtt{start}$ and $\mathtt{cat}$ are no scattered factors and each need one jumble. An example for a jumbled scattered factor with $2$ jumbles is $\mathtt{tatar}$. In this work, we investigate two problems on jumbled scattered factors from an algorithmic perspective. First, we give algorithms for testing jumbled Simon's equivalence where two words are equivalent if they share the same $\ell$-jumbled scattered factors up to length $k$. Second, we investigate how to count the possible occurrences of a jumbled scattered factor -- the jumbled binomial coefficient. After defining the jumbled binomial coefficient, we study jumbled embeddings and factorisations of such as well.

0.23

A generalized monoid of infinite words: asymptotic prefix-suffix quotients and algebraic structure

cs.FL math.GR ·2026-08-20 ·A. Alvarez Cruz, E. A. Alvarez Gutierrez
similarity 0.54
Abstract

A generalized monoid of words tilde{Sigma}* is constructed as the quotient of moderate nets of finite words by an asymptotic equivalence relation based on a bidirectional prefix-suffix metric. The main algebraic result is that this quotient is a monoid containing Sigma* faithfully, with a reversal involution, a natural divisibility preorder, failure of cancellation, and nontrivial idempotents. The construction is designed so that any functional depending only on a logarithmic prefix descends to the quotient, yielding a well-defined action of logarithmic-prefix functionals. Finite scalar values arise only after applying an additional renormalization functional, which depends on the chosen mould and window. With respect to the fixed truncation injection, the monoid strictly enlarges the classical set Sigma^{infty}: an explicit oscillating net is exhibited that has no limit in the Cantor space but defines a genuine element of tilde{Sigma}* not coming from a finite or right-infinite word under that injection.

0.50

Cycle Counting and Character Expectations Using Alternating Structures

cs.FL math.GR ·2026-08-27 ·Noam Ta Shma
theory similarity 0.54
Abstract · 59 pages, 22 figures

Recently, two related papers [arXiv:2412.13941, arXiv:2409.03626] found a connection between two subjects: the w-cycle theorem, which is a theorem about counting appearances of cycles reading out a word w in certain graphs, and character expectations on word measures. The w-cycle theorem was proven independently by [arXiv:1410.2540] using stackings and by [arXiv:1410.2579] using bislim structures. In the current work, we generalize stackings and bislim structures to alternating stackings and alternating bislim structures. We show how this significantly strengthens the w-cycle theorem for words admitting such alternating structures, and as a result, also strengthens the recent results of [arXiv:2412.13941] and [arXiv:2409.03626]. We show that generic words admit alternating bislim structures, and therefore, the strengthened results hold for generic words. Using our new machinery, we address conjectures of Wilton, of Hanany-Puder and of Puder-Shomroni. We prove that all three conjectures hold for generic words, but we also find counterexamples for the first two.

0.30

Lengths and Counting of Palindromic Prefixes of Standard Sturmian Words

cs.FL math.CO ·2026-11-15 ·Jasem Hamoud
similarity 0.53
Abstract

Every standard Sturmian word $c_\mathbf{d}$ is determined by a directive sequence $\mathbf{d}=(d_i)_{i\ge 1}$ of positive integers, and its palindromic prefixes are obtained by iterated palindromic closure. We describe the lengths of these prefixes by the numbers $j\,\ell_{i-1}+\ell_{i-2}-2$, where $\ell_n$ is the length of the $n$-th standard word and $1\le j\le d_i$, and we show that each nonzero length is attained by exactly one pair $(i,j)\neq(1,1)$. For a purely periodic directive sequence of period $k$ we then prove that the number $π_\mathbf{d}(N)$ of nonempty palindromic prefixes of length at most $N$ satisfies \[ π_\mathbf{d}(N)\sim\frac{d_1+\cdots+d_k}{\logλ_\mathbf{d}}\,\log N, \] where $λ_\mathbf{d}$ is the largest eigenvalue of the matrix $M(d_1)\cdots M(d_k)$. For the Fibonacci word this gives $π_\mathbf{d}(N)\sim\log N/\log\varphi$, where $\varphi=(1+\sqrt5)/2$.

0.30

Some complete $ω$-powers of a one-counter language in the difference hierarchy

cs.LO cs.FLcs.GTmath.GN+1 ·2026-10-12 ·Jacques Duparc, Olivier Finkel, Dominique Lecomte
theory similarity 0.53
Abstract

Fix a finite alphabet $Σ$ having at least two letters, and natural numbers $n,k\geq 1$. We denote by $D_n(\mathbfΠ^0_k)$ the class of differences of $n$ subsets of the Cantor space $Σ^ω$ in $\mathbfΠ0_k$, and by $D_n-(\mathbfΠ^0_k)$ the class of complements of sets in $D_n(\mathbfΠ^0_k)$. We prove, for any natural numbers $n,k\geq 1$, the existence of a finite alphabet $Σ$ having at least two letters and a finitary language $U_{n,k}$ over $Σ$ accepted by a one-counter automaton such that the $ω$-power $$U_{n,k}^\infty:={ w_0w_1\cdots\inΣ^ω\mid\forall i\inω~~w_i\in U_{n,k}}$$ is $D_{2n-1}(\mathbfΠ^0_k)$-complete. We also prove a conditional result for the dual classes $D^-_{2n}(\mathbfΠ^0_k)$: under the assumption that there exists a finitary language $V_{n,3}$ accepted by a one-counter automaton, such that its $ω$-power $V_{n,3}^\infty$ is $D^-_{2n}(\mathbfΠ^0_3)$-complete, there would also exist, for any integer $k>3$, a finitary language $V_{n,k}$ accepted by a one-counter automaton, such that its $ω$-power $V_{n,k}^\infty$ is $D^-_{2n}(\mathbfΠ^0_k)$-complete. Finally we add another conditionnal result about Wadge degrees of rational $\mathbfΔ^0_2$ omega powers, which completes the recent results of [FGL26].

0.23