# Publications on Confluence

## 2018

- Decreasing Diagrams with Two Labels Are Complete for Confluence of Countable SystemsJörg Endrullis, Jan Willem Klop, and Roy OverbeekIn: Proc. Conf. on Formal Structures for Computation and Deduction (FSCD 2018), pp. 14:1–14:15, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)
# Abstract

The decreasing diagrams technique is one of the strongest and most versatile methods for proving confluence of abstract reduction systems. So what makes decreasing diagrams so powerful? In contrast to other confluence techniques, decreasing diagrams employ a labelling of the steps.

In this paper we investigate how the size of the label set influences the strength of the technique. Surprisingly, we find that two labels suffice for proving confluence of every confluent, countable system. In contrast, for proving commutation of rewrite relations, it turns out that the strength of the technique increases with more labels.

While decreasing diagrams is complete for proving confluence of countable systems, the technique is not complete for commutation. In our paper De Bruijn's Weak Diamond Property Revisited we give a counterexample to the completeness of decreasing diagrams for commutation.

@inproceedings{confluence:decreasing:diagrams:2018, author = {Endrullis, J{\"{o}}rg and Klop, Jan Willem and Overbeek, Roy}, title = {{Decreasing Diagrams with Two Labels Are Complete for Confluence of Countable Systems}}, booktitle = {Proc.\ Conf.\ on Formal Structures for Computation and Deduction (FSCD~2018)}, volume = {108}, pages = {14:1--14:15}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, year = {2018}, doi = {10.4230/LIPIcs.FSCD.2018.14}, keywords = {rewriting, confluence}, type = {conference} }

## 2013

- De Bruijn’s Weak Diamond Property RevisitedJörg Endrullis, and Jan Willem KlopIndagationes Mathematicae , 24 (4) , pp. 1050–1072 (2013)
@article{confluence:weak:diamond:2013, author = {Endrullis, J\"{o}rg and Klop, Jan Willem}, title = {{De Bruijn’s Weak Diamond Property Revisited}}, journal = {Indagationes Mathematicae}, volume = {24}, number = {4}, pages = {1050 -- 1072}, year = {2013}, note = {In memory of N.G. (Dick) de Bruijn (1918–2012)}, keywords = {rewriting, confluence}, type = {journal} }

## 2011

- Levels of Undecidability in RewritingJörg Endrullis, Herman Geuvers, Jakob Grue Simonsen, and Hans ZantemaInformation and Computation , 209 (2) , pp. 227–245 (2011)
# Abstract

Undecidability of various properties of first-order term rewriting systems is well-known. An undecidable property can be classified by the complexity of the formula defining it. This classification gives rise to a hierarchy of distinct levels of undecidability, starting from the arithmetical hierarchy classifying properties using first order arithmetical formulas, and continuing into the analytic hierarchy, where quantification over function variables is allowed.

In this paper we give an overview of how the main properties of first-order term rewriting systems are classified in these hierarchies. We consider properties related to normalization (strong normalization, weak normalization and dependency problems) and properties related to confluence (confluence, local confluence and the unique normal form property). For all of these we distinguish between the single term version and the uniform version. Where appropriate, we also distinguish between ground and open terms.

Most uniform properties are \( \Pi^0_2 \)-complete. The particular problem of local confluence turns out to be \( \Pi^0_2 \)-complete for ground terms, but only \( \Sigma^0_1 \)-complete (and thereby recursively enumerable) for open terms. The most surprising result concerns dependency pair problems without minimality flag: we prove this problem to be \( \Pi^1_1 \)-complete, hence not in the arithmetical hierarchy, but properly in the analytic hierarchy.

This paper is an extended version of

*Degrees of Undecidability in Term Rewriting*(CSL 2009).@article{rewriting:undecidability:levels:2011, author = {Endrullis, J\"{o}rg and Geuvers, Herman and Simonsen, Jakob Grue and Zantema, Hans}, title = {{Levels of Undecidability in Rewriting}}, journal = {Information and Computation}, volume = {209}, number = {2}, pages = {227--245}, year = {2011}, doi = {10.1016/j.ic.2010.09.003}, keywords = {rewriting, undecidability, termination, confluence}, type = {journal} }

## 2009

- Degrees of Undecidability in Term RewritingJörg Endrullis, Herman Geuvers, and Hans ZantemaIn: Proc. Conf. on Computer Science Logic (CSL 2009), pp. 255–270, Springer (2009)
# Abstract

Undecidability of various properties of first-order term rewriting systems is well-known. An undecidable property can be classified by the complexity of the formula defining it. This classification gives rise to a hierarchy of distinct levels of undecidability, starting from the arithmetical hierarchy classifying properties using first order arithmetical formulas, and continuing into the analytic hierarchy, where quantification over function variables is allowed.

In this paper we give an overview of how the main properties of first-order term rewriting systems are classified in these hierarchies. We consider properties related to normalization (strong normalization, weak normalization and dependency problems) and properties related to confluence (confluence, local confluence and the unique normal form property). For all of these we distinguish between the single term version and the uniform version. Where appropriate, we also distinguish between ground and open terms.

Most uniform properties are \( \Pi^0_2 \)-complete. The particular problem of local confluence turns out to be \( \Pi^0_2 \)-complete for ground terms, but only \( \Sigma^0_1 \)-complete (and thereby recursively enumerable) for open terms. The most surprising result concerns dependency pair problems without minimality flag: we prove this problem to be \( \Pi^1_1 \)-complete, hence not in the arithmetical hierarchy, but properly in the analytic hierarchy.

We refer to

*Levels of Undecidability in Rewriting*(Information and Computation 2011) for an extended journal version of this paper.@inproceedings{rewriting:undecidability:degrees:2009, author = {Endrullis, J\"{o}rg and Geuvers, Herman and Zantema, Hans}, title = {{Degrees of Undecidability in Term Rewriting}}, booktitle = {Proc.\ Conf.\ on Computer Science Logic (CSL~2009)}, volume = {5771}, pages = {255--270}, publisher = {Springer}, series = {LNCS}, year = {2009}, doi = {10.1007/978-3-642-04027-6\_20}, keywords = {rewriting, undecidability, termination, confluence}, type = {conference} }