Certification Problem

Input (TPDB TRS_Standard/Various_04/06)

The rewrite relation of the following TRS is considered.

f(x,y)	→	g1(x,x,y)	(1)
f(x,y)	→	g1(y,x,x)	(2)
f(x,y)	→	g2(x,y,y)	(3)
f(x,y)	→	g2(y,y,x)	(4)
g1(x,x,y)	→	h(x,y)	(5)
g1(y,x,x)	→	h(x,y)	(6)
g2(x,y,y)	→	h(x,y)	(7)
g2(y,y,x)	→	h(x,y)	(8)
h(x,x)	→	x	(9)

Property / Task

Prove or disprove termination.

Answer / Result

Yes.

Proof (by NaTT @ termCOMP 2023)

1 Dependency Pair Transformation

The following set of initial dependency pairs has been identified.

g1^#(y,x,x)	→	h^#(x,y)	(10)
f^#(x,y)	→	g1^#(x,x,y)	(11)
g2^#(y,y,x)	→	h^#(x,y)	(12)
f^#(x,y)	→	g2^#(x,y,y)	(13)
g2^#(x,y,y)	→	h^#(x,y)	(14)
f^#(x,y)	→	g1^#(y,x,x)	(15)
f^#(x,y)	→	g2^#(y,y,x)	(16)
g1^#(x,x,y)	→	h^#(x,y)	(17)

1.1 Dependency Graph Processor

The dependency pairs are split into 0 components.