3.97/1.86	YES
3.97/1.87	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.97/1.87	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.97/1.87	
3.97/1.87	
3.97/1.87	Termination of the given ETRS could be proven:
3.97/1.87	
3.97/1.87	(0) ETRS
3.97/1.87	(1) RRRPoloETRSProof [EQUIVALENT, 148 ms]
3.97/1.87	(2) ETRS
3.97/1.87	(3) RRRPoloETRSProof [EQUIVALENT, 44 ms]
3.97/1.87	(4) ETRS
3.97/1.87	(5) RRRPoloETRSProof [EQUIVALENT, 0 ms]
3.97/1.87	(6) ETRS
3.97/1.87	(7) RRRPoloETRSProof [EQUIVALENT, 0 ms]
3.97/1.87	(8) ETRS
3.97/1.87	(9) RisEmptyProof [EQUIVALENT, 0 ms]
3.97/1.87	(10) YES
3.97/1.87	
3.97/1.87	
3.97/1.87	----------------------------------------
3.97/1.87	
3.97/1.87	(0)
3.97/1.87	Obligation:
3.97/1.87	Equational rewrite system:
3.97/1.87	The TRS R consists of the following rules:
3.97/1.87	
3.97/1.87	   union(X, empty) -> X
3.97/1.87	   union(empty, X) -> X
3.97/1.87	   0(z) -> z
3.97/1.87	   and(tt, X) -> X
3.97/1.87	   mult(z, X) -> z
3.97/1.87	   mult(0(X), Y) -> 0(mult(X, Y))
3.97/1.87	   mult(1(X), Y) -> plus(0(mult(X, Y)), Y)
3.97/1.87	   plus(z, X) -> X
3.97/1.87	   plus(0(X), 0(Y)) -> 0(plus(X, Y))
3.97/1.87	   plus(0(X), 1(Y)) -> 1(plus(X, Y))
3.97/1.87	   plus(1(X), 1(Y)) -> 0(plus(plus(X, Y), 1(z)))
3.97/1.87	   prod(empty) -> 1(z)
3.97/1.87	   prod(singl(X)) -> X
3.97/1.87	   prod(union(A, B)) -> mult(prod(A), prod(B))
3.97/1.87	   sum(empty) -> 0(z)
3.97/1.87	   sum(singl(X)) -> X
3.97/1.87	   sum(union(A, B)) -> plus(sum(A), sum(B))
3.97/1.87	
3.97/1.87	The set E consists of the following equations:
3.97/1.87	
3.97/1.87	   mult(x, y) == mult(y, x)
3.97/1.87	   plus(x, y) == plus(y, x)
3.97/1.87	   union(x, y) == union(y, x)
3.97/1.87	   mult(mult(x, y), z') == mult(x, mult(y, z'))
3.97/1.87	   plus(plus(x, y), z') == plus(x, plus(y, z'))
3.97/1.87	   union(union(x, y), z') == union(x, union(y, z'))
3.97/1.87	
3.97/1.87	
3.97/1.87	----------------------------------------
3.97/1.87	
3.97/1.87	(1) RRRPoloETRSProof (EQUIVALENT)
3.97/1.87	The following E TRS is given: Equational rewrite system:
3.97/1.87	The TRS R consists of the following rules:
3.97/1.87	
3.97/1.87	   union(X, empty) -> X
3.97/1.87	   union(empty, X) -> X
3.97/1.87	   0(z) -> z
3.97/1.87	   and(tt, X) -> X
3.97/1.87	   mult(z, X) -> z
3.97/1.87	   mult(0(X), Y) -> 0(mult(X, Y))
3.97/1.87	   mult(1(X), Y) -> plus(0(mult(X, Y)), Y)
3.97/1.87	   plus(z, X) -> X
3.97/1.87	   plus(0(X), 0(Y)) -> 0(plus(X, Y))
3.97/1.87	   plus(0(X), 1(Y)) -> 1(plus(X, Y))
3.97/1.87	   plus(1(X), 1(Y)) -> 0(plus(plus(X, Y), 1(z)))
3.97/1.87	   prod(empty) -> 1(z)
3.97/1.87	   prod(singl(X)) -> X
3.97/1.87	   prod(union(A, B)) -> mult(prod(A), prod(B))
3.97/1.87	   sum(empty) -> 0(z)
3.97/1.87	   sum(singl(X)) -> X
3.97/1.87	   sum(union(A, B)) -> plus(sum(A), sum(B))
3.97/1.87	
3.97/1.87	The set E consists of the following equations:
3.97/1.87	
3.97/1.87	   mult(x, y) == mult(y, x)
3.97/1.87	   plus(x, y) == plus(y, x)
3.97/1.87	   union(x, y) == union(y, x)
3.97/1.87	   mult(mult(x, y), z') == mult(x, mult(y, z'))
3.97/1.87	   plus(plus(x, y), z') == plus(x, plus(y, z'))
3.97/1.87	   union(union(x, y), z') == union(x, union(y, z'))
3.97/1.87	
3.97/1.87	The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering:
3.97/1.87	
3.97/1.87	   union(X, empty) -> X
3.97/1.87	   union(empty, X) -> X
3.97/1.87	   and(tt, X) -> X
3.97/1.87	   mult(1(X), Y) -> plus(0(mult(X, Y)), Y)
3.97/1.87	   plus(z, X) -> X
3.97/1.87	   sum(empty) -> 0(z)
3.97/1.87	Used ordering:
3.97/1.87	Polynomial interpretation [POLO]:
3.97/1.87	
3.97/1.87	   POL(0(x_1)) = x_1
3.97/1.87	   POL(1(x_1)) = 1 + x_1
3.97/1.87	   POL(and(x_1, x_2)) = 3*x_1 + x_1*x_2 + 3*x_2
3.97/1.87	   POL(empty) = 2
3.97/1.87	   POL(mult(x_1, x_2)) = x_1 + 2*x_1*x_2 + x_2
3.97/1.87	   POL(plus(x_1, x_2)) = x_1 + x_2
3.97/1.87	   POL(prod(x_1)) = x_1
3.97/1.87	   POL(singl(x_1)) = x_1 + 3*x_1^2
3.97/1.87	   POL(sum(x_1)) = x_1 + x_1^2
3.97/1.87	   POL(tt) = 3
3.97/1.87	   POL(union(x_1, x_2)) = x_1 + 2*x_1*x_2 + x_2
3.97/1.87	   POL(z) = 1
3.97/1.87	
3.97/1.87	
3.97/1.87	
3.97/1.87	
3.97/1.87	----------------------------------------
3.97/1.87	
3.97/1.87	(2)
3.97/1.87	Obligation:
3.97/1.87	Equational rewrite system:
3.97/1.87	The TRS R consists of the following rules:
3.97/1.87	
3.97/1.87	   0(z) -> z
3.97/1.87	   mult(z, X) -> z
3.97/1.87	   mult(0(X), Y) -> 0(mult(X, Y))
3.97/1.87	   plus(0(X), 0(Y)) -> 0(plus(X, Y))
3.97/1.87	   plus(0(X), 1(Y)) -> 1(plus(X, Y))
3.97/1.87	   plus(1(X), 1(Y)) -> 0(plus(plus(X, Y), 1(z)))
3.97/1.87	   prod(empty) -> 1(z)
3.97/1.87	   prod(singl(X)) -> X
3.97/1.87	   prod(union(A, B)) -> mult(prod(A), prod(B))
3.97/1.87	   sum(singl(X)) -> X
3.97/1.87	   sum(union(A, B)) -> plus(sum(A), sum(B))
3.97/1.87	
3.97/1.87	The set E consists of the following equations:
3.97/1.87	
3.97/1.87	   mult(x, y) == mult(y, x)
3.97/1.87	   plus(x, y) == plus(y, x)
3.97/1.87	   union(x, y) == union(y, x)
3.97/1.87	   mult(mult(x, y), z') == mult(x, mult(y, z'))
3.97/1.87	   plus(plus(x, y), z') == plus(x, plus(y, z'))
3.97/1.87	   union(union(x, y), z') == union(x, union(y, z'))
3.97/1.87	
3.97/1.87	
3.97/1.87	----------------------------------------
3.97/1.87	
3.97/1.87	(3) RRRPoloETRSProof (EQUIVALENT)
3.97/1.87	The following E TRS is given: Equational rewrite system:
3.97/1.87	The TRS R consists of the following rules:
3.97/1.87	
3.97/1.87	   0(z) -> z
3.97/1.87	   mult(z, X) -> z
3.97/1.87	   mult(0(X), Y) -> 0(mult(X, Y))
3.97/1.87	   plus(0(X), 0(Y)) -> 0(plus(X, Y))
3.97/1.87	   plus(0(X), 1(Y)) -> 1(plus(X, Y))
3.97/1.87	   plus(1(X), 1(Y)) -> 0(plus(plus(X, Y), 1(z)))
3.97/1.87	   prod(empty) -> 1(z)
3.97/1.87	   prod(singl(X)) -> X
3.97/1.87	   prod(union(A, B)) -> mult(prod(A), prod(B))
3.97/1.87	   sum(singl(X)) -> X
3.97/1.87	   sum(union(A, B)) -> plus(sum(A), sum(B))
3.97/1.87	
3.97/1.87	The set E consists of the following equations:
3.97/1.87	
3.97/1.87	   mult(x, y) == mult(y, x)
3.97/1.87	   plus(x, y) == plus(y, x)
3.97/1.87	   union(x, y) == union(y, x)
3.97/1.87	   mult(mult(x, y), z') == mult(x, mult(y, z'))
3.97/1.87	   plus(plus(x, y), z') == plus(x, plus(y, z'))
3.97/1.87	   union(union(x, y), z') == union(x, union(y, z'))
3.97/1.87	
3.97/1.87	The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering:
3.97/1.87	
3.97/1.87	   mult(z, X) -> z
3.97/1.87	   plus(1(X), 1(Y)) -> 0(plus(plus(X, Y), 1(z)))
3.97/1.87	   prod(empty) -> 1(z)
3.97/1.87	   prod(singl(X)) -> X
3.97/1.87	   prod(union(A, B)) -> mult(prod(A), prod(B))
3.97/1.87	   sum(singl(X)) -> X
3.97/1.87	   sum(union(A, B)) -> plus(sum(A), sum(B))
3.97/1.87	Used ordering:
3.97/1.87	Polynomial interpretation [POLO]:
3.97/1.87	
3.97/1.87	   POL(0(x_1)) = x_1
3.97/1.87	   POL(1(x_1)) = 1 + 2*x_1
3.97/1.87	   POL(empty) = 3
3.97/1.87	   POL(mult(x_1, x_2)) = 2 + 2*x_1 + x_1*x_2 + 2*x_2
3.97/1.87	   POL(plus(x_1, x_2)) = x_1 + 2*x_1*x_2 + x_2
3.97/1.87	   POL(prod(x_1)) = 2 + 3*x_1 + 3*x_1^2
3.97/1.87	   POL(singl(x_1)) = x_1 + 3*x_1^2
3.97/1.87	   POL(sum(x_1)) = 1 + 2*x_1 + 3*x_1^2
3.97/1.87	   POL(union(x_1, x_2)) = 2 + 3*x_1 + 3*x_1*x_2 + 3*x_2
3.97/1.87	   POL(z) = 0
3.97/1.87	
3.97/1.87	
3.97/1.87	
3.97/1.87	
3.97/1.87	----------------------------------------
3.97/1.87	
3.97/1.87	(4)
3.97/1.87	Obligation:
3.97/1.87	Equational rewrite system:
3.97/1.87	The TRS R consists of the following rules:
3.97/1.87	
3.97/1.87	   0(z) -> z
3.97/1.87	   mult(0(X), Y) -> 0(mult(X, Y))
3.97/1.87	   plus(0(X), 0(Y)) -> 0(plus(X, Y))
3.97/1.87	   plus(0(X), 1(Y)) -> 1(plus(X, Y))
3.97/1.87	
3.97/1.87	The set E consists of the following equations:
3.97/1.87	
3.97/1.87	   mult(x, y) == mult(y, x)
3.97/1.87	   plus(x, y) == plus(y, x)
3.97/1.87	   union(x, y) == union(y, x)
3.97/1.87	   mult(mult(x, y), z') == mult(x, mult(y, z'))
3.97/1.87	   plus(plus(x, y), z') == plus(x, plus(y, z'))
3.97/1.87	   union(union(x, y), z') == union(x, union(y, z'))
3.97/1.87	
3.97/1.87	
3.97/1.87	----------------------------------------
3.97/1.87	
3.97/1.87	(5) RRRPoloETRSProof (EQUIVALENT)
3.97/1.87	The following E TRS is given: Equational rewrite system:
3.97/1.87	The TRS R consists of the following rules:
3.97/1.87	
3.97/1.87	   0(z) -> z
3.97/1.87	   mult(0(X), Y) -> 0(mult(X, Y))
3.97/1.87	   plus(0(X), 0(Y)) -> 0(plus(X, Y))
3.97/1.87	   plus(0(X), 1(Y)) -> 1(plus(X, Y))
3.97/1.87	
3.97/1.87	The set E consists of the following equations:
3.97/1.87	
3.97/1.87	   mult(x, y) == mult(y, x)
3.97/1.87	   plus(x, y) == plus(y, x)
3.97/1.87	   union(x, y) == union(y, x)
3.97/1.87	   mult(mult(x, y), z') == mult(x, mult(y, z'))
3.97/1.87	   plus(plus(x, y), z') == plus(x, plus(y, z'))
3.97/1.87	   union(union(x, y), z') == union(x, union(y, z'))
3.97/1.87	
3.97/1.87	The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering:
3.97/1.87	
3.97/1.87	   0(z) -> z
3.97/1.87	   plus(0(X), 0(Y)) -> 0(plus(X, Y))
3.97/1.87	   plus(0(X), 1(Y)) -> 1(plus(X, Y))
3.97/1.87	Used ordering:
3.97/1.87	Polynomial interpretation [POLO]:
3.97/1.87	
3.97/1.87	   POL(0(x_1)) = 2 + 3*x_1
3.97/1.87	   POL(1(x_1)) = 2*x_1
3.97/1.87	   POL(mult(x_1, x_2)) = x_1 + 2*x_1*x_2 + x_2
3.97/1.87	   POL(plus(x_1, x_2)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_2
3.97/1.87	   POL(union(x_1, x_2)) = 2 + 3*x_1 + 3*x_1*x_2 + 3*x_2
3.97/1.87	   POL(z) = 2
3.97/1.87	
3.97/1.87	
3.97/1.87	
3.97/1.87	
3.97/1.87	----------------------------------------
3.97/1.87	
3.97/1.87	(6)
3.97/1.87	Obligation:
3.97/1.87	Equational rewrite system:
3.97/1.87	The TRS R consists of the following rules:
3.97/1.87	
3.97/1.87	   mult(0(X), Y) -> 0(mult(X, Y))
3.97/1.87	
3.97/1.87	The set E consists of the following equations:
3.97/1.87	
3.97/1.87	   mult(x, y) == mult(y, x)
3.97/1.87	   plus(x, y) == plus(y, x)
3.97/1.87	   union(x, y) == union(y, x)
3.97/1.87	   mult(mult(x, y), z') == mult(x, mult(y, z'))
3.97/1.87	   plus(plus(x, y), z') == plus(x, plus(y, z'))
3.97/1.87	   union(union(x, y), z') == union(x, union(y, z'))
3.97/1.87	
3.97/1.87	
3.97/1.87	----------------------------------------
3.97/1.87	
3.97/1.87	(7) RRRPoloETRSProof (EQUIVALENT)
3.97/1.87	The following E TRS is given: Equational rewrite system:
3.97/1.87	The TRS R consists of the following rules:
3.97/1.87	
3.97/1.87	   mult(0(X), Y) -> 0(mult(X, Y))
3.97/1.87	
3.97/1.87	The set E consists of the following equations:
3.97/1.87	
3.97/1.87	   mult(x, y) == mult(y, x)
3.97/1.87	   plus(x, y) == plus(y, x)
3.97/1.87	   union(x, y) == union(y, x)
3.97/1.87	   mult(mult(x, y), z') == mult(x, mult(y, z'))
3.97/1.87	   plus(plus(x, y), z') == plus(x, plus(y, z'))
3.97/1.87	   union(union(x, y), z') == union(x, union(y, z'))
3.97/1.87	
3.97/1.87	The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering:
3.97/1.87	
3.97/1.87	   mult(0(X), Y) -> 0(mult(X, Y))
3.97/1.87	Used ordering:
3.97/1.87	Polynomial interpretation [POLO]:
3.97/1.87	
3.97/1.87	   POL(0(x_1)) = 2 + x_1
3.97/1.87	   POL(mult(x_1, x_2)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_2
3.97/1.87	   POL(plus(x_1, x_2)) = 3 + 3*x_1 + 2*x_1*x_2 + 3*x_2
3.97/1.87	   POL(union(x_1, x_2)) = 2 + 3*x_1 + 3*x_1*x_2 + 3*x_2
3.97/1.87	
3.97/1.87	
3.97/1.87	
3.97/1.87	
3.97/1.87	----------------------------------------
3.97/1.87	
3.97/1.87	(8)
3.97/1.87	Obligation:
3.97/1.87	Equational rewrite system:
3.97/1.87	R is empty.
3.97/1.87	The set E consists of the following equations:
3.97/1.87	
3.97/1.87	   mult(x, y) == mult(y, x)
3.97/1.87	   plus(x, y) == plus(y, x)
3.97/1.87	   union(x, y) == union(y, x)
3.97/1.87	   mult(mult(x, y), z') == mult(x, mult(y, z'))
3.97/1.87	   plus(plus(x, y), z') == plus(x, plus(y, z'))
3.97/1.87	   union(union(x, y), z') == union(x, union(y, z'))
3.97/1.87	
3.97/1.87	
3.97/1.87	----------------------------------------
3.97/1.87	
3.97/1.87	(9) RisEmptyProof (EQUIVALENT)
3.97/1.87	The TRS R is empty. Hence, termination is trivially proven.
3.97/1.87	----------------------------------------
3.97/1.87	
3.97/1.87	(10)
3.97/1.87	YES
4.19/1.89	EOF