Linha de pesquisa: Ciência de Dados

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(nj), em que nj é 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(nj), 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.

Local: Sala: 1B132 - Campus Santa Mônica - Av. João Naves de Ávila - 2121 - Bairro Santa Mônica
Uberlândia - MG - CEP 38400-902