14.20/4.49	YES
14.80/4.58	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
14.80/4.58	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
14.80/4.58	
14.80/4.58	
14.80/4.58	Termination w.r.t. Q of the given QTRS could be proven:
14.80/4.58	
14.80/4.58	(0) QTRS
14.80/4.58	(1) DependencyPairsProof [EQUIVALENT, 16 ms]
14.80/4.58	(2) QDP
14.80/4.58	(3) DependencyGraphProof [EQUIVALENT, 5 ms]
14.80/4.58	(4) AND
14.80/4.58	    (5) QDP
14.80/4.58	        (6) QDPSizeChangeProof [EQUIVALENT, 0 ms]
14.80/4.58	        (7) YES
14.80/4.58	    (8) QDP
14.80/4.58	        (9) MRRProof [EQUIVALENT, 48 ms]
14.80/4.58	        (10) QDP
14.80/4.58	        (11) PisEmptyProof [EQUIVALENT, 0 ms]
14.80/4.58	        (12) YES
14.80/4.58	
14.80/4.58	
14.80/4.58	----------------------------------------
14.80/4.58	
14.80/4.58	(0)
14.80/4.58	Obligation:
14.80/4.58	Q restricted rewrite system:
14.80/4.58	The TRS R consists of the following rules:
14.80/4.58	
14.80/4.58	   a(b(b(b(x1)))) -> b(a(a(b(x1))))
14.80/4.58	   b(a(a(a(x1)))) -> b(b(a(a(x1))))
14.80/4.58	   a(b(a(b(x1)))) -> b(b(a(a(x1))))
14.80/4.58	
14.80/4.58	Q is empty.
14.80/4.58	
14.80/4.58	----------------------------------------
14.80/4.58	
14.80/4.58	(1) DependencyPairsProof (EQUIVALENT)
14.80/4.58	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
14.80/4.58	----------------------------------------
14.80/4.58	
14.80/4.58	(2)
14.80/4.58	Obligation:
14.80/4.58	Q DP problem:
14.80/4.58	The TRS P consists of the following rules:
14.80/4.58	
14.80/4.58	   A(b(b(b(x1)))) -> B(a(a(b(x1))))
14.80/4.58	   A(b(b(b(x1)))) -> A(a(b(x1)))
14.80/4.58	   A(b(b(b(x1)))) -> A(b(x1))
14.80/4.58	   B(a(a(a(x1)))) -> B(b(a(a(x1))))
14.80/4.58	   B(a(a(a(x1)))) -> B(a(a(x1)))
14.80/4.58	   A(b(a(b(x1)))) -> B(b(a(a(x1))))
14.80/4.58	   A(b(a(b(x1)))) -> B(a(a(x1)))
14.80/4.58	   A(b(a(b(x1)))) -> A(a(x1))
14.80/4.58	   A(b(a(b(x1)))) -> A(x1)
14.80/4.58	
14.80/4.58	The TRS R consists of the following rules:
14.80/4.58	
14.80/4.58	   a(b(b(b(x1)))) -> b(a(a(b(x1))))
14.80/4.58	   b(a(a(a(x1)))) -> b(b(a(a(x1))))
14.80/4.58	   a(b(a(b(x1)))) -> b(b(a(a(x1))))
14.80/4.58	
14.80/4.58	Q is empty.
14.80/4.58	We have to consider all minimal (P,Q,R)-chains.
14.80/4.58	----------------------------------------
14.80/4.58	
14.80/4.58	(3) DependencyGraphProof (EQUIVALENT)
14.80/4.58	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 4 less nodes.
14.80/4.58	----------------------------------------
14.80/4.58	
14.80/4.58	(4)
14.80/4.58	Complex Obligation (AND)
14.80/4.58	
14.80/4.58	----------------------------------------
14.80/4.58	
14.80/4.58	(5)
14.80/4.58	Obligation:
14.80/4.58	Q DP problem:
14.80/4.58	The TRS P consists of the following rules:
14.80/4.58	
14.80/4.58	   B(a(a(a(x1)))) -> B(a(a(x1)))
14.80/4.58	
14.80/4.58	The TRS R consists of the following rules:
14.80/4.58	
14.80/4.58	   a(b(b(b(x1)))) -> b(a(a(b(x1))))
14.80/4.58	   b(a(a(a(x1)))) -> b(b(a(a(x1))))
14.80/4.58	   a(b(a(b(x1)))) -> b(b(a(a(x1))))
14.80/4.58	
14.80/4.58	Q is empty.
14.80/4.58	We have to consider all minimal (P,Q,R)-chains.
14.80/4.58	----------------------------------------
14.80/4.58	
14.80/4.58	(6) QDPSizeChangeProof (EQUIVALENT)
14.80/4.58	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.80/4.58	
14.80/4.58	From the DPs we obtained the following set of size-change graphs:
14.80/4.58	*B(a(a(a(x1)))) -> B(a(a(x1)))
14.80/4.58	The graph contains the following edges 1 > 1
14.80/4.58	
14.80/4.58	
14.80/4.58	----------------------------------------
14.80/4.58	
14.80/4.58	(7)
14.80/4.58	YES
14.80/4.58	
14.80/4.58	----------------------------------------
14.80/4.58	
14.80/4.58	(8)
14.80/4.58	Obligation:
14.80/4.58	Q DP problem:
14.80/4.58	The TRS P consists of the following rules:
14.80/4.58	
14.80/4.58	   A(b(b(b(x1)))) -> A(b(x1))
14.80/4.58	   A(b(b(b(x1)))) -> A(a(b(x1)))
14.80/4.58	   A(b(a(b(x1)))) -> A(a(x1))
14.80/4.58	   A(b(a(b(x1)))) -> A(x1)
14.80/4.58	
14.80/4.58	The TRS R consists of the following rules:
14.80/4.58	
14.80/4.58	   a(b(b(b(x1)))) -> b(a(a(b(x1))))
14.80/4.58	   b(a(a(a(x1)))) -> b(b(a(a(x1))))
14.80/4.58	   a(b(a(b(x1)))) -> b(b(a(a(x1))))
14.80/4.58	
14.80/4.58	Q is empty.
14.80/4.58	We have to consider all minimal (P,Q,R)-chains.
14.80/4.58	----------------------------------------
14.80/4.58	
14.80/4.58	(9) MRRProof (EQUIVALENT)
14.80/4.58	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.80/4.58	
14.80/4.58	Strictly oriented dependency pairs:
14.80/4.58	
14.80/4.58	   A(b(b(b(x1)))) -> A(b(x1))
14.80/4.58	   A(b(b(b(x1)))) -> A(a(b(x1)))
14.80/4.58	   A(b(a(b(x1)))) -> A(a(x1))
14.80/4.58	   A(b(a(b(x1)))) -> A(x1)
14.80/4.58	
14.80/4.58	
14.80/4.58	Used ordering: Polynomial interpretation [POLO]:
14.80/4.58	
14.80/4.58	   POL(A(x_1)) = 2*x_1
14.80/4.58	   POL(a(x_1)) = 2 + x_1
14.80/4.58	   POL(b(x_1)) = 2 + x_1
14.80/4.58	
14.80/4.58	
14.80/4.58	----------------------------------------
14.80/4.58	
14.80/4.58	(10)
14.80/4.58	Obligation:
14.80/4.58	Q DP problem:
14.80/4.58	P is empty.
14.80/4.58	The TRS R consists of the following rules:
14.80/4.58	
14.80/4.58	   a(b(b(b(x1)))) -> b(a(a(b(x1))))
14.80/4.58	   b(a(a(a(x1)))) -> b(b(a(a(x1))))
14.80/4.58	   a(b(a(b(x1)))) -> b(b(a(a(x1))))
14.80/4.58	
14.80/4.58	Q is empty.
14.80/4.58	We have to consider all minimal (P,Q,R)-chains.
14.80/4.58	----------------------------------------
14.80/4.58	
14.80/4.58	(11) PisEmptyProof (EQUIVALENT)
14.80/4.58	The TRS P is empty. Hence, there is no (P,Q,R) chain.
14.80/4.58	----------------------------------------
14.80/4.58	
14.80/4.58	(12)
14.80/4.59	YES
15.14/4.79	EOF