6.02/2.39	YES
6.02/2.40	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
6.02/2.40	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.02/2.40	
6.02/2.40	
6.02/2.40	Termination of the given ETRS could be proven:
6.02/2.40	
6.02/2.40	(0) ETRS
6.02/2.40	(1) EquationalDependencyPairsProof [EQUIVALENT, 5 ms]
6.02/2.40	(2) EDP
6.02/2.40	(3) EDPPoloProof [EQUIVALENT, 15 ms]
6.02/2.40	(4) EDP
6.02/2.40	(5) EDPPoloProof [EQUIVALENT, 0 ms]
6.02/2.40	(6) EDP
6.02/2.40	(7) PisEmptyProof [EQUIVALENT, 0 ms]
6.02/2.40	(8) YES
6.02/2.40	
6.02/2.40	
6.02/2.40	----------------------------------------
6.02/2.40	
6.02/2.40	(0)
6.02/2.40	Obligation:
6.02/2.40	Equational rewrite system:
6.02/2.40	The TRS R consists of the following rules:
6.02/2.40	
6.02/2.40	   times(plus(x, y), z) -> plus(times(x, z), times(y, z))
6.02/2.40	   times(z, plus(x, f(y))) -> times(g(z, y), plus(x, a))
6.02/2.40	
6.02/2.40	The set E consists of the following equations:
6.02/2.40	
6.02/2.40	   plus(x, y) == plus(y, x)
6.02/2.40	   times(x, y) == times(y, x)
6.02/2.40	   plus(plus(x, y), z) == plus(x, plus(y, z))
6.02/2.40	   times(times(x, y), z) == times(x, times(y, z))
6.02/2.40	
6.02/2.40	
6.02/2.40	----------------------------------------
6.02/2.40	
6.02/2.40	(1) EquationalDependencyPairsProof (EQUIVALENT)
6.02/2.40	Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem:
6.02/2.40	The TRS P consists of the following rules:
6.02/2.40	
6.02/2.40	   TIMES(plus(x, y), z) -> TIMES(x, z)
6.02/2.40	   TIMES(plus(x, y), z) -> TIMES(y, z)
6.02/2.40	   TIMES(z, plus(x, f(y))) -> TIMES(g(z, y), plus(x, a))
6.02/2.40	   TIMES(times(plus(x, y), z), ext) -> TIMES(plus(times(x, z), times(y, z)), ext)
6.02/2.40	   TIMES(times(plus(x, y), z), ext) -> TIMES(x, z)
6.02/2.40	   TIMES(times(plus(x, y), z), ext) -> TIMES(y, z)
6.02/2.40	   TIMES(times(z, plus(x, f(y))), ext) -> TIMES(times(g(z, y), plus(x, a)), ext)
6.02/2.40	   TIMES(times(z, plus(x, f(y))), ext) -> TIMES(g(z, y), plus(x, a))
6.02/2.40	
6.02/2.40	The TRS R consists of the following rules:
6.02/2.40	
6.02/2.40	   times(plus(x, y), z) -> plus(times(x, z), times(y, z))
6.02/2.40	   times(z, plus(x, f(y))) -> times(g(z, y), plus(x, a))
6.02/2.40	   times(times(plus(x, y), z), ext) -> times(plus(times(x, z), times(y, z)), ext)
6.02/2.40	   times(times(z, plus(x, f(y))), ext) -> times(times(g(z, y), plus(x, a)), ext)
6.02/2.40	
6.02/2.40	The set E consists of the following equations:
6.02/2.40	
6.02/2.40	   plus(x, y) == plus(y, x)
6.02/2.40	   times(x, y) == times(y, x)
6.02/2.40	   plus(plus(x, y), z) == plus(x, plus(y, z))
6.02/2.40	   times(times(x, y), z) == times(x, times(y, z))
6.02/2.40	
6.02/2.40	The set E# consists of the following equations:
6.02/2.40	
6.02/2.40	   TIMES(x, y) == TIMES(y, x)
6.02/2.40	   TIMES(times(x, y), z) == TIMES(x, times(y, z))
6.02/2.40	
6.02/2.40	We have to consider all minimal (P,E#,R,E)-chains
6.02/2.40	
6.02/2.40	----------------------------------------
6.02/2.40	
6.02/2.40	(2)
6.02/2.40	Obligation:
6.02/2.40	The TRS P consists of the following rules:
6.02/2.40	
6.02/2.40	   TIMES(plus(x, y), z) -> TIMES(x, z)
6.02/2.40	   TIMES(plus(x, y), z) -> TIMES(y, z)
6.02/2.40	   TIMES(z, plus(x, f(y))) -> TIMES(g(z, y), plus(x, a))
6.02/2.40	   TIMES(times(plus(x, y), z), ext) -> TIMES(plus(times(x, z), times(y, z)), ext)
6.02/2.40	   TIMES(times(plus(x, y), z), ext) -> TIMES(x, z)
6.02/2.40	   TIMES(times(plus(x, y), z), ext) -> TIMES(y, z)
6.02/2.40	   TIMES(times(z, plus(x, f(y))), ext) -> TIMES(times(g(z, y), plus(x, a)), ext)
6.02/2.40	   TIMES(times(z, plus(x, f(y))), ext) -> TIMES(g(z, y), plus(x, a))
6.02/2.40	
6.02/2.40	The TRS R consists of the following rules:
6.02/2.40	
6.02/2.40	   times(plus(x, y), z) -> plus(times(x, z), times(y, z))
6.02/2.40	   times(z, plus(x, f(y))) -> times(g(z, y), plus(x, a))
6.02/2.40	   times(times(plus(x, y), z), ext) -> times(plus(times(x, z), times(y, z)), ext)
6.02/2.40	   times(times(z, plus(x, f(y))), ext) -> times(times(g(z, y), plus(x, a)), ext)
6.02/2.40	
6.02/2.40	The set E consists of the following equations:
6.02/2.40	
6.02/2.40	   plus(x, y) == plus(y, x)
6.02/2.40	   times(x, y) == times(y, x)
6.02/2.40	   plus(plus(x, y), z) == plus(x, plus(y, z))
6.02/2.40	   times(times(x, y), z) == times(x, times(y, z))
6.02/2.40	
6.02/2.40	The set E# consists of the following equations:
6.02/2.40	
6.02/2.40	   TIMES(x, y) == TIMES(y, x)
6.02/2.40	   TIMES(times(x, y), z) == TIMES(x, times(y, z))
6.02/2.40	
6.02/2.40	We have to consider all minimal (P,E#,R,E)-chains
6.02/2.40	----------------------------------------
6.02/2.40	
6.02/2.40	(3) EDPPoloProof (EQUIVALENT)
6.02/2.40	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented.
6.02/2.40	
6.02/2.40	
6.02/2.40	   TIMES(plus(x, y), z) -> TIMES(x, z)
6.02/2.40	   TIMES(plus(x, y), z) -> TIMES(y, z)
6.02/2.40	   TIMES(z, plus(x, f(y))) -> TIMES(g(z, y), plus(x, a))
6.02/2.40	   TIMES(times(plus(x, y), z), ext) -> TIMES(x, z)
6.02/2.40	   TIMES(times(plus(x, y), z), ext) -> TIMES(y, z)
6.02/2.40	   TIMES(times(z, plus(x, f(y))), ext) -> TIMES(times(g(z, y), plus(x, a)), ext)
6.02/2.40	   TIMES(times(z, plus(x, f(y))), ext) -> TIMES(g(z, y), plus(x, a))
6.02/2.40	The remaining Dependency Pairs were at least non-strictly oriented.
6.02/2.40	
6.02/2.40	
6.02/2.40	   TIMES(times(plus(x, y), z), ext) -> TIMES(plus(times(x, z), times(y, z)), ext)
6.02/2.40	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
6.02/2.40	
6.02/2.40	
6.02/2.40	   times(z, plus(x, f(y))) -> times(g(z, y), plus(x, a))
6.02/2.40	   times(times(plus(x, y), z), ext) -> times(plus(times(x, z), times(y, z)), ext)
6.02/2.40	   times(times(z, plus(x, f(y))), ext) -> times(times(g(z, y), plus(x, a)), ext)
6.02/2.40	   times(plus(x, y), z) -> plus(times(x, z), times(y, z))
6.02/2.40	We had to orient the following equations of E# equivalently.
6.02/2.40	
6.02/2.40	
6.02/2.40	   TIMES(x, y) == TIMES(y, x)
6.02/2.40	   TIMES(times(x, y), z) == TIMES(x, times(y, z))
6.02/2.40	With the implicit AFS we had to orient the following usable equations of E equivalently.
6.02/2.40	
6.02/2.40	
6.02/2.40	   times(x, y) == times(y, x)
6.02/2.40	   times(times(x, y), z) == times(x, times(y, z))
6.02/2.40	   plus(plus(x, y), z) == plus(x, plus(y, z))
6.02/2.40	   plus(x, y) == plus(y, x)
6.02/2.40	Used ordering: POLO with Polynomial interpretation [POLO]:
6.02/2.40	
6.02/2.40	   POL(TIMES(x_1, x_2)) = x_1 + x_1*x_2 + x_2
6.02/2.40	   POL(a) = 0
6.02/2.40	   POL(f(x_1)) = 1
6.02/2.40	   POL(g(x_1, x_2)) = 0
6.02/2.40	   POL(plus(x_1, x_2)) = 1 + x_1 + x_2
6.02/2.40	   POL(times(x_1, x_2)) = x_1 + x_1*x_2 + x_2
6.02/2.40	
6.02/2.40	
6.02/2.40	----------------------------------------
6.02/2.40	
6.02/2.40	(4)
6.02/2.40	Obligation:
6.02/2.40	The TRS P consists of the following rules:
6.02/2.40	
6.02/2.40	   TIMES(times(plus(x, y), z), ext) -> TIMES(plus(times(x, z), times(y, z)), ext)
6.02/2.40	
6.02/2.40	The TRS R consists of the following rules:
6.02/2.40	
6.02/2.40	   times(plus(x, y), z) -> plus(times(x, z), times(y, z))
6.02/2.40	   times(z, plus(x, f(y))) -> times(g(z, y), plus(x, a))
6.02/2.40	   times(times(plus(x, y), z), ext) -> times(plus(times(x, z), times(y, z)), ext)
6.02/2.40	   times(times(z, plus(x, f(y))), ext) -> times(times(g(z, y), plus(x, a)), ext)
6.02/2.40	
6.02/2.40	The set E consists of the following equations:
6.02/2.40	
6.02/2.40	   plus(x, y) == plus(y, x)
6.02/2.40	   times(x, y) == times(y, x)
6.02/2.40	   plus(plus(x, y), z) == plus(x, plus(y, z))
6.02/2.40	   times(times(x, y), z) == times(x, times(y, z))
6.02/2.40	
6.02/2.40	The set E# consists of the following equations:
6.02/2.40	
6.02/2.40	   TIMES(x, y) == TIMES(y, x)
6.02/2.40	   TIMES(times(x, y), z) == TIMES(x, times(y, z))
6.02/2.40	
6.02/2.40	We have to consider all minimal (P,E#,R,E)-chains
6.02/2.40	----------------------------------------
6.02/2.40	
6.02/2.40	(5) EDPPoloProof (EQUIVALENT)
6.02/2.40	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented.
6.02/2.40	
6.02/2.40	
6.02/2.40	   TIMES(times(plus(x, y), z), ext) -> TIMES(plus(times(x, z), times(y, z)), ext)
6.02/2.40	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
6.02/2.40	
6.02/2.40	
6.02/2.40	   times(z, plus(x, f(y))) -> times(g(z, y), plus(x, a))
6.02/2.40	   times(times(plus(x, y), z), ext) -> times(plus(times(x, z), times(y, z)), ext)
6.02/2.40	   times(times(z, plus(x, f(y))), ext) -> times(times(g(z, y), plus(x, a)), ext)
6.02/2.40	   times(plus(x, y), z) -> plus(times(x, z), times(y, z))
6.02/2.40	We had to orient the following equations of E# equivalently.
6.02/2.40	
6.02/2.40	
6.02/2.40	   TIMES(x, y) == TIMES(y, x)
6.02/2.40	   TIMES(times(x, y), z) == TIMES(x, times(y, z))
6.02/2.40	With the implicit AFS we had to orient the following usable equations of E equivalently.
6.02/2.40	
6.02/2.40	
6.02/2.40	   plus(plus(x, y), z) == plus(x, plus(y, z))
6.02/2.40	   plus(x, y) == plus(y, x)
6.02/2.40	   times(x, y) == times(y, x)
6.02/2.40	   times(times(x, y), z) == times(x, times(y, z))
6.02/2.40	Used ordering: POLO with Polynomial interpretation [POLO]:
6.02/2.40	
6.02/2.40	   POL(TIMES(x_1, x_2)) = 2*x_1 + 2*x_2
6.02/2.40	   POL(a) = 0
6.02/2.40	   POL(f(x_1)) = 0
6.02/2.40	   POL(g(x_1, x_2)) = x_1
6.02/2.40	   POL(plus(x_1, x_2)) = 1
6.02/2.40	   POL(times(x_1, x_2)) = 1 + x_1 + x_2
6.02/2.40	
6.02/2.40	
6.02/2.40	----------------------------------------
6.02/2.40	
6.02/2.40	(6)
6.02/2.40	Obligation:
6.02/2.40	P is empty.
6.02/2.40	The TRS R consists of the following rules:
6.02/2.40	
6.02/2.40	   times(plus(x, y), z) -> plus(times(x, z), times(y, z))
6.02/2.40	   times(z, plus(x, f(y))) -> times(g(z, y), plus(x, a))
6.02/2.40	   times(times(plus(x, y), z), ext) -> times(plus(times(x, z), times(y, z)), ext)
6.02/2.40	   times(times(z, plus(x, f(y))), ext) -> times(times(g(z, y), plus(x, a)), ext)
6.02/2.40	
6.02/2.40	The set E consists of the following equations:
6.02/2.40	
6.02/2.40	   plus(x, y) == plus(y, x)
6.02/2.40	   times(x, y) == times(y, x)
6.02/2.40	   plus(plus(x, y), z) == plus(x, plus(y, z))
6.02/2.40	   times(times(x, y), z) == times(x, times(y, z))
6.02/2.40	
6.02/2.40	The set E# consists of the following equations:
6.02/2.40	
6.02/2.40	   TIMES(x, y) == TIMES(y, x)
6.02/2.40	   TIMES(times(x, y), z) == TIMES(x, times(y, z))
6.02/2.40	
6.02/2.40	We have to consider all minimal (P,E#,R,E)-chains
6.02/2.40	----------------------------------------
6.02/2.40	
6.02/2.40	(7) PisEmptyProof (EQUIVALENT)
6.02/2.40	The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
6.02/2.40	----------------------------------------
6.02/2.40	
6.02/2.40	(8)
6.02/2.40	YES
6.16/2.52	EOF