On Confluence of Parallel-Innermost Term Rewriting

Thaïs Baudon (1, 2) , Carsten Fuhs (3) , Laure Gonnord (1, 2, 4, 5)

1 LIP - Laboratoire de l'Informatique du Parallélisme
2 CASH - Compilation et Analyse, Logiciel et Matériel
3 Birkbeck College [University of London]
4 LCIS - Laboratoire de Conception et d'Intégration des Systèmes
5 CTSYS - Conception et Test de SYStèmes embarqués

We revisit parallel-innermost term rewriting as a model of parallel computation on inductive data structures. We propose a simple sufficient criterion for confluence of parallelinnermost rewriting based on non-overlappingness. Our experiments on a large benchmark set indicate the practical usefulness of our criterion. We close with a challenge to the community to develop more powerful dedicated techniques for this problem.

Domaines: Algorithme et structure de données [cs.DS]; Complexité [cs.CC]

Thaïs Baudon, Carsten Fuhs, Laure Gonnord. On Confluence of Parallel-Innermost Term Rewriting. IWC 2022 - 11th International Workshop on Confluence, Aug 2022, Haifa, Israel. ⟨hal-03710007v2⟩