Sistemas Q

Los sistemas Q son un método de transformación de grafos dirigidos según reglas gramaticales dadas , desarrollado en la Universidad de Montreal por Alain Colmerauer entre 1967 y 1970 para su uso en el procesamiento del lenguaje natural . El sistema de traducción automática de la Universidad de Montreal, TAUM-73 , utilizó los sistemas Q como su formalismo lingüístico.

La estructura de datos manipulada por un sistema Q es un grafo Q , un grafo dirigido acíclico con un nodo de entrada y un nodo de salida, donde cada arco contiene un árbol ordenado etiquetado . Una oración de entrada se representa generalmente mediante un grafo Q lineal, donde cada arco contiene una palabra (el árbol se reduce a un nodo etiquetado con dicha palabra). Tras el análisis, el grafo Q suele ser un conjunto de caminos de un arco, cada uno de los cuales contiene un posible árbol de análisis. Después de la generación, el objetivo suele ser producir tantos caminos como salidas deseadas, con una palabra por arco.

Un sistema Q consiste en una secuencia de tratamientos Q , cada uno de los cuales es un conjunto de reglas Q , de la forma <ruta_coincidente> == <ruta_añadida> [<condición>]. Los tratamientos Q se aplican en secuencia, a menos que uno de ellos produzca el grafo Q vacío, en cuyo caso el resultado es el último grafo Q obtenido. Las tres partes de una regla pueden contener variables para etiquetas, árboles y bosques. Todas las variables después de "==" deben aparecer en la parte <ruta_coincidente>. Las variables son locales a las reglas.

Un tratamiento Q funciona en dos pasos: adición y limpieza. Primero aplica todas sus reglas exhaustivamente, mediante instanciación (unificación unidireccional), añadiendo así nuevas rutas al grafo Q actual (los arcos añadidos y sus árboles pueden utilizarse para generar nuevas rutas). Si este proceso de adición se detiene, se borran todos los arcos utilizados en alguna aplicación exitosa de reglas, así como todos los arcos no utilizados que ya no forman parte de ninguna ruta desde el nodo de entrada al nodo de salida. Por lo tanto, el resultado, si lo hay (si el paso de adición finaliza), es de nuevo un grafo Q. Esto permite encadenar varios sistemas Q, cada uno de los cuales realiza una tarea especializada, formando juntos un sistema complejo. Por ejemplo, TAUM 73 constaba de quince sistemas Q encadenados.

Una extensión de la idea básica de los sistemas Q, a saber, reemplazar la instanciación por la unificación (en pocas palabras, permitir variables "nuevas" en la parte derecha de una regla y reemplazar los árboles etiquetados parametrizados por términos lógicos), dio lugar a Prolog , diseñado por Alain Colmerauer y Philippe Roussel en 1972. Los refinamientos en la dirección opuesta (reduciendo el no determinismo e introduciendo etiquetas tipadas) por parte de John Chandioux dieron lugar a GramR , utilizado para programar METEO a partir de 1985.

En 2009, Hong Thai Nguyen de GETALP, ^{[ 1 ]} Laboratoire d'Informatique de Grenoble ^{[ 2 ]} reimplementó el lenguaje Q en C, utilizando ANTLR para compilar los sistemas Q y los grafos Q, y un algoritmo propuesto por Christian Boitet (ya que no se había publicado ninguno y se habían perdido las fuentes de la implementación anterior en Fortran ). Esa implementación fue corregida, completada y extendida (para etiquetas que utilizan caracteres Unicode y no solo los caracteres imprimibles del CDC6600 de la versión histórica) por David Cattanéo en 2010-11.

• Sistema METEO

• Colmerauer, A: Les systèmes Q ou un formalismo para analizar y sintetizar des frases sobre ordenador. Mimeo, Montreal, 1969.
• Nguyen, HT: Des sistemas de TA homogéneos aux sistemas de TAO hétérogènes. Estos UJF, Grenoble, 2009.

• http://unldeco.imag.fr/unldeco/SystemsQ.po?localhost=/home/nguyenht/SYS-Q/MONITEUR/ Archivado el 20/07/2011 en Wayback Machine ] Nueva demostración de Q-systems