14.67/5.85	YES
14.67/5.88	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
14.67/5.88	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
14.67/5.88	
14.67/5.88	
14.67/5.88	Termination w.r.t. Q of the given QTRS could be proven:
14.67/5.88	
14.67/5.88	(0) QTRS
14.67/5.88	(1) QTRSRRRProof [EQUIVALENT, 40 ms]
14.67/5.88	(2) QTRS
14.67/5.88	(3) DependencyPairsProof [EQUIVALENT, 10 ms]
14.67/5.88	(4) QDP
14.67/5.88	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
14.67/5.88	(6) AND
14.67/5.88	    (7) QDP
14.67/5.88	        (8) UsableRulesProof [EQUIVALENT, 0 ms]
14.67/5.88	        (9) QDP
14.67/5.88	        (10) DependencyGraphProof [EQUIVALENT, 0 ms]
14.67/5.88	        (11) QDP
14.67/5.88	        (12) UsableRulesProof [EQUIVALENT, 1 ms]
14.67/5.88	        (13) QDP
14.67/5.88	        (14) MRRProof [EQUIVALENT, 2 ms]
14.67/5.88	        (15) QDP
14.67/5.88	        (16) PisEmptyProof [EQUIVALENT, 0 ms]
14.67/5.88	        (17) YES
14.67/5.88	    (18) QDP
14.67/5.88	        (19) UsableRulesProof [EQUIVALENT, 0 ms]
14.67/5.88	        (20) QDP
14.67/5.88	        (21) QDPSizeChangeProof [EQUIVALENT, 0 ms]
14.67/5.88	        (22) YES
14.67/5.88	
14.67/5.88	
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(0)
14.67/5.88	Obligation:
14.67/5.88	Q restricted rewrite system:
14.67/5.88	The TRS R consists of the following rules:
14.67/5.88	
14.67/5.88	   a(b(a(a(x1)))) -> a(b(b(b(x1))))
14.67/5.88	   b(b(a(a(x1)))) -> a(b(a(b(x1))))
14.67/5.88	   b(a(a(b(x1)))) -> b(a(b(a(x1))))
14.67/5.88	
14.67/5.88	Q is empty.
14.67/5.88	
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(1) QTRSRRRProof (EQUIVALENT)
14.67/5.88	Used ordering:
14.67/5.88	Polynomial interpretation [POLO]:
14.67/5.88	
14.67/5.88	   POL(a(x_1)) = 1 + x_1
14.67/5.88	   POL(b(x_1)) = x_1
14.67/5.88	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
14.67/5.88	
14.67/5.88	   a(b(a(a(x1)))) -> a(b(b(b(x1))))
14.67/5.88	
14.67/5.88	
14.67/5.88	
14.67/5.88	
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(2)
14.67/5.88	Obligation:
14.67/5.88	Q restricted rewrite system:
14.67/5.88	The TRS R consists of the following rules:
14.67/5.88	
14.67/5.88	   b(b(a(a(x1)))) -> a(b(a(b(x1))))
14.67/5.88	   b(a(a(b(x1)))) -> b(a(b(a(x1))))
14.67/5.88	
14.67/5.88	Q is empty.
14.67/5.88	
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(3) DependencyPairsProof (EQUIVALENT)
14.67/5.88	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(4)
14.67/5.88	Obligation:
14.67/5.88	Q DP problem:
14.67/5.88	The TRS P consists of the following rules:
14.67/5.88	
14.67/5.88	   B(b(a(a(x1)))) -> B(a(b(x1)))
14.67/5.88	   B(b(a(a(x1)))) -> B(x1)
14.67/5.88	   B(a(a(b(x1)))) -> B(a(b(a(x1))))
14.67/5.88	   B(a(a(b(x1)))) -> B(a(x1))
14.67/5.88	
14.67/5.88	The TRS R consists of the following rules:
14.67/5.88	
14.67/5.88	   b(b(a(a(x1)))) -> a(b(a(b(x1))))
14.67/5.88	   b(a(a(b(x1)))) -> b(a(b(a(x1))))
14.67/5.88	
14.67/5.88	Q is empty.
14.67/5.88	We have to consider all minimal (P,Q,R)-chains.
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(5) DependencyGraphProof (EQUIVALENT)
14.67/5.88	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node.
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(6)
14.67/5.88	Complex Obligation (AND)
14.67/5.88	
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(7)
14.67/5.88	Obligation:
14.67/5.88	Q DP problem:
14.67/5.88	The TRS P consists of the following rules:
14.67/5.88	
14.67/5.88	   B(a(a(b(x1)))) -> B(a(x1))
14.67/5.88	   B(a(a(b(x1)))) -> B(a(b(a(x1))))
14.67/5.88	
14.67/5.88	The TRS R consists of the following rules:
14.67/5.88	
14.67/5.88	   b(b(a(a(x1)))) -> a(b(a(b(x1))))
14.67/5.88	   b(a(a(b(x1)))) -> b(a(b(a(x1))))
14.67/5.88	
14.67/5.88	Q is empty.
14.67/5.88	We have to consider all minimal (P,Q,R)-chains.
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(8) UsableRulesProof (EQUIVALENT)
14.67/5.88	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.
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(9)
14.67/5.88	Obligation:
14.67/5.88	Q DP problem:
14.67/5.88	The TRS P consists of the following rules:
14.67/5.88	
14.67/5.88	   B(a(a(b(x1)))) -> B(a(x1))
14.67/5.88	   B(a(a(b(x1)))) -> B(a(b(a(x1))))
14.67/5.88	
14.67/5.88	The TRS R consists of the following rules:
14.67/5.88	
14.67/5.88	   b(a(a(b(x1)))) -> b(a(b(a(x1))))
14.67/5.88	
14.67/5.88	Q is empty.
14.67/5.88	We have to consider all minimal (P,Q,R)-chains.
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(10) DependencyGraphProof (EQUIVALENT)
14.67/5.88	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(11)
14.67/5.88	Obligation:
14.67/5.88	Q DP problem:
14.67/5.88	The TRS P consists of the following rules:
14.67/5.88	
14.67/5.88	   B(a(a(b(x1)))) -> B(a(x1))
14.67/5.88	
14.67/5.88	The TRS R consists of the following rules:
14.67/5.88	
14.67/5.88	   b(a(a(b(x1)))) -> b(a(b(a(x1))))
14.67/5.88	
14.67/5.88	Q is empty.
14.67/5.88	We have to consider all minimal (P,Q,R)-chains.
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(12) UsableRulesProof (EQUIVALENT)
14.67/5.88	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.
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(13)
14.67/5.88	Obligation:
14.67/5.88	Q DP problem:
14.67/5.88	The TRS P consists of the following rules:
14.67/5.88	
14.67/5.88	   B(a(a(b(x1)))) -> B(a(x1))
14.67/5.88	
14.67/5.88	R is empty.
14.67/5.88	Q is empty.
14.67/5.88	We have to consider all minimal (P,Q,R)-chains.
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(14) MRRProof (EQUIVALENT)
14.67/5.88	By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.
14.67/5.88	
14.67/5.88	Strictly oriented dependency pairs:
14.67/5.88	
14.67/5.88	   B(a(a(b(x1)))) -> B(a(x1))
14.67/5.88	
14.67/5.88	
14.67/5.88	Used ordering: Polynomial interpretation [POLO]:
14.67/5.88	
14.67/5.88	   POL(B(x_1)) = x_1
14.67/5.88	   POL(a(x_1)) = 2 + x_1
14.67/5.88	   POL(b(x_1)) = 2*x_1
14.67/5.88	
14.67/5.88	
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(15)
14.67/5.88	Obligation:
14.67/5.88	Q DP problem:
14.67/5.88	P is empty.
14.67/5.88	R is empty.
14.67/5.88	Q is empty.
14.67/5.88	We have to consider all minimal (P,Q,R)-chains.
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(16) PisEmptyProof (EQUIVALENT)
14.67/5.88	The TRS P is empty. Hence, there is no (P,Q,R) chain.
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(17)
14.67/5.88	YES
14.67/5.88	
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(18)
14.67/5.88	Obligation:
14.67/5.88	Q DP problem:
14.67/5.88	The TRS P consists of the following rules:
14.67/5.88	
14.67/5.88	   B(b(a(a(x1)))) -> B(x1)
14.67/5.88	
14.67/5.88	The TRS R consists of the following rules:
14.67/5.88	
14.67/5.88	   b(b(a(a(x1)))) -> a(b(a(b(x1))))
14.67/5.88	   b(a(a(b(x1)))) -> b(a(b(a(x1))))
14.67/5.88	
14.67/5.88	Q is empty.
14.67/5.88	We have to consider all minimal (P,Q,R)-chains.
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(19) UsableRulesProof (EQUIVALENT)
14.67/5.88	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.
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(20)
14.67/5.88	Obligation:
14.67/5.88	Q DP problem:
14.67/5.88	The TRS P consists of the following rules:
14.67/5.88	
14.67/5.88	   B(b(a(a(x1)))) -> B(x1)
14.67/5.88	
14.67/5.88	R is empty.
14.67/5.88	Q is empty.
14.67/5.88	We have to consider all minimal (P,Q,R)-chains.
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(21) QDPSizeChangeProof (EQUIVALENT)
14.67/5.88	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. 
14.67/5.88	
14.67/5.88	From the DPs we obtained the following set of size-change graphs:
14.67/5.88	*B(b(a(a(x1)))) -> B(x1)
14.67/5.88	The graph contains the following edges 1 > 1
14.67/5.88	
14.67/5.88	
14.67/5.88	----------------------------------------
14.67/5.88	
14.67/5.88	(22)
14.67/5.88	YES
14.84/5.93	EOF