Publicação: Fatoração lyndon dinâmica após uma operação de substituição
Carregando...
Tipo do documento
Data
Direito de acesso
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Título da Revista
ISSN da Revista
Título de Volume
Autores
Orientador
Coorientador
Albertini, Marcelo Keese
Resumo
Esta dissertação investiga o problema da atualização da fatoração Lyndon de uma
palavra w, de tamanho n, quando uma operação de substituição em um símbolo w[i] é
realizada, com 0 ≤ i < n. O algoritmo proposto calcula a fatoração Lyndon da nova
palavra w′ a partir dos fatores Lyndon de w avaliando o efeito da alteração em tempo
O(n j), em que n j é o tamanho do fator Lyndon em que w[i] está. Em particular, oito
diferentes casos são descritos para obter a fatoração de w′ a partir dos dos fatores Lyndon
de w. O custo computacional em três casos é O(n j), enquanto que, nos outros cinco
casos, o custo é O(n), isto é, o mesmo custo para calcular a fatoração do de w′ com o
algoritmo de Duval. Conforme a literatura disponível e consultada, este é o primeiro
trabalho que aborda o problema da fatoração Lyndon dinâmica a partir de operações de
substituição em w. Os resultados apresentados nesta dissertação visam contribuir para
uma nova perspectiva para esse problema.
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.
Palavras-chave
Palavras de Lyndon, Fatoração Lyndon, Combinatória de Palavras, Atualização de Textos, Atualização Fatores Lyndon
Citação
MARTINS, Luísa Andrade. Fatoração lyndon dinâmica após uma operação de substituição. 2024. 48f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Uberlândia, Uberlândia, 2024. DOI http://doi.org/10.14393/ufu.di.2024.158