Sistema de información Scott

En la teoría de dominios , una rama de las matemáticas y la informática , un sistema de información de Scott es un tipo primitivo de sistema deductivo lógico que a menudo se utiliza como una forma alternativa de presentar los dominios de Scott .

Un sistema de información de Scott , A , es un triple ordenado${\displaystyle (T,Con,\vdash )}$

• ${\displaystyle T{\mbox{ es un conjunto de tokens (las unidades básicas de información)}}}$
• ${\displaystyle Con\subseteq {\mathcal {P}}_{f}(T){\mbox{ los subconjuntos finitos de }}T}$
• ${\displaystyle {\vdash}\subseteq (Con\setminus \lbrace \emptyset \rbrace )\times T}$

satisfactorio

1. ${\displaystyle {\mbox{Si }}a\in X\in Con{\mbox{ entonces }}X\vdash a}$
2. ${\displaystyle {\mbox{Si }}X\vdash Y{\mbox{ y }}Y\vdash a{\mbox{, entonces }}X\vdash a}$
3. ${\displaystyle {\mbox{Si }}X\vdash a{\mbox{ entonces }}X\cup \{a\}\in Con}$
4. ${\displaystyle \para todo a\en T:\{a\}\en Con}$
5. ${\displaystyle {\mbox{Si }}X\in Con{\mbox{ y }}X^{\prime }\,\subseteq X{\mbox{ entonces }}X^{\prime }\in Con.}$

Aquí significa${\displaystyle X\vdash Y}$${\displaystyle \paratodo a\en Y,X\vdash a.}$

El valor de retorno de una función recursiva parcial , que devuelve un número natural o realiza una recursión infinita, se puede expresar como un sistema de información de Scott simple de la siguiente manera:

• ${\displaystyle T:=\mathbb {N}}$
• ${\displaystyle Con:=\{\conjunto vacío \}\cup \{\{n\}\mid n\in \mathbb {N} \}}$
• ${\displaystyle X\vdash a\iff a\in X.}$

Es decir, el resultado puede ser un número natural, representado por el conjunto singleton , o una "recursión infinita", representada por . ${\estilo de visualización \{n\}}$${\displaystyle \conjunto vacío}$

Por supuesto, la misma construcción se puede realizar con cualquier otro conjunto en lugar de . ${\displaystyle \mathbb {N}}$

El cálculo proposicional nos da un sistema de información de Scott muy simple como sigue:

• ${\displaystyle T:=\{\phi \mid \phi {\mbox{ es satisfacible}}\}}$
• ${\displaystyle Con:=\{X\in {\mathcal {P}}_{f}(T)\mid X{\mbox{ es consistente}}\}}$
• ${\displaystyle X\vdash a\iff X\vdash a{\mbox{ en el cálculo proposicional}}.}$

Sea D un dominio de Scott . Entonces podemos definir un sistema de información de la siguiente manera

• $estilo de visualización T:=D^{0}}$el conjunto de elementos compactos de${\estilo de visualización D}$
• ${\displaystyle Con:=\{X\in {\mathcal {P}}_{f}(T)\mid X{\mbox{ tiene un límite superior}}\}}$
• ${\displaystyle X\vdash d\iff d\sqsubseteq \bigsqcup X.}$

Sea la función que nos lleva desde un dominio de Scott, D , al sistema de información definido anteriormente. ${\displaystyle {\mathcal {I}}}$

Dado un sistema de información, , podemos construir un dominio Scott de la siguiente manera. ${\displaystyle A=(T,Con,\vdash )}$

• Definición: es un punto si y sólo si ${\displaystyle x\subseteq T}$
  • ${\displaystyle {\mbox{Si }}X\subseteq _{f}x{\mbox{ entonces }}X\in Con}$
  • ${\displaystyle {\mbox{Si }}X\vdash a{\mbox{ y }}X\subseteq _{f}x{\mbox{ entonces }}a\in x.}$

Sea el conjunto de puntos de A con el orden de subconjuntos. será un dominio de Scott de base numerable cuando T sea numerable. En general, para cualquier dominio de Scott D y sistema de información A${\displaystyle {\mathcal {D}}(A)}$${\displaystyle {\mathcal {D}}(A)}$

• ${\displaystyle {\mathcal {D}}({\mathcal {I}}(D))\cong D}$
• ${\displaystyle {\mathcal {I}}({\mathcal {D}}(A))\cong A}$

donde la segunda congruencia se da mediante aplicaciones aproximables.

• Dominio Scott
• Teoría de dominios

• Glynn Winskel: "La semántica formal de los lenguajes de programación: una introducción", MIT Press, 1993 (capítulo 12)