Autómatas de Watson-Crick: Inferencia de modelos y caracterización de clases de lenguajes sensibles al contexto

Abstract

Este trabajo se enmarca en el área de investigación de la inferencia gramatical y la teoría de lenguajes formales. La inferencia gramatical trata fundamentalmente sobre el estudio del aprendizaje automático (inferencia inductiva) para la formulación de modelos que definen clases de lenguajes formales. En este trabajo, se abordará el estudio y la formulación de algoritmos de inferencia para el modelo de autómata finito de Watson-Crick, que es un modelo que se formuló inicialmente en el ámbito de la computación con ADN. En el TFM se plantearán y formularán nuevos algoritmos de identificación de autómatas de Watson-Crick, se estudiarán algunas propiedades fundamentales de los algoritmos propuestos (especialmente, convergencia de hipótesisy complejidad computacional) y se realizarán experimentos sintéticos para verificar su bondad en el ámbito del aprendizaje automático. El trabajo tiene una segunda parte donde se caracterizarán las subclases de lenguajes sensibles al contexto que definen los algoritmos de inferencia anteriormente propuestos. Se estudiarán algunas de sus propiedades formales con respecto a operaciones de lenguajes clásicas, se ubicarán las clases bajo estudio en la jerarquía de Chomsky y se pondrá en relación con el ámbito de la computación basada en ADN.