Dorst–Smeulders Coding for Arbitrary Binary Words
Alessandro De Luca, Gabriele Fici · 2025
Read Dorst–Smeulders Coding for Arbitrary Binary Words by Alessandro De Luca, Gabriele Fici (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-08684.txt.
Introduction
Alessandro De Luca and 1 co-author extend Dorst-Smeulders coding to arbitrary binary words in a 2025 paper. A Sturmian word is a balanced binary sequence tied to discrete lines in geometry. Its Dorst-Smeulders code is four integers that rebuild it efficiently.
A linear time algorithm finds the code for the longest Sturmian prefix of any binary word. Repeating that step splits a word into the fewest possible Sturmian factors, each with its own code. The method could help compression when inputs contain long Sturmian segments. Though the code is short, the proof rests on deep structure of Sturmian words.
Catalog record
| CREATOR | Alessandro De Luca, Gabriele Fici |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 21 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-08684
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Dorst–Smeulders Coding for Arbitrary Binary Words Thanks: Gabriele Fici is partly supported by MUR project PRIN 2022 APML – 20229BCXNW, funded by the European Union – Mission 4 “Education and Research” C2 - Investment 1.1. Affiliation: DIETI, Università di Napoli Federico II, Italy E-mail [email protected] Alessandro De Luca, Gabriele Fici Abstract A binary word is Sturmian if the occurrences of each letter are balanced, in the sense that in any two factors of the same length, the difference between the number of occurrences of the same letter is at most 1 1 . In digital geometry, Sturmian words correspond to discrete approximations of straight line segments in the Euclidean plane. The Dorst–Smeulders coding, introduced in 1984, is a 4-tuple of integers that uniquely represents a Sturmian word w w , enabling its reconstruction using | w | |w| modular operations, making it highly efficient in practice. In this paper, we present a linear-time algorithm that, given a binary input word w w , computes the Dorst–Smeulders coding of its longest Sturmian prefix. This forms the basis for computing the Dorst–Smeulders coding of an arbitrary binary word w w , which is a minimal decomposition (in terms of the number of factors) of w w into Sturmian words, each represented by its Dorst–Smeulders coding. This coding could be leveraged in compression schemes where the input is transformed into a binary word composed of long Sturmian segments. Although the algorithm is conceptually simple and can be implemented in just a few lines of code, it is grounded in a deep analysis of the structural properties of Sturmian words. 1 Introduction Sturmian (finite) words are binary balanced words. They can be used to describe straight line segments in the discrete plane. In 1984, Dorst and Smeulders introduced a coding for uniquely representing a Sturmian word [ 9 ] . Although other codings were proposed in the literature (see, e.g., [ 13 ] ) the coding of Dorst and Smeulders has a clear interpretation in terms of combinatorics on words. In fact, Sturmian words are factors of (lower primitive) Christoffel words, and Christoffel words have lots of interesting combinatorial properties. For every length \ell>0 and every height (number of 1 ’s) h coprime with \ell , there is exactly one Christoffel word u_{h,\ell} . Moreover, Christoffel words are precisely the Lyndon Sturmian words. Let w be a Sturmian word of minimum period p . The Lyndon conjugate of the prefix of length p of w is therefore a Christoffel word u_{h,p} , and w_{1}\cdots w_{p}=\sigma^{s}(u_{h,p}) for some s\geq 0 , where \sigma is the usual (right) shift operator. The word w is then uniquely determined by its length n , its period p , the height h , and the shift s . The 4 -tuple (n,p,h,s) is the Dorst–Smeulders coding of w . In this paper, we extend the Dorst–Smeulders coding to an arbitrary binary word w by considering a particular factorization of w in Sturmian words and encoding each term with its Dorst–Smeulders coding. Let \Sigma be an alphabet, and let L\subseteq\Sigma^{*} be a language such that \Sigma\subseteq L . Then every word w in \Sigma^{*} can be factored in words of L , i.e., there exist x_{1},\ldots,x_{k}\in L such that w=x_{1}\cdots x_{k} . We call k the length of the factorization. We call a factorization w=x_{1}\cdots x_{k} minimal if any other factorization in words of L has length at least k . For example, if L=\mathit{Pal} is the language of palindromes, the length of a minimal factorization of w is also called the palindromic length of w [ 11 ] . For some languages, a minimal factorization can be obtained by the greedy algorithm , which consists in taking the longest prefix of w that belongs to L and recursing on what remains after removing this prefix from w . This is the case, for example, for the language \mathit{Lyn} of Lyndon words, where the minimal factorization is also called the Chen–Fox–Lyndon factorization [ 4 ] , but it is not the case for the language of palindromes. For example, the greedy factorization of w=0010 is w=00\cdot 1\cdot 0 and it is not minimal, since w=0\cdot 010 . In particular, if the language L is factorial (i.e., it is closed under taking factors), then the greedy algorithm always produces a minimal factorization—this can be easily proved by contradiction. Actually, it is sufficient that the language is closed under taking suffixes [ 5 ] . By symmetry, for languages closed under taking prefixes, the right-to-left greedy factorization produces a minimal factorization. The complexity of the problem of determining a minimal factorization depends on the language L . For example, it is known that this complexity is linear in the length of the input word for \mathit{Pal} [ 12 ] and \mathit{Lyn} [ 10 ] . For those languages such that the greedy algorithm produces a minimal factorization, this complexity reduces to the complexity of computing the longest prefix of w that belongs to L . In this paper, we are particularly interested in the language \mathit{Sturm} of Sturmian words. A binary word is Sturmian if the occurrences of each letter are balanced, in the sense that in any two factors of the same length, the difference between the number of occurrences of the same letter is at most 1 . The language \mathit{Sturm} is a factorial language; hence, a minimal Sturmian factorization can be obtained by the greedy algorithm. We then call Dorst–Smeulders coding of an arbitrary binary word w the list of Dorst–Smeulders codings of the terms in the minimal Sturmian factorization of w obtained from the greedy algorithm. We present a linear-time algorithm to compute the Dorst–Smeulders coding of an arbitrary binary word. The core of the algorithm is a procedure that, given an arbitrary binary input word w , computes the longest prefix of w that is Sturmian (a different linear time algorithm for this, based on geometric considerations, is described in [ 2 ] ). Our procedure scans w from left to right, letter by letter, checking for an arithmetic property that ensures balance, and updates the 4 parameters of the Dorst–Smeulders coding, thus yielding as output the Dorst–Smeulders coding of the longest Sturmian prefix. Our algorithm is straightforward to implement since it consists of only elementary arithmetic operations. 2 Preliminaries Let \Sigma be a finite alphabet. A language L over \Sigma is a set of words over \Sigma , i.e., a subset of \Sigma^{*} , the free monoid generated by \Sigma . A language L is factorial (or factor-closed) if it contains all the factors of its words. Let w=w_{1}w_{2}\cdots w_{n} , w_{i}\in\Sigma , be a word of length n=|w| . An integer p>0 is a period of w if w_{i}=w_{j} whenever i=j\mod p . The prefix \rho(w) of w whose length is the minimum period of w is called the fractional root of w . A border of w is a factor that occurs as a prefix and as a suffix in w . The word w has a border of length b if and only if |w|-b is a period of w . An unbordered word is a word that coincides with its fractional root,