Detalhes bibliográficos
| Ano de defesa: |
2017 |
| Autor(a) principal: |
Proença, Glasielly Demori |
| Orientador(a): |
Pedrotti, Vagner |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Não Informado pela instituição
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
https://repositorio.ufms.br/handle/123456789/3079
|
Resumo: |
O Teorema de Courcelle afirma que todo problema definível em Lógica Monádica de Segunda Ordem (LMSO) pode ser resolvido em grafos que apresentam uma decomposição em árvore com treewidth limitada por uma constante, em tempo de execução linear, através de um algoritmo de parâmetro fixo. Mas como todo algoritmo, seu tempo de execução depende de uma constante, a qual depende do limite da treewidth e do tamanho da expressão MSO, apresentando crescimento super exponencial à medida que a treewidth aumenta. Alguns autores têm apresentado abordagens para evitar esse problema da constante. Neste trabalho, exploramos uma pesquisa feita em [12], que trata esse problema utilizando teoria dos jogos para a avaliação da expressão MSO, a partir da decomposição em árvore do grafo de entrada. São descritos neste trabalho, os conceitos sobre a tratabilidade por parâmetro fixo, sobre decomposição em árvore e treewidth, e a abordagem para a avaliação de uma expressão MSO com um foco na validação experimental da complexidade do tempo de execução do algoritmo. |
