Gramáticas de grafos y su aplicación en inferencia gramatical

Abstract

En este trabajo se presentan las gramáticas de grafos en particular un tipo de gramáticas de grafo las cuales tienen un contexto libre en el mecanismo de derivación al igual que las gramáticas de Chomsky proporcionando de esta manera un simple mecanismo para generar lenguajes de grafos. Para hacer transparente el proceso de generación de grafos se introducen los grafos decorados que son grafos equipados con una información adicional llamada hiperlíneal las cuales al ser reemplazadas en forma iterativa desencadenan procesos generativos El control de este proceso así como cuando y donde se realiza depende fundamentalmente del rótulo y del número de hiperlíneas que el grafo decorado posee. Como aplicación se desarrolla un algoritmo de inferencia gramatical, el cual posee como entrada un conjunto finito de grafos y como salida este tipo particular de gramáticas de grafos. El algoritmo de inferencia está basado esencialmente en iterar las aplicaciones de una operación, la cual descompone de una manera particular las reglas de la gramática. Además es estimado el número de gramáticas inferidas dependiente del tamaño del grafo. Dado que el Algoritmo de Inferencia produce en general un número exponencial de Gramáticas es que para reducir el número de gramáticas inferidas se considerarán medidas semánticas para limitarlas. Una conocida restricción de este tipo son los ejemplos negativos de los cuales se exige que ellos no puedan ser generados.