Algoritmo de membresía para gramáticas de reemplazo de hiperaristas

Simple item page
dc.audiencegeneralPublices_MX
dc.contributorVilariño Ayala, Darnes
dc.contributorLavalle Martínez, José de Jesús
dc.contributor.advisorVILARIÑO AYALA, DARNES; 216751
dc.contributor.advisorLAVALLE MARTINEZ, JOSE DE JESUS; 64830
dc.contributor.authorMoyao Martínez, Yolanda
dc.creatorMOYAO MARTINEZ, YOLANDA; 80297
dc.date.accessioned2021-10-20T03:58:52Z
dc.date.available2021-10-20T03:58:52Z
dc.date.issued2021-08
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”.es_MX
dc.folio20210804103046-5655-Tes_MX
dc.formatpdfes_MX
dc.identificator7es_MX
dc.identifier.urihttps://hdl.handle.net/20.500.12371/14796
dc.language.isospaes_MX
dc.matricula.creator216570427es_MX
dc.rights.accesopenAccesses_MX
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0es_MX
dc.subject.classificationINGENIERÍA Y TECNOLOGÍAes_MX
dc.subject.dbgunamHipergráficases_MX
dc.subject.lccTeoría de grafoses_MX
dc.subject.lccAlgoritmos computacionaleses_MX
dc.subject.lccMatemáticas computacionaleses_MX
dc.thesis.careerDoctorado en Ingeniería del Lenguaje y del Conocimientoes_MX
dc.thesis.degreedisciplineÁrea de Ingeniería y Ciencias Exactases_MX
dc.thesis.degreegrantorFacultad de Ciencias de la Computaciónes_MX
dc.thesis.degreetoobtainDoctor en Ingeniería del Lenguaje y del Conocimientoes_MX
dc.titleAlgoritmo de membresía para gramáticas de reemplazo de hiperaristases_MX
dc.typeTesis de doctoradoes_MX
dc.type.conacytdoctoralThesises_MX
dc.type.degreeDoctoradoes_MX
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
20210804103046-5655-T.pdf
Size:
528.46 KB
Format:
Adobe Portable Document Format
Description:
Download
Name:
20210804103046-5655-CARTA.pdf
Size:
128.67 KB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Tesis de Doctorado