Search

We evaluate the influence of different alphabet orderings on the Lyndon factorization of a string. Experiments with Pizza&Chili datasets show that for most alphabet reorderings, the number of Lyndon factors is usually small, and the length of the longest Lyndon factor can be as large as the input string, which is unfavorable for algorithms and indexes that depend on the number of Lyndon factors. We present results with randomized alphabet permutations that can be used as a baseline to assess the effectiveness of heuristics and methods designed to modify the Lyndon factorization of a string via alphabet reordering. [ABSTRACT FROM AUTHOR]

The Lyndon factorization of a word has been largely studied and recently variants of it have been introduced and investigated with different motivations. In particular, the canonical inverse Lyndon factorization ICFL (w) of a word w , introduced in [1] , maintains the main properties of the Lyndon factorization since it can be computed in linear time and it is uniquely determined. In this paper we investigate new properties of this factorization with the aim of exploring their use in some classical queries on w. The main property we prove is related to a classical query on words. We prove that there are relations between the length of the longest common prefix (or longest common extension) lcp (x , y) of two different suffixes x , y of a word w and the maximum length M of two consecutive factors of ICFL (w). More precisely, M is an upper bound on the length of lcp (x , y). A main tool used in the proof of the above result is a property that we state for factors m i with nonempty borders in ICFL (w) : a nonempty border of m i cannot be a prefix of the next factor m i + 1. Another interesting result relates sorting of global suffixes, i.e., suffixes of a word w , and sorting of local suffixes, i.e., suffixes of products of factors in ICFL (w). This is the counterpart for ICFL (w) of the compatibility property, proved in [2,3] for the Lyndon factorization. Roughly, the compatibility property allows us to extend the mutual order between suffixes of products of the (inverse) Lyndon factors to the suffixes of the whole word. The last property we prove focuses on the Lyndon factorizations of a word and its factors. It suggests that the Lyndon factorizations of two words sharing a common overlap could be used to capture the common overlap of these two words. [ABSTRACT FROM AUTHOR]

A generalized lexicographic order on words is a lexicographic order where the total order of the (possibly infinite) alphabet depends on the position of the comparison. A generalized Lyndon word is a finite word which is strictly smallest among its class of rotations with respect to a generalized lexicographic order. This notion can be extended to infinite words: an infinite generalized Lyndon word is an infinite word which is strictly smallest among its class of suffixes. We positively answer a question of Dolce, Restivo, and Reutenauer by proving that every infinite word has a unique nonincreasing factorization into finite and infinite generalized Lyndon words. When this factorization has finitely many terms, we characterize the last term of the factorization. Our methods also show that the infinite generalized Lyndon words are precisely the words with infinitely many generalized Lyndon prefixes. [ABSTRACT FROM AUTHOR]

The Burrows–Wheeler transform (BWT) is a permutation whose applications are prevalent in data compression and text indexing. The bijective BWT is a bijective variant of it that has not yet been studied for text indexing applications. We fill this gap by proposing a self-index built on the bijective BWT. The self-index applies the backward search technique of the FM-index to find a pattern P with O (| P | lg ⁡ | P |) backward search steps. Additionally, we propose the first linear-time construction algorithm that is based on SAIS, improving the best known result of O (n lg ⁡ n / lg ⁡ lg ⁡ n) time to linear. [ABSTRACT FROM AUTHOR]

A generalized lexicographic order on words is a lexicographic order where the total order of the (possibly infinite) alphabet depends on the position of the comparison. A generalized Lyndon word is a finite word which is strictly smallest among its class of rotations with respect to a generalized lexicographic order. This notion can be extended to infinite words: an infinite generalized Lyndon word is an infinite word which is strictly smallest among its class of suffixes. We positively answer a question of Dolce, Restivo, and Reutenauer by proving that every infinite word has a unique nonincreasing factorization into finite and infinite generalized Lyndon words. When this factorization has finitely many terms, we characterize the last term of the factorization. Our methods also show that the infinite generalized Lyndon words are precisely the words with infinitely many generalized Lyndon prefixes. [ABSTRACT FROM AUTHOR]

We present two modifications of Duval’s algorithm for computing the Lyndon factorization of a string. One of the algorithms has been designed for strings containing runs of the smallest character. It works best for small alphabets and it is able to skip a significant number of characters of the string. Moreover, it can be engineered to have linear time complexity in the worst case. When there is a run-length encoded string R of length ρ , the other algorithm computes the Lyndon factorization of R in O ( ρ ) time and in constant space. It is shown by experimental results that the new variations are faster than Duval’s original algorithm in many scenarios.

The Lyndon factorization of a string w is a unique factorization ℓ 1 p 1 , … , ℓ m p m of w such that ℓ 1 , … , ℓ m is a sequence of Lyndon words that is monotonically decreasing in lexicographic order. In this paper, we consider the reverse-engineering problem on Lyndon factorization : Given a sequence S = ( ( s 1 , p 1 ) , … , ( s m , p m ) ) of ordered pairs of positive integers, find a string w whose Lyndon factorization corresponds to the input sequence S , i.e., the Lyndon factorization of w is in a form of ℓ 1 p 1 , … , ℓ m p m with | ℓ i | = s i for all 1 ≤ i ≤ m . Firstly, we show that there exists a simple O ( n ) -time algorithm if the size of the alphabet is unbounded, where n is the length of the output string. Secondly, we present an O ( n ) -time algorithm to compute a string over an alphabet of the smallest size. Thirdly, we show how to compute only the size of the smallest alphabet in O ( m ) time. Fourthly, we give an O ( m ) -time algorithm to compute an O ( m ) -size representation of a string over an alphabet of the smallest size. Finally, we propose an efficient algorithm to enumerate all strings whose Lyndon factorizations correspond to S . [ABSTRACT FROM AUTHOR]

