Gráfico de términos

Un grafo de términos es una representación de una expresión en un lenguaje formal como un grafo generalizado cuyos vértices son términos . ^{[ 1 ]} Los grafos de términos son una forma de representación más potente que los árboles de expresiones porque pueden representar no solo subexpresiones comunes (es decir, pueden adoptar la estructura de un grafo dirigido acíclico) sino también subexpresiones cíclicas/recursivas (digrafos cíclicos).

Los árboles de sintaxis abstracta no pueden representar subexpresiones compartidas, ya que cada nodo del árbol solo puede tener un padre; esta simplicidad se logra a costa de la eficiencia debido a los cálculos duplicados y redundantes de términos idénticos. Por esta razón, los grafos de términos se utilizan a menudo como lenguaje intermedio en una etapa de compilación posterior a la construcción de árboles de sintaxis abstracta mediante análisis sintáctico.

La frase " reescritura de grafos de términos " se usa a menudo al hablar de métodos de reescritura de grafos para transformar expresiones en lenguajes formales. ^{[ 2 ]} Considerados desde el punto de vista de las gramáticas de grafos, los grafos de términos no son grafos regulares, sino hipergrafos donde una palabra n-aria tendrá un subgrafo particular en primer lugar, otro en segundo lugar, y así sucesivamente, una distinción que no existe en los grafos no dirigidos usuales estudiados en la teoría de grafos.

Los grafos de términos son un tema destacado en la investigación de lenguajes de programación, ya que las reglas de reescritura de grafos de términos pueden expresar formalmente la semántica operacional de un compilador . Los grafos de términos también se utilizan como máquinas abstractas capaces de modelar cálculos químicos y biológicos, así como cálculos gráficos como los modelos de concurrencia. Los grafos de términos pueden realizar verificación automatizada y programación lógica, ya que son idóneos para representar enunciados cuantificados en lógica de primer orden. El software de programación simbólica es otra aplicación para los grafos de términos, que son capaces de representar y realizar cálculos con estructuras algebraicas abstractas como grupos, cuerpos y anillos.

La conferencia TERMGRAPH ^{[ 3 ]} se centra por completo en la investigación sobre la reescritura de grafos de términos y sus aplicaciones.

Los grafos de términos también se utilizan en la inferencia de tipos, donde la estructura del grafo ayuda a implementar la unificación de tipos. ^{[ 4 ]}

• Término (lógica)
• Reescritura de grafos