dc.contributorVILARIÑO AYALA, DARNES; 216751
dc.contributorLAVALLE MARTINEZ, JOSE DE JESUS; 64830
dc.creatorMOYAO MARTINEZ, YOLANDA; 80297
dc.creatorMoyao Martínez, Yolanda
dc.date.accessioned2021-10-20T03:58:52Z
dc.date.accessioned2022-09-26T13:38:42Z
dc.date.available2021-10-20T03:58:52Z
dc.date.available2022-09-26T13:38:42Z
dc.date.created2021-10-20T03:58:52Z
dc.date.issued2021-08
dc.identifierhttps://hdl.handle.net/20.500.12371/14796
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/3548565
dc.description.abstract“Este trabajo trata del problema de membresía en gramáticas de reemplazo de hiperaristas (HRG). Dado un hipergrafo H con nodos e hiperaristas etiquetadas, dirigidas y enraizadas, el problema consiste en determinar si H ∈ L (G), donde G ∈ HRG, es decir si H está ́ en el lenguaje generado por G. Se conoce que el problema de membresía para HRG es, en general, intratable. Sin embargo, este problema se ha resuelto en tiempo polinomial pará algún un tipo restringido de HRG. El objetivo principal de esta investigación es desarrollar un algoritmo correcto con complejidad polinomial que resuelva el problema de membresía en HRG. Para lograr el objetivo fue necesario utilizar una definición ́ alternativa de la matriz de adyacencias para hipergrafos, la cual es una generalización de la matriz de adyacencias para grafos. En este trabajo se obtuvo un algoritmo Analizador, cuya complejidad es del orden O (l5 ), donde l es el número de vértices del hipergrafo de entrada. Este algoritmo lleva acabo el análisis directamente en la Matriz de Adyacencias del hipergrafo H. También, para el algoritmo propuesto se presenta la demostración de su corrección”.
dc.languagespa
dc.rightshttp://creativecommons.org/licenses/by-nc-nd/4.0
dc.rightsopenAccess
dc.titleAlgoritmo de membresía para gramáticas de reemplazo de hiperaristas
dc.typeTesis de doctorado


Este ítem pertenece a la siguiente institución