← All problems
Unverified

Under what conditions does confluence of a normal semi-equational conditional term rewriting system imply confluence of the associated oriented system?

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

For a normal conditional term-rewriting system R={s→!t⇒l→r}R = \{ s \rightarrow^! t \Rightarrow l \rightarrow r \}, where tt must be a ground normal from of ss, we can consider the corresponding semi-equational conditional rewrite system Rse={s↔∗t⇒l→r}R_{se} = \{ s \leftrightarrow^* t \Rightarrow l \rightarrow r \}. Under what conditions does confluence of RseR_{se} imply confluence of RR? In general, this is not the case, as can be seen from the following non-confluent system RR (due to Aart Middeldorp):

a→ba→cb→!c⇒b→c\begin{aligned} a \rightarrow b\\ a \rightarrow c\\ b \rightarrow^! c \Rightarrow b \rightarrow c \end{aligned}

Recorded progress.

Solutions have been provided by [Toyama, 1991]. They show that confluence of RR follows from confluence of RseR_{se} if any of the two following conditions is satisfied: \begin{itemize}

  1. RseR_{se} is semi-decreasing

  2. RseR_{se} is level-confluent \end{itemize} See [Toyama, 1991] for definitions of these properties.

Coming soon

Organizer

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