Establecer restricción
En matemáticas e informática teórica , una restricción de conjunto es una ecuación o una inecuación entre conjuntos de términos . De manera similar a los sistemas de ( in ) ecuaciones entre números, se estudian métodos para resolver sistemas de restricciones establecidas. Los diferentes enfoques admiten diferentes operadores (como "∪", "∩", "\" y la aplicación de funciones) [nota 1] en conjuntos y diferentes relaciones de (in)ecuación (como "=", "⊆" y "⊈" ) entre expresiones de conjunto.
Los sistemas de restricciones de conjuntos son útiles para describir conjuntos (en particular, infinitos) de términos básicos . [nota 2] Surgen en el análisis de programas, la interpretación abstracta y la inferencia de tipos .
Cada gramática de árbol regular puede transformarse sistemáticamente en un sistema de inclusiones de conjuntos tal que su solución mínima corresponda al lenguaje de árbol de la gramática.
Por ejemplo, la gramática (símbolos terminales y no terminales indicados por iniciales en minúsculas y mayúsculas, respectivamente) con las reglas
se transforma al sistema de inclusión de conjuntos (constantes y variables indicadas con iniciales en minúsculas y mayúsculas, respectivamente):
Este sistema tiene una solución mínima, a saber. (" L ( N )" que denota el lenguaje del árbol correspondiente a la N no terminal en la gramática del árbol anterior):
