Quelle est l'intuition derrière la logique linéaire?

J'essaie de comprendre la logique linéaire pour mieux comprendre les systèmes de type linéaire. Cependant, quand je lis les règles, je ne parviens pas à avoir une intuition comme je l'ai fait dans la logique modale - signifie est requis comme dans les cadres Kripke est requis pour chaque monde accessible [ est est mutatis possible mutandis]. Mais je ne trouve aucune explication intuitive de la dualité et laquelle des paires conjonction / disjonction (le cas échéant) correspond à et . $\Box A$ $A$ $A$ $\Diamond A$ $A$ $\land$ $\lor$

lo.logic type-theory linear-logic Maciej Piechotka
la source

Le papier original de Girard est l'endroit où vous devriez regarder si vous voulez comprendre l'intuition derrière eux. La question en l'état est trop générale et la réponse serait de regarder la page Wikipedia pour la logique linéaire.

Kaveh

Je suis d'accord que c'est un peu trop de pain et certainement pas au niveau de la recherche, peut-être que vous devriez poser la question sur CS Stack Exchange. Cependant, je vous découragerais d'utiliser le papier original de Girard comme point d'entrée de la logique linéaire. Peut-être que Wikipedia est un meilleur endroit pour commencer.

Damiano Mazza

C'est assez large. Une suggestion pourrait peut-être commencer à considérer les formules comme une "monnaie" qui peut être dépensée, au lieu de déclarations de vérité. Ensuite, la conjonction pourrait être

qui signifie que nous pouvons passer à la fois une

pièce de monnaie et une

pièce. Un autre type de conjonction pourrait être

, ce qui signifie que nous pouvons choisir entre dépenser

et dépenser

(mais pas les deux!). Vous pouvez trouver quelques exemples sur Wikipedia, comme l'a suggéré Damiano.

a \otimes b

$a \otimes b$

a

$a$

b

$b$

a & b

$a \& b$

a

$a$

b

$b$

chi

@chi Je ne suis pas sûr que "l'interprétation des ressources" soit la meilleure façon de comprendre la dualité en LL. L'interprétation du processus est beaucoup plus compréhensible.

Martin Berger

Réponses:

Je ne suis pas sûr que cette question soit idéale pour CSTheory, mais étant donné qu'elle recueille déjà des votes positifs, voici une réponse que quelqu'un aurait pu donner si la question avait été publiée sur cs.stackexchange .

$(\cdot)^{\bot}$ $A$

$A \otimes B$ $A$ $B$ $A \otimes B$ $(a, b)$ $a$ $A$ $b$ $B$

$(.)^{\bot}$ $A \otimes B$

(A \otimes B)^{⊥} = A^{⊥} ⅋ B^{⊥}

$(A \otimes B)^{\bot} \quad = \quad A^{\bot} ⅋ B^{\bot}$

Dans cette lecture est le processus qui communique avec . $A^{\bot} ⅋ B^{\bot}$ $A \otimes B$

L'équivalent de disjonction de la logique linéaire peut recevoir une lecture similaire de la théorie des processus. La formule

A & B

$A\ \&\ B$

devrait également être considéré comme deux processus et en parallèle, mais plutôt que d'envoyer activement des messages, ils attendent que l'environnement décide lequel exécuter. Donc est assis là, attendant sur son canal pour un bit d'information qui décide si devrait fonctionner comme ou . Il s'agit d'une version «parallèle» de dans les langages de programmation séquentiels. Le dual de est $A$ $B$ $A \& B$ $A \& B$ $A$ $B$ $if/then/else$ $(A \& B)^{\bot}$ $A \& B$

(A & B)^{⊥} = A^{⊥} \oplus B^{⊥}

$(A \& B)^{\bot} \quad = \quad A^{\bot} \oplus B^{\bot}$

peut être vu comme un processus envoyant 1 bit d'information à , à savoir: "continuer comme " ou "continuer comme ". Ceci est similaire à dans évaluant à tandis que évaluant à , sauf que le choix entre et est maintenant fait par l'environnement. $A \& B$ $A$ $B$ $if\ true\ then\ P\ else\ Q$ $P$ $if\ false\ then\ P\ else\ Q$ $Q$ $A$ $B$

L'opérateur! A également une interprétation théorique du processus: si est lu comme un processus, alors peut être lu comme exécutant une infinité de processus en parallèle.

A

$A$

! A

$!A$

A

$A$

Dans cette lecture , les axiomes la logique linéaire deviennent des « fils » de simples messages avant de processus aux processus . Cette interprétation des axiomes est déjà dans les réseaux de preuve de Girard (3). $A \vdash A$ $A^{\bot}$ $A$

Cette interprétation théorique du processus a été influente et a donné lieu à de nombreux travaux de suivi comme par exemple (2) pour les types de session. Néanmoins, il y a quelques cas de bord qui le rendent un peu gênant, et à ma connaissance, il n'a pas été conçu pour fonctionner parfaitement pour une logique linéaire complète , même en 2017.

_{1. S. Abramsky, Interprétations computationnelles de la logique linéaire .

2. P. Wadler, Propositions as sessions .

3. Wikipédia, filet de preuve .}

Martin Berger
la source