Funciones de censo de lenguajes libre del contexto
No Thumbnail Available
Date
2011
Authors
Advisors
Evaluators
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad Industrial de Santander
Abstract
En este trabajo, estudiamos algunos de los resultados más relevantes acerca de las funciones de censo de los lenguajes libres del contexto y usamos estos resultados para resolver dos problemas de conteo delgado (tally counting problems) cuando son restringidos a grillas rectangulares de altura fija. Estos problemas surgen de la tomografía discreta y la mecánica estadística. Nuestras soluciones se basan en el método de Schützenberger-Bertoni, una importante técnica de conteo que permite reducir varios problemas de conteo al cálculo de las funciones de censo de ciertos lenguajes formales. La complejidad de calcular la función de censo de lenguajes libres del contexto está estrechamente relacionada con la ambigüedad del lenguaje. Para lenguajes regulares, existen algoritmos de tiempo lineal que permiten calcularla, para lenguajes libres del contexto no ambiguos, existen algoritmos en paralelo que permiten calcularla en tiempo polilogarítmico, sin embargo, para lenguajes libres del contexto ambiguos no se conocen algoritmos determinísticos de tiempo polinomial que permitan calcular su función de censo, solo se conocen esquemas de aproximación aleatorios completamente polinomiales que permiten aproximarla. Nuestro principal aporte consiste en reducir el problema de conteo de poliominoes en grillas rectangulares de altura fija al cálculo de la función de censo de un lenguaje libre del contexto determinístico y reducir el problema de conteo de caminos que se auto-evitan en grillas rectangulares de altura fija al cálculo de la función de censo de un lenguaje regular.
Description
Keywords
Problemas de conteo delgado, Método de Schutzenberger-Bertoni, Poliominoes, Caminos que se auto-evitan, Complejidad computacional.