Funciones de censo de lenguajes libre del contexto

Simple item page
dc.contributor.advisorMontoya Arguello, Juan Andrés
dc.contributor.authorZambrano Fernández, Luis Eduardo
dc.date.accessioned2024-03-03T18:45:58Z
dc.date.available2011
dc.date.available2024-03-03T18:45:58Z
dc.date.created2011
dc.date.issued2011
dc.description.abstractEn 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.
dc.description.abstractenglishIn this paper, we study some of the most relevant results on the census functions of context free languages and use these results to solve two tally counting problems when they are restricted to rectangular grids of fixed height. These problems arise from discrete tomography and statistical mechanics. Our solutions are based on the Schützenberger-Bertoni Method, a powerful counting technique that reduces multiple counting problems to the calculation of functions Census of certain formal languages. The complexity of calculating the census function of context-free languages is closely related to the ambiguity of language. For regular languages, there are linear time algorithms to calculate, if context-free languages is not ambiguous, there are parallel algorithms that calculate in polylogarithm time, however, for ambiguous context-free languages are not known deterministic polynomial time algorithms that can calculate their function census, only known fully polynomial time randomized approximation schemes to approximate. Our main contribution in this paper is to reduce the problem of counting polyominoes on rectangular grids of fixed height to the calculation the census function of a deterministic context-free language, and reduce the problem of counting self-avoiding walks on rectangular grids of fixed height to the calculation the census function of a regular language.
dc.description.degreelevelMaestría
dc.description.degreenameMagíster en Matemáticas
dc.format.mimetypeapplication/pdf
dc.identifier.instnameUniversidad Industrial de Santander
dc.identifier.reponameUniversidad Industrial de Santander
dc.identifier.repourlhttps://noesis.uis.edu.co
dc.identifier.urihttps://noesis.uis.edu.co/handle/20.500.14071/25860
dc.language.isospa
dc.publisherUniversidad Industrial de Santander
dc.publisher.facultyFacultad de Ciencias
dc.publisher.programMaestría en Matemáticas
dc.publisher.schoolEscuela de Matemáticas
dc.rightshttp://creativecommons.org/licenses/by/4.0/
dc.rights.accessrightsinfo:eu-repo/semantics/openAccess
dc.rights.creativecommonsAtribución-NoComercial-SinDerivadas 4.0 Internacional (CC BY-NC-ND 4.0)
dc.rights.licenseAttribution-NonCommercial 4.0 International (CC BY-NC 4.0)
dc.rights.urihttp://creativecommons.org/licenses/by-nc/4.0
dc.subjectProblemas de conteo delgado
dc.subjectMétodo de Schutzenberger-Bertoni
dc.subjectPoliominoes
dc.subjectCaminos que se auto-evitan
dc.subjectComplejidad computacional.
dc.subject.keywordTally counting problems
dc.subject.keywordSchutzenberger-Bertoni Method
dc.subject.keywordPolyominoes
dc.subject.keywordSelf-avoiding walks
dc.subject.keywordComputational complexity.
dc.titleFunciones de censo de lenguajes libre del contexto
dc.title.englishCensus Functions of Context Free
dc.type.coarhttp://purl.org/coar/version/c_b1a7d7d4d402bcce
dc.type.hasversionhttp://purl.org/coar/resource_type/c_bdcc
dc.type.localTesis/Trabajo de grado - Monografía - Maestria
Files
Original bundle
Now showing 1 - 3 of 3
No Thumbnail Available
Name:
Carta de autorización.pdf
Size:
367.05 KB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
Documento.pdf
Size:
957.09 KB
Format:
Adobe Portable Document Format
Download
No Thumbnail Available
Name:
Nota de proyecto.pdf
Size:
135.91 KB
Format:
Adobe Portable Document Format
Download
Collections
Maestría en Matemáticas