Hispanopedia Wiki
Articulo de referencia

Establecer restricción

Restricciones de conjunto obtenidas a partir de la interpretación abstracta del algoritmo de Collatz. En matemáticas e informática teórica , una restricción de conjunto es una e...

Hispanopedia WikiContenido en espanolLectura gratuita
Restricciones de conjunto obtenidas a partir de la interpretación abstracta del algoritmo de Collatz.

En matemáticas e informática teórica , una restricción de conjunto es una ecuación o inecuación entre conjuntos de términos . De forma similar a los sistemas de ecuaciones ( de inecuación ) entre números, se estudian métodos para resolver sistemas de restricciones de conjunto. Los distintos enfoques admiten diferentes operadores (como "∪", "∩", "\" y la aplicación de funciones) [ nota 1 ] sobre 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 .

Relación con las gramáticas de árboles regulares

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úscula y mayúscula, respectivamente) con las reglas

se transforma al sistema de inclusión de conjuntos (constantes y variables indicadas con iniciales en minúscula y mayúscula, respectivamente):

Este sistema tiene una solución mínima, a saber: (" L ( N )" que denota el lenguaje de árbol correspondiente al no terminal N en la gramática de árbol anterior):

La solución máxima del sistema es trivial; asigna el conjunto de todos los términos a cada variable.

Literatura

  • Aiken, A. (1995). Restricciones de conjuntos: resultados, aplicaciones y direcciones futuras (Informe técnico). Univ. Berkeley.
  • Aiken, A., Kozen, D., Vardi, M., Wimmers, EL (mayo de 1993). La complejidad de las restricciones de conjuntos (Informe técnico). Departamento de Ciencias de la Computación, Universidad de Cornell. 93–1352.{{cite tech report}}: CS1 maint: varios nombres: lista de autores ( enlace )
  • Aiken, A., Kozen, D., Vardi, M., Wimmers, EL (1994). "La complejidad de las restricciones de conjuntos". Computer Science Logic'93 . LNCS. Vol.  832. Springer. pp. 1–17 . {{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
  • Aiken, A., Wimmers, EL (1992). "Resolución de sistemas de restricciones de conjuntos (Resumen extendido)". Séptimo Simposio Anual IEEE sobre Lógica en Ciencias de la Computación . págs. 329–340 . {{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
  • Bachmair, Leo, Ganzinger, Harald, Waldmann, Uwe (1992). Las restricciones de conjuntos son la clase monádica (Informe técnico). Instituto Max Planck de Informática. pág.  13. CiteSeerX 10.1.1.32.3739 . MPI-I-92-240. {{cite tech report}}: CS1 maint: varios nombres: lista de autores ( enlace )
  • Bachmair, Leo, Ganzinger, Harald, Waldmann, Uwe (1993). "Las restricciones de conjuntos son la clase monádica". Octavo Simposio Anual del IEEE sobre Lógica en Ciencias de la Computación . págs. 75–83 . {{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
  • Charatonik, W. (septiembre de 1994). "Restricciones de conjuntos en algunas teorías ecuacionales". Actas de la 1.ª Conferencia Internacional sobre Restricciones en Lógicas Computacionales (CCL) . LNCS. Vol.  845. Springer. págs. 304–319 . 
  • Charatonik, Witold; Podelski, Andreas (2002). "Restricciones de conjuntos con intersección" . Información y computación . 179 (2): 213– 229. doi : 10.1006/inco.2001.2952 .
  • Charatonik, W., Podelski, A. (1998). Tobias Nipkow (ed.). Restricciones de conjuntos codefinidos . LNCS 1379. Springer-Verlag. pp. 211–225 . {{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
  • Charatonik, W., Talbot, J.-M. (2002). Tison, S. (ed.). Restricciones de conjuntos atómicos con proyección . LNCS 2378. Springer. pp. 311–325 . {{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
  • Gilleron, R., Tison, S. , Tommasi, M. (1993). "Resolución de sistemas de restricciones de conjuntos mediante autómatas de árbol". 10.º Simposio Anual sobre Aspectos Teóricos de la Informática . LNCS. Vol.  665. Springer. pp. 505–514 . {{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
  • Heintze, N., Jaffar, J. (1990). "Un procedimiento de decisión para una clase de restricciones de conjuntos (resumen extendido)". Quinto Simposio Anual IEEE sobre Lógica en Ciencias de la Computación . págs. 42–51 . {{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
  • Heintze, N., Jaffar, J. (febrero de 1991). Un procedimiento de decisión para una clase de restricciones de conjuntos (informe técnico). Escuela de Ciencias de la Computación, Universidad Carnegie Mellon.{{cite tech report}}: CS1 maint: varios nombres: lista de autores ( enlace )
  • Kozen, D. (1993). "Aspectos lógicos de las restricciones de conjuntos" (PDF) . Computer Science Logic'93 . LNCS. Vol.  832. pp. 175–188 . 
  • Kozen, D. (1994). "Restricciones de conjuntos y programación lógica". CCL . LNCS. Vol.  845.
  • Dexter Kozen (1998). "Restricciones de conjuntos y programación lógica" . Information and Computation . 142 : 2–25 . doi : 10.1006/inco.1997.2694 .
  • Uribe, TE (1992). "Unificación ordenada mediante restricciones de conjuntos" . Actas de CADE–11 . LNCS. Vol.  607. págs. 163–177 . 

Literatura sobre restricciones negativas

  • Aiken, A., Kozen, D., Wimmers, EL (junio de 1993). Decidibilidad de sistemas de restricciones de conjuntos con restricciones negativas (Informe técnico). Departamento de Ciencias de la Computación, Universidad de Cornell. 93–1362.{{cite tech report}}: CS1 maint: varios nombres: lista de autores ( enlace )
  • Charatonik, W., Pacholski, L. (julio de 1994). "Restricciones de conjuntos negativos con igualdad". Noveno Simposio Anual IEEE sobre Lógica en Ciencias de la Computación . págs. 128–136 . {{cite book}}: CS1 maint: varios nombres: lista de autores ( enlace )
  • R. Gilleron; S. Tison ; M. Tommasi (1993). "Resolución de sistemas de restricciones de conjuntos con relaciones de subconjuntos negadas". Actas del 34.º Simposio sobre Fundamentos de la Informática . págs. 372–380 . 
  • Gilleron, R., Tison, S. , Tommasi, M. (1993). Resolución de sistemas de restricciones de conjuntos con relaciones de subconjuntos negadas (Informe técnico). Laboratoire d'Informatique Fondamentale de Lille. IT 247.{{cite tech report}}: CS1 maint: varios nombres: lista de autores ( enlace )
  • Stefansson, K. (agosto de 1993). Los sistemas de restricciones de conjuntos con restricciones negativas son NEXPTIME-completos (Informe técnico). Departamento de Ciencias de la Computación, Universidad de Cornell. 93–1380.
  • Stefansson, K. (1994). "Los sistemas de restricciones de conjuntos con restricciones negativas son NEXPTIME-completos". Noveno Simposio Anual IEEE sobre Lógica en Ciencias de la Computación . págs. 137–141 . 

Notas

  1. ↑ Si f es un símbolo de función n-aria admitido en un término, entonces " f ( E 1 ,..., E n )" es una expresión de conjunto que denota el conjunto { f ( t 1 ,..., t n ) : t 1 ∈ E 1 y ... y t n ∈ E n }, donde E 1 ,..., E n son expresiones de conjunto a su vez.
  2. ↑ Esto es similar a describir, por ejemplo, un número racional como solución de una ecuación a ⋅ x + b = 0, concoeficientes enteros a , b .