Sistema de información Scott

Sistema lógico deductivo

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 .

Definición

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

• ${\displaystyle T{\mbox{ is a set of tokens (the basic units of information)}}}$
• ${\displaystyle Con\subseteq {\mathcal {P}}_{f}(T){\mbox{ the finite subsets of }}T}$
• ${\displaystyle {\vdash }\subseteq (Con\setminus \lbrace \emptyset \rbrace )\times T}$

satisfactorio

1. ${\displaystyle {\mbox{If }}a\in X\in Con{\mbox{ then }}X\vdash a}$
2. ${\displaystyle {\mbox{If }}X\vdash Y{\mbox{ and }}Y\vdash a{\mbox{, then }}X\vdash a}$
3. ${\displaystyle {\mbox{If }}X\vdash a{\mbox{ then }}X\cup \{a\}\in Con}$
4. ${\displaystyle \forall a\in T:\{a\}\in Con}$
5. ${\displaystyle {\mbox{If }}X\in Con{\mbox{ and }}X^{\prime }\,\subseteq X{\mbox{ then }}X^{\prime }\in Con.}$

Aquí significa ${\displaystyle X\vdash Y}$ ${\displaystyle \forall a\in Y,X\vdash a.}$

Ejemplos

Números naturales

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:=\{\emptyset \}\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 . ${\displaystyle \{n\}}$ ${\displaystyle \emptyset }$

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

Cálculo proposicional

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

• ${\displaystyle T:=\{\phi \mid \phi {\mbox{ is satisfiable}}\}}$
• ${\displaystyle Con:=\{X\in {\mathcal {P}}_{f}(T)\mid X{\mbox{ is consistent}}\}}$
• ${\displaystyle X\vdash a\iff X\vdash a{\mbox{ in the propositional calculus}}.}$

Dominios de Scott

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

• ${\displaystyle T:=D^{0}}$el conjunto de elementos compactos de ${\displaystyle D}$
• ${\displaystyle Con:=\{X\in {\mathcal {P}}_{f}(T)\mid X{\mbox{ has an upper bound}}\}}$
• ${\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}}}$

Sistemas de información y dominios Scott

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{If }}X\subseteq _{f}x{\mbox{ then }}X\in Con}$
  • ${\displaystyle {\mbox{If }}X\vdash a{\mbox{ and }}X\subseteq _{f}x{\mbox{ then }}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.

Véase también

• Dominio Scott
• Teoría de dominios

Referencias

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