Fatoração Lyndon Dinâmica após uma Operação de Substituição

Dissertação de Mestrado
por Caroline Félix de Oliveira
Publicado: 20/02/2024 - 09:48
Última modificação: 20/02/2024 - 09:48

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

Coorientador: Marcelo Keese Albertini - Universidade Federal de Uberlândia, Centro de Ciências Exatas e Tecnologia, Faculdade de Ciências da Computação.
Banca Examinadora: 
Paulo Henrique Ribeiro Gabriel - Universidade Federal de Uberlândia, Faculdade de Computação
Guilherme Pimentel Telles - Universidade Estadual de Campinas, Instituto de Computação
Data e Horário: 
26/02/2024 - 10:00
Av. João Naves de Ávila, 2121 Bairro: Santa Mônica
Uberlândia, Minas Gerais, Brasil
38408-100
Campus Santa Mônica - Bloco 1B - Sala 132
Complemento: 
Bairro: Santa Mônica