39.49/10.90	YES
39.81/10.96	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
39.81/10.96	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
39.81/10.96	
39.81/10.96	
39.81/10.96	Termination w.r.t. Q of the given QTRS could be proven:
39.81/10.96	
39.81/10.96	(0) QTRS
39.81/10.96	(1) QTRS Reverse [EQUIVALENT, 0 ms]
39.81/10.96	(2) QTRS
39.81/10.96	(3) DependencyPairsProof [EQUIVALENT, 18 ms]
39.81/10.96	(4) QDP
39.81/10.96	(5) QDPOrderProof [EQUIVALENT, 58 ms]
39.81/10.96	(6) QDP
39.81/10.96	(7) QDPOrderProof [EQUIVALENT, 207 ms]
39.81/10.96	(8) QDP
39.81/10.96	(9) DependencyGraphProof [EQUIVALENT, 0 ms]
39.81/10.96	(10) QDP
39.81/10.96	(11) QDPOrderProof [EQUIVALENT, 67 ms]
39.81/10.96	(12) QDP
39.81/10.96	(13) QDPOrderProof [EQUIVALENT, 161 ms]
39.81/10.96	(14) QDP
39.81/10.96	(15) PisEmptyProof [EQUIVALENT, 0 ms]
39.81/10.96	(16) YES
39.81/10.96	
39.81/10.96	
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(0)
39.81/10.96	Obligation:
39.81/10.96	Q restricted rewrite system:
39.81/10.96	The TRS R consists of the following rules:
39.81/10.96	
39.81/10.96	   b(a(a(b(x1)))) -> b(a(b(a(x1))))
39.81/10.96	   b(a(a(a(x1)))) -> b(a(b(b(x1))))
39.81/10.96	   a(b(a(b(x1)))) -> b(b(b(b(x1))))
39.81/10.96	   a(b(a(b(x1)))) -> a(a(a(b(x1))))
39.81/10.96	
39.81/10.96	Q is empty.
39.81/10.96	
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(1) QTRS Reverse (EQUIVALENT)
39.81/10.96	We applied the QTRS Reverse Processor [REVERSE].
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(2)
39.81/10.96	Obligation:
39.81/10.96	Q restricted rewrite system:
39.81/10.96	The TRS R consists of the following rules:
39.81/10.96	
39.81/10.96	   b(a(a(b(x1)))) -> a(b(a(b(x1))))
39.81/10.96	   a(a(a(b(x1)))) -> b(b(a(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(b(b(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(a(a(a(x1))))
39.81/10.96	
39.81/10.96	Q is empty.
39.81/10.96	
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(3) DependencyPairsProof (EQUIVALENT)
39.81/10.96	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(4)
39.81/10.96	Obligation:
39.81/10.96	Q DP problem:
39.81/10.96	The TRS P consists of the following rules:
39.81/10.96	
39.81/10.96	   B(a(a(b(x1)))) -> A(b(a(b(x1))))
39.81/10.96	   B(a(a(b(x1)))) -> B(a(b(x1)))
39.81/10.96	   A(a(a(b(x1)))) -> B(b(a(b(x1))))
39.81/10.96	   A(a(a(b(x1)))) -> B(a(b(x1)))
39.81/10.96	   B(a(b(a(x1)))) -> B(b(b(b(x1))))
39.81/10.96	   B(a(b(a(x1)))) -> B(b(b(x1)))
39.81/10.96	   B(a(b(a(x1)))) -> B(b(x1))
39.81/10.96	   B(a(b(a(x1)))) -> B(x1)
39.81/10.96	   B(a(b(a(x1)))) -> B(a(a(a(x1))))
39.81/10.96	   B(a(b(a(x1)))) -> A(a(a(x1)))
39.81/10.96	   B(a(b(a(x1)))) -> A(a(x1))
39.81/10.96	
39.81/10.96	The TRS R consists of the following rules:
39.81/10.96	
39.81/10.96	   b(a(a(b(x1)))) -> a(b(a(b(x1))))
39.81/10.96	   a(a(a(b(x1)))) -> b(b(a(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(b(b(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(a(a(a(x1))))
39.81/10.96	
39.81/10.96	Q is empty.
39.81/10.96	We have to consider all minimal (P,Q,R)-chains.
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(5) QDPOrderProof (EQUIVALENT)
39.81/10.96	We use the reduction pair processor [LPAR04,JAR06].
39.81/10.96	
39.81/10.96	
39.81/10.96	The following pairs can be oriented strictly and are deleted.
39.81/10.96	
39.81/10.96	   B(a(a(b(x1)))) -> B(a(b(x1)))
39.81/10.96	   A(a(a(b(x1)))) -> B(a(b(x1)))
39.81/10.96	   B(a(b(a(x1)))) -> B(b(b(x1)))
39.81/10.96	   B(a(b(a(x1)))) -> B(b(x1))
39.81/10.96	   B(a(b(a(x1)))) -> B(x1)
39.81/10.96	   B(a(b(a(x1)))) -> A(a(a(x1)))
39.81/10.96	   B(a(b(a(x1)))) -> A(a(x1))
39.81/10.96	The remaining pairs can at least be oriented weakly.
39.81/10.96	Used ordering:  Polynomial interpretation [POLO]:
39.81/10.96	
39.81/10.96	   POL(A(x_1)) = 1 + x_1
39.81/10.96	   POL(B(x_1)) = 1 + x_1
39.81/10.96	   POL(a(x_1)) = 1 + x_1
39.81/10.96	   POL(b(x_1)) = 1 + x_1
39.81/10.96	
39.81/10.96	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
39.81/10.96	
39.81/10.96	   a(a(a(b(x1)))) -> b(b(a(b(x1))))
39.81/10.96	   b(a(a(b(x1)))) -> a(b(a(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(b(b(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(a(a(a(x1))))
39.81/10.96	
39.81/10.96	
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(6)
39.81/10.96	Obligation:
39.81/10.96	Q DP problem:
39.81/10.96	The TRS P consists of the following rules:
39.81/10.96	
39.81/10.96	   B(a(a(b(x1)))) -> A(b(a(b(x1))))
39.81/10.96	   A(a(a(b(x1)))) -> B(b(a(b(x1))))
39.81/10.96	   B(a(b(a(x1)))) -> B(b(b(b(x1))))
39.81/10.96	   B(a(b(a(x1)))) -> B(a(a(a(x1))))
39.81/10.96	
39.81/10.96	The TRS R consists of the following rules:
39.81/10.96	
39.81/10.96	   b(a(a(b(x1)))) -> a(b(a(b(x1))))
39.81/10.96	   a(a(a(b(x1)))) -> b(b(a(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(b(b(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(a(a(a(x1))))
39.81/10.96	
39.81/10.96	Q is empty.
39.81/10.96	We have to consider all minimal (P,Q,R)-chains.
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(7) QDPOrderProof (EQUIVALENT)
39.81/10.96	We use the reduction pair processor [LPAR04,JAR06].
39.81/10.96	
39.81/10.96	
39.81/10.96	The following pairs can be oriented strictly and are deleted.
39.81/10.96	
39.81/10.96	   A(a(a(b(x1)))) -> B(b(a(b(x1))))
39.81/10.96	The remaining pairs can at least be oriented weakly.
39.81/10.96	Used ordering:  Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]:
39.81/10.96	
39.81/10.96	   <<<
39.81/10.96	 POL(B(x_1)) =  	[[0A]] 	 +  	[[0A, 0A, 0A]] 	* 	x_1
39.81/10.96	>>>
39.81/10.96	
39.81/10.96	   <<<
39.81/10.96	 POL(a(x_1)) =  	[[0A], [0A], [0A]] 	 +  	[[-I, 0A, 0A], [0A, -I, -I], [0A, 1A, 0A]] 	* 	x_1
39.81/10.96	>>>
39.81/10.96	
39.81/10.96	   <<<
39.81/10.96	 POL(b(x_1)) =  	[[0A], [-I], [0A]] 	 +  	[[0A, 1A, 1A], [-I, 0A, 0A], [-I, 0A, 0A]] 	* 	x_1
39.81/10.96	>>>
39.81/10.96	
39.81/10.96	   <<<
39.81/10.96	 POL(A(x_1)) =  	[[1A]] 	 +  	[[0A, 0A, 1A]] 	* 	x_1
39.81/10.96	>>>
39.81/10.96	
39.81/10.96	
39.81/10.96	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
39.81/10.96	
39.81/10.96	   a(a(a(b(x1)))) -> b(b(a(b(x1))))
39.81/10.96	   b(a(a(b(x1)))) -> a(b(a(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(b(b(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(a(a(a(x1))))
39.81/10.96	
39.81/10.96	
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(8)
39.81/10.96	Obligation:
39.81/10.96	Q DP problem:
39.81/10.96	The TRS P consists of the following rules:
39.81/10.96	
39.81/10.96	   B(a(a(b(x1)))) -> A(b(a(b(x1))))
39.81/10.96	   B(a(b(a(x1)))) -> B(b(b(b(x1))))
39.81/10.96	   B(a(b(a(x1)))) -> B(a(a(a(x1))))
39.81/10.96	
39.81/10.96	The TRS R consists of the following rules:
39.81/10.96	
39.81/10.96	   b(a(a(b(x1)))) -> a(b(a(b(x1))))
39.81/10.96	   a(a(a(b(x1)))) -> b(b(a(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(b(b(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(a(a(a(x1))))
39.81/10.96	
39.81/10.96	Q is empty.
39.81/10.96	We have to consider all minimal (P,Q,R)-chains.
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(9) DependencyGraphProof (EQUIVALENT)
39.81/10.96	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(10)
39.81/10.96	Obligation:
39.81/10.96	Q DP problem:
39.81/10.96	The TRS P consists of the following rules:
39.81/10.96	
39.81/10.96	   B(a(b(a(x1)))) -> B(a(a(a(x1))))
39.81/10.96	   B(a(b(a(x1)))) -> B(b(b(b(x1))))
39.81/10.96	
39.81/10.96	The TRS R consists of the following rules:
39.81/10.96	
39.81/10.96	   b(a(a(b(x1)))) -> a(b(a(b(x1))))
39.81/10.96	   a(a(a(b(x1)))) -> b(b(a(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(b(b(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(a(a(a(x1))))
39.81/10.96	
39.81/10.96	Q is empty.
39.81/10.96	We have to consider all minimal (P,Q,R)-chains.
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(11) QDPOrderProof (EQUIVALENT)
39.81/10.96	We use the reduction pair processor [LPAR04,JAR06].
39.81/10.96	
39.81/10.96	
39.81/10.96	The following pairs can be oriented strictly and are deleted.
39.81/10.96	
39.81/10.96	   B(a(b(a(x1)))) -> B(b(b(b(x1))))
39.81/10.96	The remaining pairs can at least be oriented weakly.
39.81/10.96	Used ordering:  Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]:
39.81/10.96	
39.81/10.96	   <<<
39.81/10.96	 POL(B(x_1)) =  	[[-I]] 	 +  	[[0A, -I, -I]] 	* 	x_1
39.81/10.96	>>>
39.81/10.96	
39.81/10.96	   <<<
39.81/10.96	 POL(a(x_1)) =  	[[-I], [-I], [-I]] 	 +  	[[0A, 0A, 1A], [-I, -I, 0A], [0A, 1A, -I]] 	* 	x_1
39.81/10.96	>>>
39.81/10.96	
39.81/10.96	   <<<
39.81/10.96	 POL(b(x_1)) =  	[[-I], [-I], [-I]] 	 +  	[[0A, 0A, 0A], [0A, -I, 0A], [0A, -I, 0A]] 	* 	x_1
39.81/10.96	>>>
39.81/10.96	
39.81/10.96	
39.81/10.96	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
39.81/10.96	
39.81/10.96	   a(a(a(b(x1)))) -> b(b(a(b(x1))))
39.81/10.96	   b(a(a(b(x1)))) -> a(b(a(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(b(b(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(a(a(a(x1))))
39.81/10.96	
39.81/10.96	
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(12)
39.81/10.96	Obligation:
39.81/10.96	Q DP problem:
39.81/10.96	The TRS P consists of the following rules:
39.81/10.96	
39.81/10.96	   B(a(b(a(x1)))) -> B(a(a(a(x1))))
39.81/10.96	
39.81/10.96	The TRS R consists of the following rules:
39.81/10.96	
39.81/10.96	   b(a(a(b(x1)))) -> a(b(a(b(x1))))
39.81/10.96	   a(a(a(b(x1)))) -> b(b(a(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(b(b(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(a(a(a(x1))))
39.81/10.96	
39.81/10.96	Q is empty.
39.81/10.96	We have to consider all minimal (P,Q,R)-chains.
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(13) QDPOrderProof (EQUIVALENT)
39.81/10.96	We use the reduction pair processor [LPAR04,JAR06].
39.81/10.96	
39.81/10.96	
39.81/10.96	The following pairs can be oriented strictly and are deleted.
39.81/10.96	
39.81/10.96	   B(a(b(a(x1)))) -> B(a(a(a(x1))))
39.81/10.96	The remaining pairs can at least be oriented weakly.
39.81/10.96	Used ordering:  Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]:
39.81/10.96	
39.81/10.96	   <<<
39.81/10.96	 POL(B(x_1)) =  	[[-I]] 	 +  	[[0A, -I, -I]] 	* 	x_1
39.81/10.96	>>>
39.81/10.96	
39.81/10.96	   <<<
39.81/10.96	 POL(a(x_1)) =  	[[1A], [1A], [-I]] 	 +  	[[0A, -I, 0A], [1A, 0A, 0A], [0A, 0A, 0A]] 	* 	x_1
39.81/10.96	>>>
39.81/10.96	
39.81/10.96	   <<<
39.81/10.96	 POL(b(x_1)) =  	[[0A], [-I], [0A]] 	 +  	[[-I, 0A, -I], [0A, 0A, -I], [0A, 1A, 0A]] 	* 	x_1
39.81/10.96	>>>
39.81/10.96	
39.81/10.96	
39.81/10.96	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
39.81/10.96	
39.81/10.96	   a(a(a(b(x1)))) -> b(b(a(b(x1))))
39.81/10.96	   b(a(a(b(x1)))) -> a(b(a(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(b(b(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(a(a(a(x1))))
39.81/10.96	
39.81/10.96	
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(14)
39.81/10.96	Obligation:
39.81/10.96	Q DP problem:
39.81/10.96	P is empty.
39.81/10.96	The TRS R consists of the following rules:
39.81/10.96	
39.81/10.96	   b(a(a(b(x1)))) -> a(b(a(b(x1))))
39.81/10.96	   a(a(a(b(x1)))) -> b(b(a(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(b(b(b(x1))))
39.81/10.96	   b(a(b(a(x1)))) -> b(a(a(a(x1))))
39.81/10.96	
39.81/10.96	Q is empty.
39.81/10.96	We have to consider all minimal (P,Q,R)-chains.
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(15) PisEmptyProof (EQUIVALENT)
39.81/10.96	The TRS P is empty. Hence, there is no (P,Q,R) chain.
39.81/10.96	----------------------------------------
39.81/10.96	
39.81/10.96	(16)
39.81/10.96	YES
39.89/11.01	EOF