38.33/10.62	YES
38.73/10.66	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
38.73/10.66	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
38.73/10.66	
38.73/10.66	
38.73/10.66	Termination w.r.t. Q of the given QTRS could be proven:
38.73/10.66	
38.73/10.66	(0) QTRS
38.73/10.66	(1) DependencyPairsProof [EQUIVALENT, 18 ms]
38.73/10.66	(2) QDP
38.73/10.66	(3) DependencyGraphProof [EQUIVALENT, 1 ms]
38.73/10.66	(4) AND
38.73/10.66	    (5) QDP
38.73/10.66	        (6) UsableRulesProof [EQUIVALENT, 0 ms]
38.73/10.66	        (7) QDP
38.73/10.66	        (8) QDPOrderProof [EQUIVALENT, 68 ms]
38.73/10.66	        (9) QDP
38.73/10.66	        (10) DependencyGraphProof [EQUIVALENT, 0 ms]
38.73/10.66	        (11) QDP
38.73/10.66	        (12) QDPOrderProof [EQUIVALENT, 241 ms]
38.73/10.66	        (13) QDP
38.73/10.66	        (14) DependencyGraphProof [EQUIVALENT, 0 ms]
38.73/10.66	        (15) QDP
38.73/10.66	        (16) QDPOrderProof [EQUIVALENT, 0 ms]
38.73/10.66	        (17) QDP
38.73/10.66	        (18) DependencyGraphProof [EQUIVALENT, 0 ms]
38.73/10.66	        (19) QDP
38.73/10.66	        (20) QDPOrderProof [EQUIVALENT, 0 ms]
38.73/10.66	        (21) QDP
38.73/10.66	        (22) DependencyGraphProof [EQUIVALENT, 0 ms]
38.73/10.66	        (23) QDP
38.73/10.66	        (24) QDPOrderProof [EQUIVALENT, 0 ms]
38.73/10.66	        (25) QDP
38.73/10.66	        (26) PisEmptyProof [EQUIVALENT, 0 ms]
38.73/10.66	        (27) YES
38.73/10.66	    (28) QDP
38.73/10.66	        (29) UsableRulesProof [EQUIVALENT, 1 ms]
38.73/10.66	        (30) QDP
38.73/10.66	        (31) QDPSizeChangeProof [EQUIVALENT, 0 ms]
38.73/10.66	        (32) YES
38.73/10.66	
38.73/10.66	
38.73/10.66	----------------------------------------
38.73/10.66	
38.73/10.66	(0)
38.73/10.66	Obligation:
38.73/10.66	Q restricted rewrite system:
38.73/10.66	The TRS R consists of the following rules:
38.73/10.66	
38.73/10.66	   3(1(x1)) -> 4(1(x1))
38.73/10.66	   5(9(x1)) -> 2(6(5(x1)))
38.73/10.66	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.66	   9(x1) -> 3(2(3(x1)))
38.73/10.66	   8(4(x1)) -> 6(x1)
38.73/10.66	   2(6(x1)) -> 4(3(x1))
38.73/10.66	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.66	   9(x1) -> 5(0(2(x1)))
38.73/10.66	   8(8(4(x1))) -> 1(9(x1))
38.73/10.66	   7(1(x1)) -> 6(9(x1))
38.73/10.66	   3(9(x1)) -> 9(3(x1))
38.73/10.66	   7(5(x1)) -> 1(0(x1))
38.73/10.66	
38.73/10.66	Q is empty.
38.73/10.66	
38.73/10.66	----------------------------------------
38.73/10.66	
38.73/10.66	(1) DependencyPairsProof (EQUIVALENT)
38.73/10.66	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
38.73/10.66	----------------------------------------
38.73/10.66	
38.73/10.66	(2)
38.73/10.66	Obligation:
38.73/10.66	Q DP problem:
38.73/10.66	The TRS P consists of the following rules:
38.73/10.66	
38.73/10.66	   5^1(9(x1)) -> 2^1(6(5(x1)))
38.73/10.66	   5^1(9(x1)) -> 5^1(x1)
38.73/10.66	   3^1(5(x1)) -> 8^1(9(7(x1)))
38.73/10.66	   3^1(5(x1)) -> 9^1(7(x1))
38.73/10.66	   3^1(5(x1)) -> 7^1(x1)
38.73/10.66	   9^1(x1) -> 3^1(2(3(x1)))
38.73/10.66	   9^1(x1) -> 2^1(3(x1))
38.73/10.66	   9^1(x1) -> 3^1(x1)
38.73/10.66	   2^1(6(x1)) -> 3^1(x1)
38.73/10.66	   3^1(8(x1)) -> 3^1(2(7(x1)))
38.73/10.66	   3^1(8(x1)) -> 2^1(7(x1))
38.73/10.66	   3^1(8(x1)) -> 7^1(x1)
38.73/10.66	   9^1(x1) -> 5^1(0(2(x1)))
38.73/10.66	   9^1(x1) -> 2^1(x1)
38.73/10.66	   8^1(8(4(x1))) -> 9^1(x1)
38.73/10.66	   7^1(1(x1)) -> 9^1(x1)
38.73/10.66	   3^1(9(x1)) -> 9^1(3(x1))
38.73/10.66	   3^1(9(x1)) -> 3^1(x1)
38.73/10.66	
38.73/10.66	The TRS R consists of the following rules:
38.73/10.66	
38.73/10.66	   3(1(x1)) -> 4(1(x1))
38.73/10.66	   5(9(x1)) -> 2(6(5(x1)))
38.73/10.66	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.66	   9(x1) -> 3(2(3(x1)))
38.73/10.66	   8(4(x1)) -> 6(x1)
38.73/10.66	   2(6(x1)) -> 4(3(x1))
38.73/10.66	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.66	   9(x1) -> 5(0(2(x1)))
38.73/10.66	   8(8(4(x1))) -> 1(9(x1))
38.73/10.66	   7(1(x1)) -> 6(9(x1))
38.73/10.66	   3(9(x1)) -> 9(3(x1))
38.73/10.66	   7(5(x1)) -> 1(0(x1))
38.73/10.66	
38.73/10.66	Q is empty.
38.73/10.66	We have to consider all minimal (P,Q,R)-chains.
38.73/10.66	----------------------------------------
38.73/10.66	
38.73/10.66	(3) DependencyGraphProof (EQUIVALENT)
38.73/10.66	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 2 less nodes.
38.73/10.66	----------------------------------------
38.73/10.66	
38.73/10.66	(4)
38.73/10.66	Complex Obligation (AND)
38.73/10.66	
38.73/10.66	----------------------------------------
38.73/10.66	
38.73/10.66	(5)
38.73/10.66	Obligation:
38.73/10.66	Q DP problem:
38.73/10.66	The TRS P consists of the following rules:
38.73/10.66	
38.73/10.66	   8^1(8(4(x1))) -> 9^1(x1)
38.73/10.66	   9^1(x1) -> 3^1(2(3(x1)))
38.73/10.66	   3^1(5(x1)) -> 8^1(9(7(x1)))
38.73/10.66	   3^1(5(x1)) -> 9^1(7(x1))
38.73/10.66	   9^1(x1) -> 2^1(3(x1))
38.73/10.66	   2^1(6(x1)) -> 3^1(x1)
38.73/10.66	   3^1(5(x1)) -> 7^1(x1)
38.73/10.66	   7^1(1(x1)) -> 9^1(x1)
38.73/10.66	   9^1(x1) -> 3^1(x1)
38.73/10.66	   3^1(8(x1)) -> 3^1(2(7(x1)))
38.73/10.66	   3^1(8(x1)) -> 2^1(7(x1))
38.73/10.66	   3^1(8(x1)) -> 7^1(x1)
38.73/10.66	   3^1(9(x1)) -> 9^1(3(x1))
38.73/10.66	   9^1(x1) -> 2^1(x1)
38.73/10.66	   3^1(9(x1)) -> 3^1(x1)
38.73/10.66	
38.73/10.66	The TRS R consists of the following rules:
38.73/10.66	
38.73/10.66	   3(1(x1)) -> 4(1(x1))
38.73/10.66	   5(9(x1)) -> 2(6(5(x1)))
38.73/10.66	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.66	   9(x1) -> 3(2(3(x1)))
38.73/10.66	   8(4(x1)) -> 6(x1)
38.73/10.66	   2(6(x1)) -> 4(3(x1))
38.73/10.66	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.66	   9(x1) -> 5(0(2(x1)))
38.73/10.66	   8(8(4(x1))) -> 1(9(x1))
38.73/10.66	   7(1(x1)) -> 6(9(x1))
38.73/10.66	   3(9(x1)) -> 9(3(x1))
38.73/10.66	   7(5(x1)) -> 1(0(x1))
38.73/10.66	
38.73/10.66	Q is empty.
38.73/10.66	We have to consider all minimal (P,Q,R)-chains.
38.73/10.66	----------------------------------------
38.73/10.66	
38.73/10.66	(6) UsableRulesProof (EQUIVALENT)
38.73/10.66	We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
38.73/10.66	----------------------------------------
38.73/10.66	
38.73/10.66	(7)
38.73/10.66	Obligation:
38.73/10.66	Q DP problem:
38.73/10.66	The TRS P consists of the following rules:
38.73/10.66	
38.73/10.66	   8^1(8(4(x1))) -> 9^1(x1)
38.73/10.66	   9^1(x1) -> 3^1(2(3(x1)))
38.73/10.66	   3^1(5(x1)) -> 8^1(9(7(x1)))
38.73/10.66	   3^1(5(x1)) -> 9^1(7(x1))
38.73/10.66	   9^1(x1) -> 2^1(3(x1))
38.73/10.66	   2^1(6(x1)) -> 3^1(x1)
38.73/10.66	   3^1(5(x1)) -> 7^1(x1)
38.73/10.66	   7^1(1(x1)) -> 9^1(x1)
38.73/10.66	   9^1(x1) -> 3^1(x1)
38.73/10.66	   3^1(8(x1)) -> 3^1(2(7(x1)))
38.73/10.66	   3^1(8(x1)) -> 2^1(7(x1))
38.73/10.66	   3^1(8(x1)) -> 7^1(x1)
38.73/10.66	   3^1(9(x1)) -> 9^1(3(x1))
38.73/10.66	   9^1(x1) -> 2^1(x1)
38.73/10.66	   3^1(9(x1)) -> 3^1(x1)
38.73/10.66	
38.73/10.66	The TRS R consists of the following rules:
38.73/10.66	
38.73/10.66	   3(1(x1)) -> 4(1(x1))
38.73/10.66	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.66	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.66	   3(9(x1)) -> 9(3(x1))
38.73/10.66	   9(x1) -> 3(2(3(x1)))
38.73/10.66	   7(1(x1)) -> 6(9(x1))
38.73/10.66	   7(5(x1)) -> 1(0(x1))
38.73/10.66	   2(6(x1)) -> 4(3(x1))
38.73/10.66	   9(x1) -> 5(0(2(x1)))
38.73/10.66	   8(4(x1)) -> 6(x1)
38.73/10.66	   8(8(4(x1))) -> 1(9(x1))
38.73/10.66	
38.73/10.66	Q is empty.
38.73/10.66	We have to consider all minimal (P,Q,R)-chains.
38.73/10.66	----------------------------------------
38.73/10.66	
38.73/10.66	(8) QDPOrderProof (EQUIVALENT)
38.73/10.66	We use the reduction pair processor [LPAR04,JAR06].
38.73/10.66	
38.73/10.66	
38.73/10.66	The following pairs can be oriented strictly and are deleted.
38.73/10.66	
38.73/10.66	   8^1(8(4(x1))) -> 9^1(x1)
38.73/10.66	The remaining pairs can at least be oriented weakly.
38.73/10.66	Used ordering:  Polynomial interpretation [POLO]:
38.73/10.66	
38.73/10.66	   POL(0(x_1)) = 0
38.73/10.66	   POL(1(x_1)) = 0
38.73/10.66	   POL(2(x_1)) = 0
38.73/10.66	   POL(2^1(x_1)) = 4
38.73/10.66	   POL(3(x_1)) = 4*x_1
38.73/10.66	   POL(3^1(x_1)) = 4
38.73/10.66	   POL(4(x_1)) = 0
38.73/10.66	   POL(5(x_1)) = 1
38.73/10.66	   POL(6(x_1)) = 0
38.73/10.66	   POL(7(x_1)) = 0
38.73/10.66	   POL(7^1(x_1)) = 4
38.73/10.66	   POL(8(x_1)) = 2
38.73/10.66	   POL(8^1(x_1)) = 4*x_1
38.73/10.66	   POL(9(x_1)) = 1
38.73/10.66	   POL(9^1(x_1)) = 4
38.73/10.66	
38.73/10.66	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
38.73/10.66	
38.73/10.66	   3(1(x1)) -> 4(1(x1))
38.73/10.66	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.66	   3(9(x1)) -> 9(3(x1))
38.73/10.66	   9(x1) -> 3(2(3(x1)))
38.73/10.66	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.66	   2(6(x1)) -> 4(3(x1))
38.73/10.66	   9(x1) -> 5(0(2(x1)))
38.73/10.66	   8(8(4(x1))) -> 1(9(x1))
38.73/10.66	   8(4(x1)) -> 6(x1)
38.73/10.66	
38.73/10.66	
38.73/10.66	----------------------------------------
38.73/10.66	
38.73/10.66	(9)
38.73/10.66	Obligation:
38.73/10.66	Q DP problem:
38.73/10.66	The TRS P consists of the following rules:
38.73/10.66	
38.73/10.66	   9^1(x1) -> 3^1(2(3(x1)))
38.73/10.66	   3^1(5(x1)) -> 8^1(9(7(x1)))
38.73/10.66	   3^1(5(x1)) -> 9^1(7(x1))
38.73/10.66	   9^1(x1) -> 2^1(3(x1))
38.73/10.66	   2^1(6(x1)) -> 3^1(x1)
38.73/10.66	   3^1(5(x1)) -> 7^1(x1)
38.73/10.66	   7^1(1(x1)) -> 9^1(x1)
38.73/10.66	   9^1(x1) -> 3^1(x1)
38.73/10.66	   3^1(8(x1)) -> 3^1(2(7(x1)))
38.73/10.66	   3^1(8(x1)) -> 2^1(7(x1))
38.73/10.66	   3^1(8(x1)) -> 7^1(x1)
38.73/10.66	   3^1(9(x1)) -> 9^1(3(x1))
38.73/10.66	   9^1(x1) -> 2^1(x1)
38.73/10.66	   3^1(9(x1)) -> 3^1(x1)
38.73/10.66	
38.73/10.66	The TRS R consists of the following rules:
38.73/10.66	
38.73/10.66	   3(1(x1)) -> 4(1(x1))
38.73/10.66	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.66	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.66	   3(9(x1)) -> 9(3(x1))
38.73/10.66	   9(x1) -> 3(2(3(x1)))
38.73/10.66	   7(1(x1)) -> 6(9(x1))
38.73/10.66	   7(5(x1)) -> 1(0(x1))
38.73/10.66	   2(6(x1)) -> 4(3(x1))
38.73/10.66	   9(x1) -> 5(0(2(x1)))
38.73/10.66	   8(4(x1)) -> 6(x1)
38.73/10.66	   8(8(4(x1))) -> 1(9(x1))
38.73/10.66	
38.73/10.66	Q is empty.
38.73/10.66	We have to consider all minimal (P,Q,R)-chains.
38.73/10.66	----------------------------------------
38.73/10.66	
38.73/10.66	(10) DependencyGraphProof (EQUIVALENT)
38.73/10.66	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
38.73/10.66	----------------------------------------
38.73/10.66	
38.73/10.66	(11)
38.73/10.66	Obligation:
38.73/10.66	Q DP problem:
38.73/10.66	The TRS P consists of the following rules:
38.73/10.66	
38.73/10.66	   3^1(5(x1)) -> 9^1(7(x1))
38.73/10.66	   9^1(x1) -> 3^1(2(3(x1)))
38.73/10.66	   3^1(5(x1)) -> 7^1(x1)
38.73/10.66	   7^1(1(x1)) -> 9^1(x1)
38.73/10.66	   9^1(x1) -> 2^1(3(x1))
38.73/10.66	   2^1(6(x1)) -> 3^1(x1)
38.73/10.66	   3^1(8(x1)) -> 3^1(2(7(x1)))
38.73/10.66	   3^1(8(x1)) -> 2^1(7(x1))
38.73/10.66	   3^1(8(x1)) -> 7^1(x1)
38.73/10.66	   3^1(9(x1)) -> 9^1(3(x1))
38.73/10.66	   9^1(x1) -> 3^1(x1)
38.73/10.66	   3^1(9(x1)) -> 3^1(x1)
38.73/10.66	   9^1(x1) -> 2^1(x1)
38.73/10.66	
38.73/10.66	The TRS R consists of the following rules:
38.73/10.66	
38.73/10.66	   3(1(x1)) -> 4(1(x1))
38.73/10.66	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.66	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.66	   3(9(x1)) -> 9(3(x1))
38.73/10.66	   9(x1) -> 3(2(3(x1)))
38.73/10.66	   7(1(x1)) -> 6(9(x1))
38.73/10.66	   7(5(x1)) -> 1(0(x1))
38.73/10.66	   2(6(x1)) -> 4(3(x1))
38.73/10.66	   9(x1) -> 5(0(2(x1)))
38.73/10.66	   8(4(x1)) -> 6(x1)
38.73/10.66	   8(8(4(x1))) -> 1(9(x1))
38.73/10.66	
38.73/10.66	Q is empty.
38.73/10.66	We have to consider all minimal (P,Q,R)-chains.
38.73/10.66	----------------------------------------
38.73/10.66	
38.73/10.66	(12) QDPOrderProof (EQUIVALENT)
38.73/10.66	We use the reduction pair processor [LPAR04,JAR06].
38.73/10.66	
38.73/10.66	
38.73/10.66	The following pairs can be oriented strictly and are deleted.
38.73/10.69	
38.73/10.69	   7^1(1(x1)) -> 9^1(x1)
38.73/10.69	The remaining pairs can at least be oriented weakly.
38.73/10.69	Used ordering:  Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]:
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(3^1(x_1)) =  	[[0A]] 	 +  	[[0A, -I, 0A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(5(x_1)) =  	[[-I], [0A], [-I]] 	 +  	[[0A, 0A, 0A], [0A, 1A, -I], [-I, 0A, 1A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(9^1(x_1)) =  	[[0A]] 	 +  	[[0A, 0A, 0A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(7(x_1)) =  	[[0A], [0A], [-I]] 	 +  	[[0A, 0A, -I], [0A, 0A, -I], [-I, 0A, -I]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(2(x_1)) =  	[[0A], [-I], [0A]] 	 +  	[[0A, 0A, -I], [-I, -I, -I], [0A, 0A, 0A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(3(x_1)) =  	[[0A], [0A], [-I]] 	 +  	[[-I, 0A, -I], [-I, 0A, -I], [-I, 0A, -I]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(7^1(x_1)) =  	[[0A]] 	 +  	[[0A, 0A, 1A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(1(x_1)) =  	[[0A], [0A], [0A]] 	 +  	[[0A, 0A, 0A], [0A, 0A, 0A], [0A, 0A, 0A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(2^1(x_1)) =  	[[0A]] 	 +  	[[0A, 0A, 0A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(6(x_1)) =  	[[-I], [-I], [-I]] 	 +  	[[0A, 0A, 0A], [0A, 0A, 0A], [0A, 0A, 0A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(8(x_1)) =  	[[-I], [0A], [-I]] 	 +  	[[0A, 0A, 1A], [-I, -I, 0A], [-I, -I, 0A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(9(x_1)) =  	[[0A], [0A], [-I]] 	 +  	[[0A, 0A, 0A], [0A, 0A, -I], [-I, -I, 0A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(0(x_1)) =  	[[0A], [-I], [-I]] 	 +  	[[0A, -I, -I], [-I, -I, -I], [-I, 0A, -I]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(4(x_1)) =  	[[0A], [-I], [0A]] 	 +  	[[0A, 0A, -I], [-I, -I, -I], [0A, 0A, 0A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	
38.73/10.69	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
38.73/10.69	
38.73/10.69	   7(1(x1)) -> 6(9(x1))
38.73/10.69	   7(5(x1)) -> 1(0(x1))
38.73/10.69	   3(1(x1)) -> 4(1(x1))
38.73/10.69	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.69	   3(9(x1)) -> 9(3(x1))
38.73/10.69	   9(x1) -> 3(2(3(x1)))
38.73/10.69	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.69	   2(6(x1)) -> 4(3(x1))
38.73/10.69	   9(x1) -> 5(0(2(x1)))
38.73/10.69	   8(8(4(x1))) -> 1(9(x1))
38.73/10.69	   8(4(x1)) -> 6(x1)
38.73/10.69	
38.73/10.69	
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(13)
38.73/10.69	Obligation:
38.73/10.69	Q DP problem:
38.73/10.69	The TRS P consists of the following rules:
38.73/10.69	
38.73/10.69	   3^1(5(x1)) -> 9^1(7(x1))
38.73/10.69	   9^1(x1) -> 3^1(2(3(x1)))
38.73/10.69	   3^1(5(x1)) -> 7^1(x1)
38.73/10.69	   9^1(x1) -> 2^1(3(x1))
38.73/10.69	   2^1(6(x1)) -> 3^1(x1)
38.73/10.69	   3^1(8(x1)) -> 3^1(2(7(x1)))
38.73/10.69	   3^1(8(x1)) -> 2^1(7(x1))
38.73/10.69	   3^1(8(x1)) -> 7^1(x1)
38.73/10.69	   3^1(9(x1)) -> 9^1(3(x1))
38.73/10.69	   9^1(x1) -> 3^1(x1)
38.73/10.69	   3^1(9(x1)) -> 3^1(x1)
38.73/10.69	   9^1(x1) -> 2^1(x1)
38.73/10.69	
38.73/10.69	The TRS R consists of the following rules:
38.73/10.69	
38.73/10.69	   3(1(x1)) -> 4(1(x1))
38.73/10.69	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.69	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.69	   3(9(x1)) -> 9(3(x1))
38.73/10.69	   9(x1) -> 3(2(3(x1)))
38.73/10.69	   7(1(x1)) -> 6(9(x1))
38.73/10.69	   7(5(x1)) -> 1(0(x1))
38.73/10.69	   2(6(x1)) -> 4(3(x1))
38.73/10.69	   9(x1) -> 5(0(2(x1)))
38.73/10.69	   8(4(x1)) -> 6(x1)
38.73/10.69	   8(8(4(x1))) -> 1(9(x1))
38.73/10.69	
38.73/10.69	Q is empty.
38.73/10.69	We have to consider all minimal (P,Q,R)-chains.
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(14) DependencyGraphProof (EQUIVALENT)
38.73/10.69	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes.
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(15)
38.73/10.69	Obligation:
38.73/10.69	Q DP problem:
38.73/10.69	The TRS P consists of the following rules:
38.73/10.69	
38.73/10.69	   9^1(x1) -> 3^1(2(3(x1)))
38.73/10.69	   3^1(5(x1)) -> 9^1(7(x1))
38.73/10.69	   9^1(x1) -> 2^1(3(x1))
38.73/10.69	   2^1(6(x1)) -> 3^1(x1)
38.73/10.69	   3^1(8(x1)) -> 3^1(2(7(x1)))
38.73/10.69	   3^1(8(x1)) -> 2^1(7(x1))
38.73/10.69	   3^1(9(x1)) -> 9^1(3(x1))
38.73/10.69	   9^1(x1) -> 3^1(x1)
38.73/10.69	   3^1(9(x1)) -> 3^1(x1)
38.73/10.69	   9^1(x1) -> 2^1(x1)
38.73/10.69	
38.73/10.69	The TRS R consists of the following rules:
38.73/10.69	
38.73/10.69	   3(1(x1)) -> 4(1(x1))
38.73/10.69	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.69	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.69	   3(9(x1)) -> 9(3(x1))
38.73/10.69	   9(x1) -> 3(2(3(x1)))
38.73/10.69	   7(1(x1)) -> 6(9(x1))
38.73/10.69	   7(5(x1)) -> 1(0(x1))
38.73/10.69	   2(6(x1)) -> 4(3(x1))
38.73/10.69	   9(x1) -> 5(0(2(x1)))
38.73/10.69	   8(4(x1)) -> 6(x1)
38.73/10.69	   8(8(4(x1))) -> 1(9(x1))
38.73/10.69	
38.73/10.69	Q is empty.
38.73/10.69	We have to consider all minimal (P,Q,R)-chains.
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(16) QDPOrderProof (EQUIVALENT)
38.73/10.69	We use the reduction pair processor [LPAR04,JAR06].
38.73/10.69	
38.73/10.69	
38.73/10.69	The following pairs can be oriented strictly and are deleted.
38.73/10.69	
38.73/10.69	   2^1(6(x1)) -> 3^1(x1)
38.73/10.69	The remaining pairs can at least be oriented weakly.
38.73/10.69	Used ordering:  Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]:
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(9^1(x_1)) =  	[[0A]] 	 +  	[[0A, 0A, 1A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(3^1(x_1)) =  	[[-I]] 	 +  	[[0A, 0A, 0A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(2(x_1)) =  	[[0A], [-I], [-I]] 	 +  	[[-I, 0A, 1A], [-I, 0A, 0A], [-I, -I, 0A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(3(x_1)) =  	[[0A], [-I], [-I]] 	 +  	[[0A, 0A, 1A], [-I, 0A, 0A], [-I, -I, 0A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(5(x_1)) =  	[[0A], [-I], [0A]] 	 +  	[[0A, 0A, -I], [-I, -I, -I], [1A, 0A, 1A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(7(x_1)) =  	[[-I], [-I], [-I]] 	 +  	[[0A, 0A, 1A], [0A, 0A, -I], [0A, -I, -I]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(2^1(x_1)) =  	[[0A]] 	 +  	[[-I, 0A, 1A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(6(x_1)) =  	[[0A], [0A], [-I]] 	 +  	[[0A, 0A, 0A], [-I, 0A, 0A], [0A, 0A, 0A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(8(x_1)) =  	[[1A], [-I], [-I]] 	 +  	[[1A, 0A, 0A], [-I, 0A, -I], [0A, -I, -I]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(9(x_1)) =  	[[0A], [-I], [1A]] 	 +  	[[0A, 0A, 1A], [0A, 0A, 0A], [0A, 0A, 1A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(1(x_1)) =  	[[1A], [0A], [0A]] 	 +  	[[0A, 0A, 1A], [-I, -I, -I], [-I, 0A, 0A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(4(x_1)) =  	[[-I], [0A], [-I]] 	 +  	[[0A, 0A, 0A], [-I, 0A, 0A], [-I, 0A, 0A]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	   <<<
38.73/10.69	 POL(0(x_1)) =  	[[0A], [-I], [-I]] 	 +  	[[-I, -I, 0A], [-I, 0A, -I], [-I, -I, -I]] 	* 	x_1
38.73/10.69	>>>
38.73/10.69	
38.73/10.69	
38.73/10.69	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
38.73/10.69	
38.73/10.69	   3(1(x1)) -> 4(1(x1))
38.73/10.69	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.69	   3(9(x1)) -> 9(3(x1))
38.73/10.69	   9(x1) -> 3(2(3(x1)))
38.73/10.69	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.69	   2(6(x1)) -> 4(3(x1))
38.73/10.69	   7(1(x1)) -> 6(9(x1))
38.73/10.69	   7(5(x1)) -> 1(0(x1))
38.73/10.69	   9(x1) -> 5(0(2(x1)))
38.73/10.69	   8(8(4(x1))) -> 1(9(x1))
38.73/10.69	   8(4(x1)) -> 6(x1)
38.73/10.69	
38.73/10.69	
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(17)
38.73/10.69	Obligation:
38.73/10.69	Q DP problem:
38.73/10.69	The TRS P consists of the following rules:
38.73/10.69	
38.73/10.69	   9^1(x1) -> 3^1(2(3(x1)))
38.73/10.69	   3^1(5(x1)) -> 9^1(7(x1))
38.73/10.69	   9^1(x1) -> 2^1(3(x1))
38.73/10.69	   3^1(8(x1)) -> 3^1(2(7(x1)))
38.73/10.69	   3^1(8(x1)) -> 2^1(7(x1))
38.73/10.69	   3^1(9(x1)) -> 9^1(3(x1))
38.73/10.69	   9^1(x1) -> 3^1(x1)
38.73/10.69	   3^1(9(x1)) -> 3^1(x1)
38.73/10.69	   9^1(x1) -> 2^1(x1)
38.73/10.69	
38.73/10.69	The TRS R consists of the following rules:
38.73/10.69	
38.73/10.69	   3(1(x1)) -> 4(1(x1))
38.73/10.69	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.69	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.69	   3(9(x1)) -> 9(3(x1))
38.73/10.69	   9(x1) -> 3(2(3(x1)))
38.73/10.69	   7(1(x1)) -> 6(9(x1))
38.73/10.69	   7(5(x1)) -> 1(0(x1))
38.73/10.69	   2(6(x1)) -> 4(3(x1))
38.73/10.69	   9(x1) -> 5(0(2(x1)))
38.73/10.69	   8(4(x1)) -> 6(x1)
38.73/10.69	   8(8(4(x1))) -> 1(9(x1))
38.73/10.69	
38.73/10.69	Q is empty.
38.73/10.69	We have to consider all minimal (P,Q,R)-chains.
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(18) DependencyGraphProof (EQUIVALENT)
38.73/10.69	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes.
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(19)
38.73/10.69	Obligation:
38.73/10.69	Q DP problem:
38.73/10.69	The TRS P consists of the following rules:
38.73/10.69	
38.73/10.69	   3^1(5(x1)) -> 9^1(7(x1))
38.73/10.69	   9^1(x1) -> 3^1(2(3(x1)))
38.73/10.69	   3^1(8(x1)) -> 3^1(2(7(x1)))
38.73/10.69	   3^1(9(x1)) -> 9^1(3(x1))
38.73/10.69	   9^1(x1) -> 3^1(x1)
38.73/10.69	   3^1(9(x1)) -> 3^1(x1)
38.73/10.69	
38.73/10.69	The TRS R consists of the following rules:
38.73/10.69	
38.73/10.69	   3(1(x1)) -> 4(1(x1))
38.73/10.69	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.69	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.69	   3(9(x1)) -> 9(3(x1))
38.73/10.69	   9(x1) -> 3(2(3(x1)))
38.73/10.69	   7(1(x1)) -> 6(9(x1))
38.73/10.69	   7(5(x1)) -> 1(0(x1))
38.73/10.69	   2(6(x1)) -> 4(3(x1))
38.73/10.69	   9(x1) -> 5(0(2(x1)))
38.73/10.69	   8(4(x1)) -> 6(x1)
38.73/10.69	   8(8(4(x1))) -> 1(9(x1))
38.73/10.69	
38.73/10.69	Q is empty.
38.73/10.69	We have to consider all minimal (P,Q,R)-chains.
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(20) QDPOrderProof (EQUIVALENT)
38.73/10.69	We use the reduction pair processor [LPAR04,JAR06].
38.73/10.69	
38.73/10.69	
38.73/10.69	The following pairs can be oriented strictly and are deleted.
38.73/10.69	
38.73/10.69	   3^1(5(x1)) -> 9^1(7(x1))
38.73/10.69	   3^1(9(x1)) -> 9^1(3(x1))
38.73/10.69	   3^1(9(x1)) -> 3^1(x1)
38.73/10.69	The remaining pairs can at least be oriented weakly.
38.73/10.69	Used ordering:  Polynomial interpretation [POLO]:
38.73/10.69	
38.73/10.69	   POL(0(x_1)) = 0
38.73/10.69	   POL(1(x_1)) = 0
38.73/10.69	   POL(2(x_1)) = 0
38.73/10.69	   POL(3(x_1)) = x_1
38.73/10.69	   POL(3^1(x_1)) = x_1
38.73/10.69	   POL(4(x_1)) = 0
38.73/10.69	   POL(5(x_1)) = 1
38.73/10.69	   POL(6(x_1)) = 0
38.73/10.69	   POL(7(x_1)) = 0
38.73/10.69	   POL(8(x_1)) = 0
38.73/10.69	   POL(9(x_1)) = 1 + x_1
38.73/10.69	   POL(9^1(x_1)) = x_1
38.73/10.69	
38.73/10.69	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
38.73/10.69	
38.73/10.69	   7(1(x1)) -> 6(9(x1))
38.73/10.69	   7(5(x1)) -> 1(0(x1))
38.73/10.69	   3(1(x1)) -> 4(1(x1))
38.73/10.69	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.69	   3(9(x1)) -> 9(3(x1))
38.73/10.69	   9(x1) -> 3(2(3(x1)))
38.73/10.69	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.69	   2(6(x1)) -> 4(3(x1))
38.73/10.69	   9(x1) -> 5(0(2(x1)))
38.73/10.69	   8(8(4(x1))) -> 1(9(x1))
38.73/10.69	   8(4(x1)) -> 6(x1)
38.73/10.69	
38.73/10.69	
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(21)
38.73/10.69	Obligation:
38.73/10.69	Q DP problem:
38.73/10.69	The TRS P consists of the following rules:
38.73/10.69	
38.73/10.69	   9^1(x1) -> 3^1(2(3(x1)))
38.73/10.69	   3^1(8(x1)) -> 3^1(2(7(x1)))
38.73/10.69	   9^1(x1) -> 3^1(x1)
38.73/10.69	
38.73/10.69	The TRS R consists of the following rules:
38.73/10.69	
38.73/10.69	   3(1(x1)) -> 4(1(x1))
38.73/10.69	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.69	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.69	   3(9(x1)) -> 9(3(x1))
38.73/10.69	   9(x1) -> 3(2(3(x1)))
38.73/10.69	   7(1(x1)) -> 6(9(x1))
38.73/10.69	   7(5(x1)) -> 1(0(x1))
38.73/10.69	   2(6(x1)) -> 4(3(x1))
38.73/10.69	   9(x1) -> 5(0(2(x1)))
38.73/10.69	   8(4(x1)) -> 6(x1)
38.73/10.69	   8(8(4(x1))) -> 1(9(x1))
38.73/10.69	
38.73/10.69	Q is empty.
38.73/10.69	We have to consider all minimal (P,Q,R)-chains.
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(22) DependencyGraphProof (EQUIVALENT)
38.73/10.69	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes.
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(23)
38.73/10.69	Obligation:
38.73/10.69	Q DP problem:
38.73/10.69	The TRS P consists of the following rules:
38.73/10.69	
38.73/10.69	   3^1(8(x1)) -> 3^1(2(7(x1)))
38.73/10.69	
38.73/10.69	The TRS R consists of the following rules:
38.73/10.69	
38.73/10.69	   3(1(x1)) -> 4(1(x1))
38.73/10.69	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.69	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.69	   3(9(x1)) -> 9(3(x1))
38.73/10.69	   9(x1) -> 3(2(3(x1)))
38.73/10.69	   7(1(x1)) -> 6(9(x1))
38.73/10.69	   7(5(x1)) -> 1(0(x1))
38.73/10.69	   2(6(x1)) -> 4(3(x1))
38.73/10.69	   9(x1) -> 5(0(2(x1)))
38.73/10.69	   8(4(x1)) -> 6(x1)
38.73/10.69	   8(8(4(x1))) -> 1(9(x1))
38.73/10.69	
38.73/10.69	Q is empty.
38.73/10.69	We have to consider all minimal (P,Q,R)-chains.
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(24) QDPOrderProof (EQUIVALENT)
38.73/10.69	We use the reduction pair processor [LPAR04,JAR06].
38.73/10.69	
38.73/10.69	
38.73/10.69	The following pairs can be oriented strictly and are deleted.
38.73/10.69	
38.73/10.69	   3^1(8(x1)) -> 3^1(2(7(x1)))
38.73/10.69	The remaining pairs can at least be oriented weakly.
38.73/10.69	Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:
38.73/10.69	
38.73/10.69	POL( 2_1(x_1) ) = max{0, -2}
38.73/10.69	POL( 3^1_1(x_1) ) = x_1
38.73/10.69	POL( 4_1(x_1) ) = max{0, -2}
38.73/10.69	POL( 8_1(x_1) ) = 2
38.73/10.69	POL( 9_1(x_1) ) = max{0, 2x_1 - 2}
38.73/10.69	POL( 7_1(x_1) ) = 2
38.73/10.69	POL( 1_1(x_1) ) = max{0, -2}
38.73/10.69	POL( 6_1(x_1) ) = x_1 + 2
38.73/10.69	POL( 5_1(x_1) ) = max{0, x_1 - 2}
38.73/10.69	POL( 0_1(x_1) ) = max{0, -2}
38.73/10.69	POL( 3_1(x_1) ) = max{0, x_1 - 2}
38.73/10.69	
38.73/10.69	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
38.73/10.69	
38.73/10.69	   2(6(x1)) -> 4(3(x1))
38.73/10.69	
38.73/10.69	
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(25)
38.73/10.69	Obligation:
38.73/10.69	Q DP problem:
38.73/10.69	P is empty.
38.73/10.69	The TRS R consists of the following rules:
38.73/10.69	
38.73/10.69	   3(1(x1)) -> 4(1(x1))
38.73/10.69	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.69	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.69	   3(9(x1)) -> 9(3(x1))
38.73/10.69	   9(x1) -> 3(2(3(x1)))
38.73/10.69	   7(1(x1)) -> 6(9(x1))
38.73/10.69	   7(5(x1)) -> 1(0(x1))
38.73/10.69	   2(6(x1)) -> 4(3(x1))
38.73/10.69	   9(x1) -> 5(0(2(x1)))
38.73/10.69	   8(4(x1)) -> 6(x1)
38.73/10.69	   8(8(4(x1))) -> 1(9(x1))
38.73/10.69	
38.73/10.69	Q is empty.
38.73/10.69	We have to consider all minimal (P,Q,R)-chains.
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(26) PisEmptyProof (EQUIVALENT)
38.73/10.69	The TRS P is empty. Hence, there is no (P,Q,R) chain.
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(27)
38.73/10.69	YES
38.73/10.69	
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(28)
38.73/10.69	Obligation:
38.73/10.69	Q DP problem:
38.73/10.69	The TRS P consists of the following rules:
38.73/10.69	
38.73/10.69	   5^1(9(x1)) -> 5^1(x1)
38.73/10.69	
38.73/10.69	The TRS R consists of the following rules:
38.73/10.69	
38.73/10.69	   3(1(x1)) -> 4(1(x1))
38.73/10.69	   5(9(x1)) -> 2(6(5(x1)))
38.73/10.69	   3(5(x1)) -> 8(9(7(x1)))
38.73/10.69	   9(x1) -> 3(2(3(x1)))
38.73/10.69	   8(4(x1)) -> 6(x1)
38.73/10.69	   2(6(x1)) -> 4(3(x1))
38.73/10.69	   3(8(x1)) -> 3(2(7(x1)))
38.73/10.69	   9(x1) -> 5(0(2(x1)))
38.73/10.69	   8(8(4(x1))) -> 1(9(x1))
38.73/10.69	   7(1(x1)) -> 6(9(x1))
38.73/10.69	   3(9(x1)) -> 9(3(x1))
38.73/10.69	   7(5(x1)) -> 1(0(x1))
38.73/10.69	
38.73/10.69	Q is empty.
38.73/10.69	We have to consider all minimal (P,Q,R)-chains.
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(29) UsableRulesProof (EQUIVALENT)
38.73/10.69	We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R.
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(30)
38.73/10.69	Obligation:
38.73/10.69	Q DP problem:
38.73/10.69	The TRS P consists of the following rules:
38.73/10.69	
38.73/10.69	   5^1(9(x1)) -> 5^1(x1)
38.73/10.69	
38.73/10.69	R is empty.
38.73/10.69	Q is empty.
38.73/10.69	We have to consider all minimal (P,Q,R)-chains.
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(31) QDPSizeChangeProof (EQUIVALENT)
38.73/10.69	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
38.73/10.69	
38.73/10.69	From the DPs we obtained the following set of size-change graphs:
38.73/10.69	*5^1(9(x1)) -> 5^1(x1)
38.73/10.69	The graph contains the following edges 1 > 1
38.73/10.69	
38.73/10.69	
38.73/10.69	----------------------------------------
38.73/10.69	
38.73/10.69	(32)
38.73/10.69	YES
39.02/10.78	EOF