28.67/8.27	YES
30.80/9.12	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
30.80/9.12	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
30.80/9.12	
30.80/9.12	
30.80/9.12	Termination w.r.t. Q of the given QTRS could be proven:
30.80/9.12	
30.80/9.12	(0) QTRS
30.80/9.12	(1) DependencyPairsProof [EQUIVALENT, 14 ms]
30.80/9.12	(2) QDP
30.80/9.12	(3) DependencyGraphProof [EQUIVALENT, 10 ms]
30.80/9.12	(4) AND
30.80/9.12	    (5) QDP
30.80/9.12	        (6) UsableRulesProof [EQUIVALENT, 0 ms]
30.80/9.12	        (7) QDP
30.80/9.12	        (8) QDPSizeChangeProof [EQUIVALENT, 2 ms]
30.80/9.12	        (9) YES
30.80/9.12	    (10) QDP
30.80/9.12	        (11) UsableRulesProof [EQUIVALENT, 0 ms]
30.80/9.12	        (12) QDP
30.80/9.12	        (13) QDPOrderProof [EQUIVALENT, 8 ms]
30.80/9.12	        (14) QDP
30.80/9.12	        (15) PisEmptyProof [EQUIVALENT, 0 ms]
30.80/9.12	        (16) YES
30.80/9.12	
30.80/9.12	
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(0)
30.80/9.12	Obligation:
30.80/9.12	Q restricted rewrite system:
30.80/9.12	The TRS R consists of the following rules:
30.80/9.12	
30.80/9.12	   a(x1) -> b(c(x1))
30.80/9.12	   a(b(x1)) -> b(a(x1))
30.80/9.12	   d(c(x1)) -> d(a(x1))
30.80/9.12	   a(c(x1)) -> c(a(x1))
30.80/9.12	
30.80/9.12	Q is empty.
30.80/9.12	
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(1) DependencyPairsProof (EQUIVALENT)
30.80/9.12	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(2)
30.80/9.12	Obligation:
30.80/9.12	Q DP problem:
30.80/9.12	The TRS P consists of the following rules:
30.80/9.12	
30.80/9.12	   A(b(x1)) -> A(x1)
30.80/9.12	   D(c(x1)) -> D(a(x1))
30.80/9.12	   D(c(x1)) -> A(x1)
30.80/9.12	   A(c(x1)) -> A(x1)
30.80/9.12	
30.80/9.12	The TRS R consists of the following rules:
30.80/9.12	
30.80/9.12	   a(x1) -> b(c(x1))
30.80/9.12	   a(b(x1)) -> b(a(x1))
30.80/9.12	   d(c(x1)) -> d(a(x1))
30.80/9.12	   a(c(x1)) -> c(a(x1))
30.80/9.12	
30.80/9.12	Q is empty.
30.80/9.12	We have to consider all minimal (P,Q,R)-chains.
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(3) DependencyGraphProof (EQUIVALENT)
30.80/9.12	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node.
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(4)
30.80/9.12	Complex Obligation (AND)
30.80/9.12	
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(5)
30.80/9.12	Obligation:
30.80/9.12	Q DP problem:
30.80/9.12	The TRS P consists of the following rules:
30.80/9.12	
30.80/9.12	   A(c(x1)) -> A(x1)
30.80/9.12	   A(b(x1)) -> A(x1)
30.80/9.12	
30.80/9.12	The TRS R consists of the following rules:
30.80/9.12	
30.80/9.12	   a(x1) -> b(c(x1))
30.80/9.12	   a(b(x1)) -> b(a(x1))
30.80/9.12	   d(c(x1)) -> d(a(x1))
30.80/9.12	   a(c(x1)) -> c(a(x1))
30.80/9.12	
30.80/9.12	Q is empty.
30.80/9.12	We have to consider all minimal (P,Q,R)-chains.
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(6) UsableRulesProof (EQUIVALENT)
30.80/9.12	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.
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(7)
30.80/9.12	Obligation:
30.80/9.12	Q DP problem:
30.80/9.12	The TRS P consists of the following rules:
30.80/9.12	
30.80/9.12	   A(c(x1)) -> A(x1)
30.80/9.12	   A(b(x1)) -> A(x1)
30.80/9.12	
30.80/9.12	R is empty.
30.80/9.12	Q is empty.
30.80/9.12	We have to consider all minimal (P,Q,R)-chains.
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(8) QDPSizeChangeProof (EQUIVALENT)
30.80/9.12	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. 
30.80/9.12	
30.80/9.12	From the DPs we obtained the following set of size-change graphs:
30.80/9.12	*A(c(x1)) -> A(x1)
30.80/9.12	The graph contains the following edges 1 > 1
30.80/9.12	
30.80/9.12	
30.80/9.12	*A(b(x1)) -> A(x1)
30.80/9.12	The graph contains the following edges 1 > 1
30.80/9.12	
30.80/9.12	
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(9)
30.80/9.12	YES
30.80/9.12	
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(10)
30.80/9.12	Obligation:
30.80/9.12	Q DP problem:
30.80/9.12	The TRS P consists of the following rules:
30.80/9.12	
30.80/9.12	   D(c(x1)) -> D(a(x1))
30.80/9.12	
30.80/9.12	The TRS R consists of the following rules:
30.80/9.12	
30.80/9.12	   a(x1) -> b(c(x1))
30.80/9.12	   a(b(x1)) -> b(a(x1))
30.80/9.12	   d(c(x1)) -> d(a(x1))
30.80/9.12	   a(c(x1)) -> c(a(x1))
30.80/9.12	
30.80/9.12	Q is empty.
30.80/9.12	We have to consider all minimal (P,Q,R)-chains.
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(11) UsableRulesProof (EQUIVALENT)
30.80/9.12	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.
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(12)
30.80/9.12	Obligation:
30.80/9.12	Q DP problem:
30.80/9.12	The TRS P consists of the following rules:
30.80/9.12	
30.80/9.12	   D(c(x1)) -> D(a(x1))
30.80/9.12	
30.80/9.12	The TRS R consists of the following rules:
30.80/9.12	
30.80/9.12	   a(x1) -> b(c(x1))
30.80/9.12	   a(b(x1)) -> b(a(x1))
30.80/9.12	   a(c(x1)) -> c(a(x1))
30.80/9.12	
30.80/9.12	Q is empty.
30.80/9.12	We have to consider all minimal (P,Q,R)-chains.
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(13) QDPOrderProof (EQUIVALENT)
30.80/9.12	We use the reduction pair processor [LPAR04,JAR06].
30.80/9.12	
30.80/9.12	
30.80/9.12	The following pairs can be oriented strictly and are deleted.
30.80/9.12	
30.80/9.12	   D(c(x1)) -> D(a(x1))
30.80/9.12	The remaining pairs can at least be oriented weakly.
30.80/9.12	Used ordering:  Polynomial interpretation [POLO]:
30.80/9.12	
30.80/9.12	   POL(D(x_1)) = x_1
30.80/9.12	   POL(a(x_1)) = x_1
30.80/9.12	   POL(b(x_1)) = 0
30.80/9.12	   POL(c(x_1)) = 1 + x_1
30.80/9.12	
30.80/9.12	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
30.80/9.12	
30.80/9.12	   a(x1) -> b(c(x1))
30.80/9.12	   a(b(x1)) -> b(a(x1))
30.80/9.12	   a(c(x1)) -> c(a(x1))
30.80/9.12	
30.80/9.12	
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(14)
30.80/9.12	Obligation:
30.80/9.12	Q DP problem:
30.80/9.12	P is empty.
30.80/9.12	The TRS R consists of the following rules:
30.80/9.12	
30.80/9.12	   a(x1) -> b(c(x1))
30.80/9.12	   a(b(x1)) -> b(a(x1))
30.80/9.12	   a(c(x1)) -> c(a(x1))
30.80/9.12	
30.80/9.12	Q is empty.
30.80/9.12	We have to consider all minimal (P,Q,R)-chains.
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(15) PisEmptyProof (EQUIVALENT)
30.80/9.12	The TRS P is empty. Hence, there is no (P,Q,R) chain.
30.80/9.12	----------------------------------------
30.80/9.12	
30.80/9.12	(16)
30.80/9.12	YES
31.14/10.43	EOF