We present two efficient algorithms which, given a compressed representation of a string w of length N , compute the Lyndon factorization of w . Given a straight line program (SLP) S of size n that describes w , the first algorithm runs in O ( n 2 + P ( n , N ) + Q ( n , N ) n log ⁡ n ) time and O ( n 2 + S ( n , N ) ) space, where P ( n , N ) , S ( n , N ) , Q ( n , N ) are respectively the pre-processing time, space, and query time of a data structure for longest common extensions (LCE) on SLPs. Given the Lempel–Ziv 78 encoding of size s for w , the second algorithm runs in O ( s log ⁡ s ) time and space. [ABSTRACT FROM AUTHOR]

The main goal of this paper is to highlight the relationship between the suffix array of a text and its Lyndon factorization. It is proved in [15] that one can obtain the Lyndon factorization of a text from its suffix array. Conversely, here we show a new method for constructing the suffix array of a text that takes advantage of its Lyndon factorization. The surprising consequence of our results is that, in order to construct the suffix array, the local suffixes inside each Lyndon factor can be separately processed, allowing different implementative scenarios, such as online, external and internal memory, or parallel implementations. Based on our results, the algorithm that we propose sorts the suffixes by starting from the leftmost Lyndon factors, even if the whole text or the complete Lyndon factorization are not yet available. [ABSTRACT FROM AUTHOR]

Combinatorics

Abstract: The decrease value theorem is restated and given a specialization more adapted to permutation statistic calculus. As an application, the computation of a factorial multivariable generating function for the wreath product of the cyclic group of finite order by the symmetric group is given in full detail. [Copyright &y& Elsevier]

In a recent paper, Brlek, Jamet and Paquin showed that some extremal infinite smooth words are also infinite Lyndon words. This result raises a natural question: are they the only ones? If no, what do the infinite smooth words that are also Lyndon words look like? In this paper, we give the answer, proving that the only infinite smooth Lyndon words are m{1< b}, with a,b even, m{1< b} and |Δ-11 with b odd, where mA is the minimal infinite smooth word with respect to the lexicographic order over a numerical alphabet A and Δ is the run-length encoding function. [ABSTRACT FROM AUTHOR]

The LS (Look and Say) derivative of a word is obtained by writing the number of consecutive equal letters when the word is spelled from left to right. For example, LS(1 1 2 3 3) = 2 1 1 2 2 3 (two 1, one 2, two 3). We start the study of the behaviour of binary words generated by morphisms under the LS operator, focusing in particular on the Fibonacci word. [ABSTRACT FROM AUTHOR]

In this paper, we consider smooth words over 2-letter alphabets , where are integers having same parity, with . We show that all are recurrent and that the closure of the set of factors under reversal holds for odd alphabets only. We provide a linear time algorithm computing the extremal words, w.r.t. lexicographic order. The minimal word is an infinite Lyndon word if and only if either and are odd, or are even. A connection is established between generalized Kolakoski words and maximal infinite smooth words over even 2-letter alphabets revealing new properties for some of the generalized Kolakoski words. Finally, the frequency of letters in extremal words is 1/2 for even alphabets, and for with odd, the frequency of ’s is . [Copyright &y& Elsevier]

Smooth words are connected to the Kolakoski sequence. We construct the maximal and the minimal infinite smooth words, with respect to the lexicographical order. The naive algorithm generating them is improved by using a reduction of the De Bruijn graph of their factors. We also study their Lyndon factorizations. Finally, we show that the minimal smooth word over the alphabet {1; 3} belongs to the orbit of the Fibonacci word. [ABSTRACT FROM AUTHOR]

We introduce a finite semigroup associated with a conjugacy class of a word in the free monoid over a finite alphabet. Using properties of this semigroup we derive results on combinatorics on words. [ABSTRACT FROM AUTHOR]

Prouhet words are a natural generalization, over alphabets with more than two letters, of the well known binary Thue–Morse word.We give a unique factorization of these words in a sequence of decreasing Lyndon words, then generalizing such a decomposition given by Ido and Melanc¸on for the Thue–Morse word. [Copyright &y& Elsevier]

The i-th symbol of the well-known infinite word of Thue on the alphabet \ 0,1\ can be characterized as the parity of the number of occurrences of the digit 1 in the binary notation of i. Generalized words of Thue are based on counting the parity of occurrences of an arbitrary word w∈\ 0,1\^+-0^* in the binary notation of i. We provide here the standard Lyndon factorization of some subclasses of this class of infinite words.

We compute the Lyndon factorization of the Thue-Morse word. We also compute the Lyndon factorization of two related sequences involving morphisms that give rise to new presentations of these sequences.

We present two modifications of Duval's algorithm for computing the Lyndon factorization of a string. One of the algorithms has been designed for strings containing runs of the smallest character. It works best for small alphabets and it is able to skip a significant number of characters of the string. Moreover, it can be engineered to have linear time complexity in the worst case. When there is a run-length encoded string R of length ρ , the other algorithm computes the Lyndon factorization of R in O (ρ) time and in constant space. It is shown by experimental results that the new variations are faster than Duval's original algorithm in many scenarios. [ABSTRACT FROM AUTHOR]