Kann Konsumieren / Produzieren in linearer Logik modelliert werden?

8

Die Frage ist, ob es möglich ist, zwei Arten des Zugriffs auf eine Ressource in linearer Logik zu modellieren. Ich weiß, dass zwei Arten von Ressourcen möglich sind, nämlich:

!r r ist unendlich verfügbar r ist nur einmal verfügbar
r

Aber was ist, wenn ich nicht entscheiden möchte, ob r unendlich oder nur einmal verfügbar ist? Und die Abfrage, dh der Zugriff, sollte entscheiden, also:

rr r wird nur überprüft (
sozusagen ! r) * r \ vdash verbrauchen (r)rconsume(r) r wird verbraucht (so wie es allein wäre)

Kann ich einen Verbrauchs- (r) und einen normalen r-Zugriff in linearer Logik modellieren? Ebenso hätte ich gerne einen Erzeuger (r), der dann die Form * r einer Ressource bestätigt.

Kaveh
quelle
Jan, du kannst LaTeX für Mathe in deinen Posts verwenden.
Kaveh
\ otimes und \ multimap (hat einen von Neels Posts überprüft :).
Kaveh
1
@ Jan, ich bin nicht sicher, welches Problem Sie vorschlagen. Wenn Sie eine Konjunktion von Bedingungen beschreiben möchten , sollten Sie die additive Konjunktion & ("mit") verwenden. Die Folge ist in linearer Logik beweisbar. X.p(a,X)p(X,b)p(a,b)X.p(a,X)&p(X,b)
Noam Zeilberger
Meine Antwort hier cstheory.stackexchange.com/questions/5797/… auf eine andere Frage enthält einige Links zu Artikeln über die Planung mit linearer Logik.
Dave Clarke
Wie wäre es mit oder zu modellieren, dass eine Wahl zwischen einem einzelnen oder einer beliebigen Anzahl von ihnen getroffen werden muss? Eine Wahl wird extern getroffen, die andere intern (obwohl ich mich nicht erinnern kann, welche welche ist). r!rr&!rr
Dave Clarke

Antworten:

5

Mit nicht kommutativer linearer Logik (vgl. Retoré 1997 für Pomset-Logik) können Sie die Abfolge der Ressourcenprüfung modellieren und vermeiden, dass die Ressourcenprüfung im Rahmen des von Ihnen gewünschten Auswahloperators erfolgt.

Sie können Ihre Abfrage beispielsweise folgendermaßen modellieren:

(r;ab)(c;r)

Sie könnten dies so interpretieren: Wenn ich nehmen und dann konsumieren kann, kann ich bereitstellen und dann . Ist das die Semantik, die Sie wollen?rabcr

Es sieht leider so aus, als könnten Sie nicht-kommutative lineare Logik nicht mit üblicher linearer Logik in der sequentiellen Berechnung kombinieren und die erforderlichen beweistheoretischen Eigenschaften für die Modellplanung über die Beweissuche beibehalten. Sie können dies tun, indem Sie die Strukturrechnung verwenden (siehe (Strassburger, 2003)), die für die Planung verwendet wurde (Kahramanogullari 2009).

Wenn Sie den Weg gehen möchten, eine Modalität zu haben, die nur dekoriert , kann dies schwierig sein, da Sie im Wesentlichen in der Lage sein möchten, ohne es zu konsumieren und ohne es für unbegrenzte Verwendung verfügbar zu haben, was keine aussagekräftige Haltung ist der regulären linearen Logik. Sie können versuchen zu sehen, obtr

((?ra)(?rb))c

funktioniert für Sie, wird es aber wahrscheinlich nicht, weil billiger ist als - es ist ein bisschen wie eine Referenz ro ; und stellt so nicht sicher, dass Sie Ihre Hände auf legen können . funktioniert möglicherweise besser und ist die Grundlage für die beiden Codierungen, die zur Modellierung der klassischen Logik in der linearen Logik verwendet werden. zu haben bedeutet jedoch nicht, dass Sie bereitstellen können . Ein Blick auf eines der verschiedenen schwachen Exponentiale für die lineare Logik könnte hier hilfreich sein.?rrrr?!rr?!r

Verweise

  1. Retoré 1997, Pomset-Logik: eine nicht kommutative Erweiterung der klassischen linearen Logik
  2. Strassburger 2003, Lineare Logik und Nichtkommutativität in der Strukturrechnung
  3. Kahramanogullari 2009, Über lineare Logikplanung und Parallelität, Information und Berechnung 207: 1229 - 1258.
Charles Stewart
quelle