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

11

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 A est requis comme dans les cadres Kripke A est requis pour chaque monde accessible [ A est A 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 .AAAAA

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
5
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 une pièce de monnaie et une b pièce. Un autre type de conjonction pourrait être a & b , ce qui signifie que nous pouvons choisir entre dépenser a et dépenser b (mais pas les deux!). Vous pouvez trouver quelques exemples sur Wikipedia, comme l'a suggéré Damiano. ababa&bab
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:

11

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 .

()A

                    Processus

ABABAB (a,b)aAbB

                   entrez la description de l'image ici

(.)AB

(AB)=AB

Dans cette lecture est le processus qui communique avec .ABAB

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

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 estABA&BA&BABif/then/else(A&B)A&B

(A&B)=AB

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&BABif true then P else QPif false then P else QQAB

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!AA

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).AAAA

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