Church-Rosser-Eigenschaft für abhängig typisierten Lambda-Kalkül?

Es ist bekannt, dass die Church-Rosser-Eigenschaft für die -Reduktion in einfach typisierter Lambda-Rechnung gilt. Dies impliziert, dass der Kalkül in dem Sinne konsistent ist, dass nicht alle Gleichungen mit Termen ableitbar sind: zum Beispiel K I , da sie nicht dieselbe Normalform haben.λ $\beta \eta$$\lambda$$\neq$

Es ist auch bekannt, das Ergebnis auf Paare zu erweitern, die den Produkttypen entsprechen.

Aber ich frage mich, ob man das Ergebnis für abhängig typisierten Lambda-Kalkül (vielleicht) mit polymorphen Typen, z. B. dem Konstruktionskalkül, noch erweitern kann.

Referenzen wären auch super!

Vielen Dank

Es könnte nützlich sein, das Gegenbeispiel zu CR in typisierten Kalkülen mit und η schnell anzugeben :$\beta$$\eta$

$$t=\lambda x:A.(\lambda y:B.\ y)\ x$$

Und wir haben und t → & eegr; & lgr; y : B .

$$t\rightarrow_\beta \lambda x: A.x$$ $$t\rightarrow_\eta \lambda y:B.y$$

Es ist sofort , dass , wenn , dann werden die beiden resultierenden Begriffe sind in der Tat, & agr; äquivalent, aber es gibt keinen Grund dafür auf der Fall zu sein , nicht typisierten Bedingungen.$A\equiv B$$\alpha$

Bei typisierten Begriffen ist es ziemlich klar, dass gleich B sein muss, damit der resultierende Term t gut typisiert wird. Die große Schwierigkeit, die auftritt, ist die folgende:$A$$B$$t$

Bei typabhängigen Systemen muss die Konfluenz vor dem Erhalt des Typs nachgewiesen werden!

$\Pi$

$$\Pi x:A.B=_{\beta\eta}\Pi x:A'.B'\ \Leftrightarrow\ A=_{\beta\eta}A'\wedge B=_{\beta\eta} B'$$

$\beta\eta$

$\eta$$\eta$$t\rightarrow_{\eta*}\lambda x:A.t\ x$

$\lambda$

Ein anderer und in letzter Zeit recht populärer Ansatz wird von Abel, Untyped Algorithmic Equality für Martin-Löfs Logical Framework with Surjective Pairs, beschrieben .

$\lambda$

• PTS mit nur β-Reduktion erfüllen CR unter typisierten Bedingungen. Dies folgt unmittelbar aus CR zu 'Pseudoterms' zusammen mit der Subjektreduktion.

• Für PTS mit βη-Reduktion ist CR auf der Menge von Pseudoterms falsch. Siehe (2).

• In PTS mit βη-Reduktion gilt CR für gut typisierte Terme eines festen Typs . Siehe (1).

PTS sind sehr allgemeine Formalismen und umfassen System F, Fω, LF sowie die Berechnung von Konstruktionen. Die letzten beiden sind abhängig von der Schreibweise. Beide (1, 2) sind ziemlich alte Papiere, und ich stelle mir vor, dass 2015 mehr bekannt ist.

---

^$\lambda$

^{2. RP Nederpelt, Starke Normalisierung in einem typisierten Lambda-Kalkül mit Lambda-strukturierten Typen .}