← All problems
Unverified

Is the extension of Combinatory Logic by Boolean constants confluent?

The source page states the original problem together with its recorded qualifications and progress updates as follows.

Consider the following extension of Combinatory Logic with constants TT (true), FF (false), CC (conditional):

Ix→xKxy→xSxyz→(xz)(yz)CTxy→xCFxy→yx↔∗y⇒Czxy→x\begin{aligned} Ix & \rightarrow & x\\ Kxy & \rightarrow & x\\ Sxyz & \rightarrow & (xz)(yz)\\ CTxy & \rightarrow & x\\ CFxy & \rightarrow & y\\ x \leftrightarrow^* y \Rightarrow Czxy & \rightarrow & x \end{aligned}

Is this (non-terminating) semi-equational'' (or natural'', as such are called in [Toyama, 1991]) conditional rewrite system confluent? Note that if we take the above system plus the rule x↔∗y⇒Czxy→yx \leftrightarrow^* y \Rightarrow Czxy \rightarrow y, the resulting conditional rewrite system is confluent (cf. [Toyama, 1991]).

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu