Ver registro no DEDALUS
Exportar registro bibliográfico

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:
  • USP affiliated authors: SANTOS, GILMAR PEREIRA DOS - EACH
  • USP Schools: 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: (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 promissoraA 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)
  • Imprenta:
  • Data da defesa: 26.10.2018
  • Acesso online ao documento

    Online access or search this record in

    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      SANTOS, Gilmar Pereira dos; MACHADO-LIMA, Ariane. 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.Universidade de São Paulo, São Paulo, 2018. Disponível em: < http://www.teses.usp.br/teses/disponiveis/100/100131/tde-17122018-112356/ >.
    • APA

      Santos, G. P. dos, & Machado-Lima, A. (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. 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, Machado-Lima A. 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 ;Available from: http://www.teses.usp.br/teses/disponiveis/100/100131/tde-17122018-112356/
    • Vancouver

      Santos GP dos, Machado-Lima A. 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 ;Available from: http://www.teses.usp.br/teses/disponiveis/100/100131/tde-17122018-112356/

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI: