Fatoração lyndon dinâmica após uma operação de substituição

Abstract

This dissertation investigates the problem of updating the Lyndon factorization of a word w, of size n, when a substitution operation is performed on a symbol w[i], with 0 ≤ i < n. The proposed algorithm computes the Lyndon factorization of the new word w′ from the Lyndon factors of w by assessing the effect of the change in time O(n j), where n j is the size of the Lyndon factor in which w[i] is located. In particular, eight different cases are described to obtain the factorization of w′ from the Lyndon factors of w. The computational cost in three cases is O(n j), whereas, the other five cases, the cost is O(n), that is, the same cost to calculate the factorization of w′ with Duval’s algorithm. According to the available and consulted literature, this is the first work that addresses the problem of dynamic Lyndon factorization from substitution operations in w. The results presented in this dissertation aim to contribute to a new perspective on this problem.