Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSome variations on Lyndon words
115
0
0.0
(
0
)
Added by
Francesco Dolce
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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].
rate research
Read More
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 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 main goal of this work is to establish a bijection between Dyck words and a family of Eulerian digraphs. We do so by providing two algorithms implementing such bijection in both directions. The connection between Dyck words and Eulerian digraphs exploits a novel combinatorial structure: a binary matrix, we call Dyck matrix, representing the cycles of an Eulerian digraph.
A Lyndon word is a non-empty word strictly smaller in the lexicographic order than any of its suffixes, except itself and the empty word. In this paper, we show how Lyndon words can be used in the distributed control of a set of n weak mobile robots. By weak, we mean that the robots are anonymous, memoryless, without any common sense of direction, and unable to communicate in an other way than observation. An efficient and simple deterministic protocol to form a regular n-gon is presented and proven for n prime.
A foundational result in the theory of Lyndon words (words that are strictly earlier in lexicographic order than their cyclic permutations) is the Chen-Fox-Lyndon theorem which states that every word has a unique non-increasing decomposition into Lyndon words. This article extends this factorization theorem, obtaining the proportion of these decompositions that are strictly decreasing. This result is then used to count primitive pseudo orbits (sets of primitive periodic orbits) on q-nary graphs. As an application we obtain a diagonal approximation to the variance of the characteristic polynomial coefficients q-nary quantum graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
