The notion of Lyndon word and Lyndon factorization has shown to have unexpected applications in theory as well in developing novel algorithms on words. A counterpart to these notions are those of inverse Lyndon word and inverse Lyndon factorization. Differently from the Lyndon words, the inverse Lyndon words may be bordered. The relationship between the two factorizations is related to the inverse lexicographic ordering, and has only been recently explored. More precisely, a main open question is how to get an inverse Lyndon factorization from a classical Lyndon factorization under the inverse lexicographic ordering, named CFLin. In this paper we reveal a strong connection between these two factorizations where the border plays a relevant role. More precisely, we show two main results. We say that a factorization has the border property if a nonempty border of a factor cannot be a prefix of the next factor. First we show that there exists a unique inverse Lyndon factorization having the border property. Then we show that this unique factorization with the border property is the so-called canonical inverse Lyndon factorization, named ICFL. By showing that ICFL is obtained by compacting factors of the Lyndon factorization over the inverse lexicographic ordering, we provide a linear time algorithm for computing ICFL from CFLin.

Circular splicing systems are a mathematical model, inspired by a recombinant behaviour of circular DNA. They are defined by a finite alphabet A, an initial set I of circular words, and a set R of rules. A circular splicing language is a language generated by a circular splicing system. An open pro blem is to characterize regular circular splicing languages and the corresponding circular splicing systems. In this framework an important role is played by unavoidable sets. These sets have been considered in several contexts. In particular, Ehrenfeucht, Haussler and Rozenberg (1983) proved the following generalization of a famous Higman’s theorem: the quasi-order induced by insertions of words from a fixed finite set is a well-quasi-order if and only if the finite set is unavoidable. In this paper we survey the known relations between unavoidable sets and regular circular languages. Motivated by these connections we give an alternative and simpler proof of the Ehrenfeucht, Haussler and Rozenberg result. Our proof is strongly based on a known characterization of unavoidable sets in terms of graphs associated with them.