Analisador sintático de Earley para gramáticas livres de contexto adaptativas e sua aplicação na caracterização de famílias de RNAs com pseudonós (2018)
- Authors:
- Autor USP: SANTOS, GILMAR PEREIRA DOS - EACH
- Unidade: EACH
- Subjects: RECONHECIMENTO DE PADRÕES; ANÁLISE SINTÁTICA; LINGUAGENS FORMAIS; LINGUAGENS LIVRES DE CONTEXTO; RNA
- Keywords: Adaptive Methods; Gramáticas; Grammars; Métodos Adaptativos; Métodos Sintáticos; Pseudoknot; Pseudonós; Syntactic Methods
- Language: Português
- Abstract: A teoria das linguagens formais é amplamente utilizada nos processos de solução de problemas de naturezas diversas, uma vez que tem poder de lidar tanto com as linguagens artifiais quanto com as linguagens naturais. As gramáticas, formalismos capazes de sintetizar as linguagens, podem também ser utilizadas no âmbito do problema de reconhecimento de padrões por poderem modelar as hierarquias dos componentes da linguagem, decompondo padrões em subestruturas. Seguindo essa linha, o arcabouço GrammarLab, cujo objetivo é facilitar a implementação, geração e testes de diferentes classificadores de sequências baseados em gramáticas, permitia em sua implementação anterior o uso de gramáticas regulares e livres de contexto. No entanto, alguns problemas necessitam de formalismos presentes apenas em gramáticas de níveis superiores na hierarquia de Chomsky. O problema encontrado ao se subir a hierarquia de gramáticas é a complexidade de tempo necessária para a análise sintática. Enquanto o reconhecimento de sequências por gramáticas regulares e livres de contexto pode ser feito em tempo polinomial, o problema geral de reconhecimento por gramáticas sensíveis ao contexto é um problema NP-completo e o de gramáticas irrestritas é considerado indecidível no caso geral... (Continua)(Continuação) No entanto, o uso de métodos adaptativos possibilita que uma gramática altere seu conjunto de regras de produção durante a geração de sentenças, adicionando sensibilidade ao contexto a gramáticas originalmente livres de contexto, sem prejudicar a complexidade de análise polinomial. Desta forma, este trabalho teve como foco a inserção de métodos adaptativos no arcabouço GrammarLab e a criação de uma versão adaptativa do algoritmo de Earley de análise sintática. Como forma de verificar sua aplicação em problemas reais, foi realizado um estudo preliminar do uso do arcabouço na caracterização de famílias funcionais de RNAs com estrutura conservada, incluindo pseudonós. Os pseudonós apresentam relações de dependências cruzadas entre os nucleotídeos de uma sequência de RNA, relação esta que exemplifica dependência de contexto, sendo portanto um bom caso para o uso do modelo com adaptatividade em sua constituição. Os resultados obtidos com duas famílias de RNAs com pseudonós mostraram que a abordagem é altamente promissora
- Imprenta:
- Data da defesa: 26.10.2018
-
ABNT
SANTOS, Gilmar Pereira dos. Analisador sintático de Earley para gramáticas livres de contexto adaptativas e sua aplicação na caracterização de famílias de RNAs com pseudonós. 2018. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2018. Disponível em: http://www.teses.usp.br/teses/disponiveis/100/100131/tde-17122018-112356/. Acesso em: 03 nov. 2024. -
APA
Santos, G. P. dos. (2018). Analisador sintático de Earley para gramáticas livres de contexto adaptativas e sua aplicação na caracterização de famílias de RNAs com pseudonós (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/100/100131/tde-17122018-112356/ -
NLM
Santos GP dos. Analisador sintático de Earley para gramáticas livres de contexto adaptativas e sua aplicação na caracterização de famílias de RNAs com pseudonós [Internet]. 2018 ;[citado 2024 nov. 03 ] Available from: http://www.teses.usp.br/teses/disponiveis/100/100131/tde-17122018-112356/ -
Vancouver
Santos GP dos. Analisador sintático de Earley para gramáticas livres de contexto adaptativas e sua aplicação na caracterização de famílias de RNAs com pseudonós [Internet]. 2018 ;[citado 2024 nov. 03 ] Available from: http://www.teses.usp.br/teses/disponiveis/100/100131/tde-17122018-112356/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
