Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEfficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence
267
0
0.0
(
0
)
Added by
Jakub Radoszewski
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We give efficient algorithms for ranking Lyndon words of length n over an alphabet of size {sigma}. The rank of a Lyndon word is its position in the sequence of lexicographically ordered Lyndon words of the same length. The outputs are integers of exponential size, and complexity of arithmetic operations on such large integers cannot be ignored. Our model of computations is the word-RAM, in which basic arithmetic operations on (large) numbers of size at most {sigma}^n take O(n) time. Our algorithm for ranking Lyndon words makes O(n^2) arithmetic operations (this would imply directly cubic time on word-RAM). However, using an algebraic approach we are able to reduce the total time complexity on the word-RAM to O(n^2 log {sigma}). We also present an O(n^3 log^2 {sigma})-time algorithm that generates the Lyndon word of a given length and rank in lexicographic order. Finally we use the connections between Lyndon words and lexicographically minimal de Bruijn sequences (theorem of Fredricksen and Maiorana) to develop the first polynomial-time algorithm for decoding minimal de Bruijn sequence of any rank n (it determines the position of an arbitrary word of length n within the de Bruijn sequence).
rate research
Read More
We present a space- and time-efficient fully dynamic implementation de Bruijn graphs, which can also support fixed-length jumbled pattern matching.
In this paper, we extend the notion of Lyndon word to transfinite words. We prove two main results. We first show that, given a transfinite word, there exists a unique factorization in Lyndon words that are densely non-increasing, a relaxation of the condition used in the case of finite words. In the annex, we prove that the factorization of a rational word has a special form and that it can be computed from a rational expression describing the word.
The notion of emph{string attractor} has recently been introduced in [Prezza, 2017] and studied in [Kempa and Prezza, 2018] to provide a unifying framework for known dictionary-based compressors. A string attractor for a word $w=w[1]w[2]cdots w[n]$ is a subset $Gamma$ of the positions ${1,ldots,n}$, such that all distinct factors of $w$ have an occurrence crossing at least one of the elements of $Gamma$. While finding the smallest string attractor for a word is a NP-complete problem, it has been proved in [Kempa and Prezza, 2018] that dictionary compressors can be interpreted as algorithms approximating the smallest string attractor for a given word. In this paper we explore the notion of string attractor from a combinatorial point of view, by focusing on several families of finite words. The results presented in the paper suggest that the notion of string attractor can be used to define new tools to investigate combinatorial properties of the words.
A generalized lexicographical order on infinite words is defined by choosing for each position a total order on the alphabet. This allows to define generalized Lyndon words. Every word in the free monoid can be factorized in a unique way as a nonincreasing factorization of generalized Lyndon words. We give new characterizations of the first and the last factor in this factorization as well as new characterization of generalized Lyndon words. We also give more specific results on two special cases: the classical one and the one arising from the alternating lexicographical order.
In this paper we compare two finite words $u$ and $v$ by the lexicographical order of the infinite words $u^omega$ and $v^omega$. Informally, we say that we compare $u$ and $v$ by the infinite order. We show several properties of Lyndon words expressed using this infinite order. The innovative aspect of this approach is that it allows to take into account also non trivial conditions on the prefixes of a word, instead that only on the suffixes. In particular, we derive a result of Ufnarovskij [V. Ufnarovskij, Combinatorial and asymptotic methods in algebra, 1995] that characterizes a Lyndon word as a word which is greater, with respect to the infinite order, than all its prefixes. Motivated by this result, we introduce the prefix standard permutation of a Lyndon word and the corresponding (left) Cartesian tree. We prove that the left Cartesian tree is equal to the left Lyndon tree, defined by the left standard factorization of Viennot [G. Viennot, Alg`ebres de Lie libres et monoides libres, 1978]. This result is dual with respect to a theorem of Hohlweg and Reutenauer [C. Hohlweg and C. Reutenauer, Lyndon words, permutations and trees, 2003].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
