Título

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

Autor

YOLANDA MOYAO MARTINEZ

Colaborador

DARNES VILARIÑO AYALA (Asesor de tesis)

JOSE DE JESUS LAVALLE MARTINEZ (Asesor de tesis)

Nivel de Acceso

Acceso Abierto

Licencia

http://creativecommons.org/licenses/by-nc-nd/4.0

Materias

Teoría de grafos - (LCC) Algoritmos computacionales - (LCC) Matemáticas computacionales - (LCC) INGENIERÍA Y TECNOLOGÍA - (CTI)

Resumen o descripción

“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”.

Fecha de publicación

agosto de 2021

Tipo de publicación

Tesis de doctorado

Recurso de información

https://hdl.handle.net/20.500.12371/14796

Formato

application/pdf

Idioma

Español

Audiencia

Público en general

Repositorio Orígen

Repositorio Institucional de Acceso Abierto RIAA-BUAP

Descargas

0