Lógica con contracción y debilitamiento limitados.
En su respuesta a esta pregunta , Stephane Giménez me señaló un algoritmo de normalización de tiempo polinómico para pruebas en lógica lineal. La prueba en el documento de Girard utiliza redes de prueba, que son un aspecto de la lógica lineal que realmente no conozco mucho. Ahora, he tratado de...
Probablemente, la aplicación más común de los tipos lineales en PL es usarlos para dar lenguajes que controlen el alias (es decir, un valor lineal tiene un solo puntero, más o menos). Pero hay un ligero desajuste entre este uso y los modelos denotacionales típicos de lógica lineal. IIRC, Benton...
¿La prueba automática de teoremas y la búsqueda de pruebas son más fáciles en lógicas subestructurales lineales y otras proposicionales que carecen de contracción? ¿Dónde puedo leer más sobre la demostración automática de teoremas en estas lógicas y el papel de la contracción en la búsqueda de...
Supongamos que estamos tratando con un lenguaje de programación que admite tipos lineales (los términos de tipo lineal se pueden usar como máximo una vez, por así decirlo). Esto permite tratar algunos efectos computacionales (como la mutación, incluso cambiar el tipo de operando) de una manera que...
Si observa los combinadores recursivos en el cálculo lambda sin tipo, como el combinador Y o el combinador omega: Está claro que todos estos combinadores terminan duplicando una variable en algún lugar de su definición.ωY==( λ x .Xx )( λ x .XX)λ f.( λx .F(xx ))( λ x.F(xx )...
La lógica lineal se interpreta utilizando espacios coherentes , y ocupan un lugar destacado en los documentos de Girard. Conozco las tres formas principales de definirlas formalmente, y realmente no plantean ningún problema para usar y probar cosas, pero no puedo entender lo que significan...
\newcommand{\symp}{\Bumpeq} Una relación de coherencia en un conjunto X es una relación reflexiva y simétrica. Un espacio de coherencia es un par (X, \ symp_X) , y un morfismo f: X \ a Y entre espacios de coherencia es una relación f \ subseteq X \ veces Y tal que para todos (x, y) \ en f y (x ',...
Estoy tratando de entender la lógica lineal para comprender mejor los sistemas de tipo lineal. Sin embargo, cuando leí las reglas, no llego a tener una intuición detrás de él como lo he hecho en la lógica modal - significa un se requiere como en los marcos de Kripke A es necesaria para todos los...
Somos capaces de demostrar teoremas un parametricity gratis sobre funciones como ? Se supone que indica que f toma una lista y siempre devuelve una permutación de la misma.f:∀A.[A]⊸[A]f:∀A.[A]⊸[A]f : \forall A . [A] ⊸ [A]fff Otro ejemplo: probar que la función siempre devolverá una lista permutada...
La pregunta es si es posible modelar en lógica lineal dos modos de acceso a un recurso. Sé que son posibles dos modos de recursos, es decir: !r⊢!r⊢!r \vdash r está infinitamente disponible r solo está disponible una vez r⊢r⊢r \vdash \quad Pero, ¿y si no quiero decidir si r es infinita o solo una...
En la encuesta de Melliès, Semántica categórica de la lógica lineal , se proporciona un procedimiento de eliminación de corte para la lógica lineal intuicionista que incluye el siguiente caso: 3.9.3 Promoción versus contracción La prueba se transforma en la prueba π