16.79/5.14	YES
17.17/5.25	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
17.17/5.25	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
17.17/5.25	
17.17/5.25	
17.17/5.25	Termination w.r.t. Q of the given QTRS could be proven:
17.17/5.25	
17.17/5.25	(0) QTRS
17.17/5.25	(1) QTRSRRRProof [EQUIVALENT, 59 ms]
17.17/5.25	(2) QTRS
17.17/5.25	(3) QTRSRRRProof [EQUIVALENT, 3 ms]
17.17/5.25	(4) QTRS
17.17/5.25	(5) DependencyPairsProof [EQUIVALENT, 13 ms]
17.17/5.25	(6) QDP
17.17/5.25	(7) DependencyGraphProof [EQUIVALENT, 0 ms]
17.17/5.25	(8) AND
17.17/5.25	    (9) QDP
17.17/5.25	        (10) UsableRulesProof [EQUIVALENT, 0 ms]
17.17/5.25	        (11) QDP
17.17/5.25	        (12) QDPSizeChangeProof [EQUIVALENT, 0 ms]
17.17/5.25	        (13) YES
17.17/5.25	    (14) QDP
17.17/5.25	        (15) UsableRulesProof [EQUIVALENT, 0 ms]
17.17/5.25	        (16) QDP
17.17/5.25	        (17) QDPSizeChangeProof [EQUIVALENT, 0 ms]
17.17/5.25	        (18) YES
17.17/5.25	    (19) QDP
17.17/5.25	        (20) UsableRulesProof [EQUIVALENT, 0 ms]
17.17/5.25	        (21) QDP
17.17/5.25	        (22) QDPSizeChangeProof [EQUIVALENT, 0 ms]
17.17/5.25	        (23) YES
17.17/5.25	    (24) QDP
17.17/5.25	        (25) UsableRulesProof [EQUIVALENT, 0 ms]
17.17/5.25	        (26) QDP
17.17/5.25	        (27) QDPSizeChangeProof [EQUIVALENT, 0 ms]
17.17/5.25	        (28) YES
17.17/5.25	    (29) QDP
17.17/5.25	        (30) UsableRulesProof [EQUIVALENT, 0 ms]
17.17/5.25	        (31) QDP
17.17/5.25	        (32) QDPSizeChangeProof [EQUIVALENT, 0 ms]
17.17/5.25	        (33) YES
17.17/5.25	
17.17/5.25	
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(0)
17.17/5.25	Obligation:
17.17/5.25	Q restricted rewrite system:
17.17/5.25	The TRS R consists of the following rules:
17.17/5.25	
17.17/5.25	   q0(0(x1)) -> 0'(q1(x1))
17.17/5.25	   q1(0(x1)) -> 0(q1(x1))
17.17/5.25	   q1(1'(x1)) -> 1'(q1(x1))
17.17/5.25	   0(q1(1(x1))) -> q2(0(1'(x1)))
17.17/5.25	   0'(q1(1(x1))) -> q2(0'(1'(x1)))
17.17/5.25	   1'(q1(1(x1))) -> q2(1'(1'(x1)))
17.17/5.25	   0(q2(0(x1))) -> q2(0(0(x1)))
17.17/5.25	   0'(q2(0(x1))) -> q2(0'(0(x1)))
17.17/5.25	   1'(q2(0(x1))) -> q2(1'(0(x1)))
17.17/5.25	   0(q2(1'(x1))) -> q2(0(1'(x1)))
17.17/5.25	   0'(q2(1'(x1))) -> q2(0'(1'(x1)))
17.17/5.25	   1'(q2(1'(x1))) -> q2(1'(1'(x1)))
17.17/5.25	   q2(0'(x1)) -> 0'(q0(x1))
17.17/5.25	   q0(1'(x1)) -> 1'(q3(x1))
17.17/5.25	   q3(1'(x1)) -> 1'(q3(x1))
17.17/5.25	   q3(b(x1)) -> b(q4(x1))
17.17/5.25	
17.17/5.25	Q is empty.
17.17/5.25	
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(1) QTRSRRRProof (EQUIVALENT)
17.17/5.25	Used ordering:
17.17/5.25	Polynomial interpretation [POLO]:
17.17/5.25	
17.17/5.25	   POL(0(x_1)) = x_1
17.17/5.25	   POL(0'(x_1)) = x_1
17.17/5.25	   POL(1(x_1)) = 3 + x_1
17.17/5.25	   POL(1'(x_1)) = x_1
17.17/5.25	   POL(b(x_1)) = x_1
17.17/5.25	   POL(q0(x_1)) = 2 + x_1
17.17/5.25	   POL(q1(x_1)) = x_1
17.17/5.25	   POL(q2(x_1)) = 3 + x_1
17.17/5.25	   POL(q3(x_1)) = 1 + x_1
17.17/5.25	   POL(q4(x_1)) = x_1
17.17/5.25	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
17.17/5.25	
17.17/5.25	   q0(0(x1)) -> 0'(q1(x1))
17.17/5.25	   q2(0'(x1)) -> 0'(q0(x1))
17.17/5.25	   q0(1'(x1)) -> 1'(q3(x1))
17.17/5.25	   q3(b(x1)) -> b(q4(x1))
17.17/5.25	
17.17/5.25	
17.17/5.25	
17.17/5.25	
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(2)
17.17/5.25	Obligation:
17.17/5.25	Q restricted rewrite system:
17.17/5.25	The TRS R consists of the following rules:
17.17/5.25	
17.17/5.25	   q1(0(x1)) -> 0(q1(x1))
17.17/5.25	   q1(1'(x1)) -> 1'(q1(x1))
17.17/5.25	   0(q1(1(x1))) -> q2(0(1'(x1)))
17.17/5.25	   0'(q1(1(x1))) -> q2(0'(1'(x1)))
17.17/5.25	   1'(q1(1(x1))) -> q2(1'(1'(x1)))
17.17/5.25	   0(q2(0(x1))) -> q2(0(0(x1)))
17.17/5.25	   0'(q2(0(x1))) -> q2(0'(0(x1)))
17.17/5.25	   1'(q2(0(x1))) -> q2(1'(0(x1)))
17.17/5.25	   0(q2(1'(x1))) -> q2(0(1'(x1)))
17.17/5.25	   0'(q2(1'(x1))) -> q2(0'(1'(x1)))
17.17/5.25	   1'(q2(1'(x1))) -> q2(1'(1'(x1)))
17.17/5.25	   q3(1'(x1)) -> 1'(q3(x1))
17.17/5.25	
17.17/5.25	Q is empty.
17.17/5.25	
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(3) QTRSRRRProof (EQUIVALENT)
17.17/5.25	Used ordering:
17.17/5.25	Polynomial interpretation [POLO]:
17.17/5.25	
17.17/5.25	   POL(0(x_1)) = x_1
17.17/5.25	   POL(0'(x_1)) = x_1
17.17/5.25	   POL(1(x_1)) = 1 + x_1
17.17/5.25	   POL(1'(x_1)) = x_1
17.17/5.25	   POL(q1(x_1)) = x_1
17.17/5.25	   POL(q2(x_1)) = x_1
17.17/5.25	   POL(q3(x_1)) = x_1
17.17/5.25	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
17.17/5.25	
17.17/5.25	   0(q1(1(x1))) -> q2(0(1'(x1)))
17.17/5.25	   0'(q1(1(x1))) -> q2(0'(1'(x1)))
17.17/5.25	   1'(q1(1(x1))) -> q2(1'(1'(x1)))
17.17/5.25	
17.17/5.25	
17.17/5.25	
17.17/5.25	
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(4)
17.17/5.25	Obligation:
17.17/5.25	Q restricted rewrite system:
17.17/5.25	The TRS R consists of the following rules:
17.17/5.25	
17.17/5.25	   q1(0(x1)) -> 0(q1(x1))
17.17/5.25	   q1(1'(x1)) -> 1'(q1(x1))
17.17/5.25	   0(q2(0(x1))) -> q2(0(0(x1)))
17.17/5.25	   0'(q2(0(x1))) -> q2(0'(0(x1)))
17.17/5.25	   1'(q2(0(x1))) -> q2(1'(0(x1)))
17.17/5.25	   0(q2(1'(x1))) -> q2(0(1'(x1)))
17.17/5.25	   0'(q2(1'(x1))) -> q2(0'(1'(x1)))
17.17/5.25	   1'(q2(1'(x1))) -> q2(1'(1'(x1)))
17.17/5.25	   q3(1'(x1)) -> 1'(q3(x1))
17.17/5.25	
17.17/5.25	Q is empty.
17.17/5.25	
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(5) DependencyPairsProof (EQUIVALENT)
17.17/5.25	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(6)
17.17/5.25	Obligation:
17.17/5.25	Q DP problem:
17.17/5.25	The TRS P consists of the following rules:
17.17/5.25	
17.17/5.25	   Q1(0(x1)) -> 0^1(q1(x1))
17.17/5.25	   Q1(0(x1)) -> Q1(x1)
17.17/5.25	   Q1(1'(x1)) -> 1'^1(q1(x1))
17.17/5.25	   Q1(1'(x1)) -> Q1(x1)
17.17/5.25	   0^1(q2(0(x1))) -> 0^1(0(x1))
17.17/5.25	   0'^1(q2(0(x1))) -> 0'^1(0(x1))
17.17/5.25	   1'^1(q2(0(x1))) -> 1'^1(0(x1))
17.17/5.25	   0^1(q2(1'(x1))) -> 0^1(1'(x1))
17.17/5.25	   0'^1(q2(1'(x1))) -> 0'^1(1'(x1))
17.17/5.25	   1'^1(q2(1'(x1))) -> 1'^1(1'(x1))
17.17/5.25	   Q3(1'(x1)) -> 1'^1(q3(x1))
17.17/5.25	   Q3(1'(x1)) -> Q3(x1)
17.17/5.25	
17.17/5.25	The TRS R consists of the following rules:
17.17/5.25	
17.17/5.25	   q1(0(x1)) -> 0(q1(x1))
17.17/5.25	   q1(1'(x1)) -> 1'(q1(x1))
17.17/5.25	   0(q2(0(x1))) -> q2(0(0(x1)))
17.17/5.25	   0'(q2(0(x1))) -> q2(0'(0(x1)))
17.17/5.25	   1'(q2(0(x1))) -> q2(1'(0(x1)))
17.17/5.25	   0(q2(1'(x1))) -> q2(0(1'(x1)))
17.17/5.25	   0'(q2(1'(x1))) -> q2(0'(1'(x1)))
17.17/5.25	   1'(q2(1'(x1))) -> q2(1'(1'(x1)))
17.17/5.25	   q3(1'(x1)) -> 1'(q3(x1))
17.17/5.25	
17.17/5.25	Q is empty.
17.17/5.25	We have to consider all minimal (P,Q,R)-chains.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(7) DependencyGraphProof (EQUIVALENT)
17.17/5.25	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 5 SCCs with 3 less nodes.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(8)
17.17/5.25	Complex Obligation (AND)
17.17/5.25	
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(9)
17.17/5.25	Obligation:
17.17/5.25	Q DP problem:
17.17/5.25	The TRS P consists of the following rules:
17.17/5.25	
17.17/5.25	   1'^1(q2(1'(x1))) -> 1'^1(1'(x1))
17.17/5.25	   1'^1(q2(0(x1))) -> 1'^1(0(x1))
17.17/5.25	
17.17/5.25	The TRS R consists of the following rules:
17.17/5.25	
17.17/5.25	   q1(0(x1)) -> 0(q1(x1))
17.17/5.25	   q1(1'(x1)) -> 1'(q1(x1))
17.17/5.25	   0(q2(0(x1))) -> q2(0(0(x1)))
17.17/5.25	   0'(q2(0(x1))) -> q2(0'(0(x1)))
17.17/5.25	   1'(q2(0(x1))) -> q2(1'(0(x1)))
17.17/5.25	   0(q2(1'(x1))) -> q2(0(1'(x1)))
17.17/5.25	   0'(q2(1'(x1))) -> q2(0'(1'(x1)))
17.17/5.25	   1'(q2(1'(x1))) -> q2(1'(1'(x1)))
17.17/5.25	   q3(1'(x1)) -> 1'(q3(x1))
17.17/5.25	
17.17/5.25	Q is empty.
17.17/5.25	We have to consider all minimal (P,Q,R)-chains.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(10) UsableRulesProof (EQUIVALENT)
17.17/5.25	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.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(11)
17.17/5.25	Obligation:
17.17/5.25	Q DP problem:
17.17/5.25	The TRS P consists of the following rules:
17.17/5.25	
17.17/5.25	   1'^1(q2(1'(x1))) -> 1'^1(1'(x1))
17.17/5.25	   1'^1(q2(0(x1))) -> 1'^1(0(x1))
17.17/5.25	
17.17/5.25	The TRS R consists of the following rules:
17.17/5.25	
17.17/5.25	   0(q2(0(x1))) -> q2(0(0(x1)))
17.17/5.25	   0(q2(1'(x1))) -> q2(0(1'(x1)))
17.17/5.25	   1'(q2(0(x1))) -> q2(1'(0(x1)))
17.17/5.25	   1'(q2(1'(x1))) -> q2(1'(1'(x1)))
17.17/5.25	
17.17/5.25	Q is empty.
17.17/5.25	We have to consider all minimal (P,Q,R)-chains.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(12) QDPSizeChangeProof (EQUIVALENT)
17.17/5.25	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. 
17.17/5.25	
17.17/5.25	From the DPs we obtained the following set of size-change graphs:
17.17/5.25	*1'^1(q2(1'(x1))) -> 1'^1(1'(x1))
17.17/5.25	The graph contains the following edges 1 > 1
17.17/5.25	
17.17/5.25	
17.17/5.25	*1'^1(q2(0(x1))) -> 1'^1(0(x1))
17.17/5.25	The graph contains the following edges 1 > 1
17.17/5.25	
17.17/5.25	
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(13)
17.17/5.25	YES
17.17/5.25	
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(14)
17.17/5.25	Obligation:
17.17/5.25	Q DP problem:
17.17/5.25	The TRS P consists of the following rules:
17.17/5.25	
17.17/5.25	   Q3(1'(x1)) -> Q3(x1)
17.17/5.25	
17.17/5.25	The TRS R consists of the following rules:
17.17/5.25	
17.17/5.25	   q1(0(x1)) -> 0(q1(x1))
17.17/5.25	   q1(1'(x1)) -> 1'(q1(x1))
17.17/5.25	   0(q2(0(x1))) -> q2(0(0(x1)))
17.17/5.25	   0'(q2(0(x1))) -> q2(0'(0(x1)))
17.17/5.25	   1'(q2(0(x1))) -> q2(1'(0(x1)))
17.17/5.25	   0(q2(1'(x1))) -> q2(0(1'(x1)))
17.17/5.25	   0'(q2(1'(x1))) -> q2(0'(1'(x1)))
17.17/5.25	   1'(q2(1'(x1))) -> q2(1'(1'(x1)))
17.17/5.25	   q3(1'(x1)) -> 1'(q3(x1))
17.17/5.25	
17.17/5.25	Q is empty.
17.17/5.25	We have to consider all minimal (P,Q,R)-chains.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(15) UsableRulesProof (EQUIVALENT)
17.17/5.25	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.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(16)
17.17/5.25	Obligation:
17.17/5.25	Q DP problem:
17.17/5.25	The TRS P consists of the following rules:
17.17/5.25	
17.17/5.25	   Q3(1'(x1)) -> Q3(x1)
17.17/5.25	
17.17/5.25	R is empty.
17.17/5.25	Q is empty.
17.17/5.25	We have to consider all minimal (P,Q,R)-chains.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(17) QDPSizeChangeProof (EQUIVALENT)
17.17/5.25	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. 
17.17/5.25	
17.17/5.25	From the DPs we obtained the following set of size-change graphs:
17.17/5.25	*Q3(1'(x1)) -> Q3(x1)
17.17/5.25	The graph contains the following edges 1 > 1
17.17/5.25	
17.17/5.25	
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(18)
17.17/5.25	YES
17.17/5.25	
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(19)
17.17/5.25	Obligation:
17.17/5.25	Q DP problem:
17.17/5.25	The TRS P consists of the following rules:
17.17/5.25	
17.17/5.25	   0'^1(q2(1'(x1))) -> 0'^1(1'(x1))
17.17/5.25	   0'^1(q2(0(x1))) -> 0'^1(0(x1))
17.17/5.25	
17.17/5.25	The TRS R consists of the following rules:
17.17/5.25	
17.17/5.25	   q1(0(x1)) -> 0(q1(x1))
17.17/5.25	   q1(1'(x1)) -> 1'(q1(x1))
17.17/5.25	   0(q2(0(x1))) -> q2(0(0(x1)))
17.17/5.25	   0'(q2(0(x1))) -> q2(0'(0(x1)))
17.17/5.25	   1'(q2(0(x1))) -> q2(1'(0(x1)))
17.17/5.25	   0(q2(1'(x1))) -> q2(0(1'(x1)))
17.17/5.25	   0'(q2(1'(x1))) -> q2(0'(1'(x1)))
17.17/5.25	   1'(q2(1'(x1))) -> q2(1'(1'(x1)))
17.17/5.25	   q3(1'(x1)) -> 1'(q3(x1))
17.17/5.25	
17.17/5.25	Q is empty.
17.17/5.25	We have to consider all minimal (P,Q,R)-chains.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(20) UsableRulesProof (EQUIVALENT)
17.17/5.25	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.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(21)
17.17/5.25	Obligation:
17.17/5.25	Q DP problem:
17.17/5.25	The TRS P consists of the following rules:
17.17/5.25	
17.17/5.25	   0'^1(q2(1'(x1))) -> 0'^1(1'(x1))
17.17/5.25	   0'^1(q2(0(x1))) -> 0'^1(0(x1))
17.17/5.25	
17.17/5.25	The TRS R consists of the following rules:
17.17/5.25	
17.17/5.25	   0(q2(0(x1))) -> q2(0(0(x1)))
17.17/5.25	   0(q2(1'(x1))) -> q2(0(1'(x1)))
17.17/5.25	   1'(q2(0(x1))) -> q2(1'(0(x1)))
17.17/5.25	   1'(q2(1'(x1))) -> q2(1'(1'(x1)))
17.17/5.25	
17.17/5.25	Q is empty.
17.17/5.25	We have to consider all minimal (P,Q,R)-chains.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(22) QDPSizeChangeProof (EQUIVALENT)
17.17/5.25	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. 
17.17/5.25	
17.17/5.25	From the DPs we obtained the following set of size-change graphs:
17.17/5.25	*0'^1(q2(1'(x1))) -> 0'^1(1'(x1))
17.17/5.25	The graph contains the following edges 1 > 1
17.17/5.25	
17.17/5.25	
17.17/5.25	*0'^1(q2(0(x1))) -> 0'^1(0(x1))
17.17/5.25	The graph contains the following edges 1 > 1
17.17/5.25	
17.17/5.25	
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(23)
17.17/5.25	YES
17.17/5.25	
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(24)
17.17/5.25	Obligation:
17.17/5.25	Q DP problem:
17.17/5.25	The TRS P consists of the following rules:
17.17/5.25	
17.17/5.25	   0^1(q2(1'(x1))) -> 0^1(1'(x1))
17.17/5.25	   0^1(q2(0(x1))) -> 0^1(0(x1))
17.17/5.25	
17.17/5.25	The TRS R consists of the following rules:
17.17/5.25	
17.17/5.25	   q1(0(x1)) -> 0(q1(x1))
17.17/5.25	   q1(1'(x1)) -> 1'(q1(x1))
17.17/5.25	   0(q2(0(x1))) -> q2(0(0(x1)))
17.17/5.25	   0'(q2(0(x1))) -> q2(0'(0(x1)))
17.17/5.25	   1'(q2(0(x1))) -> q2(1'(0(x1)))
17.17/5.25	   0(q2(1'(x1))) -> q2(0(1'(x1)))
17.17/5.25	   0'(q2(1'(x1))) -> q2(0'(1'(x1)))
17.17/5.25	   1'(q2(1'(x1))) -> q2(1'(1'(x1)))
17.17/5.25	   q3(1'(x1)) -> 1'(q3(x1))
17.17/5.25	
17.17/5.25	Q is empty.
17.17/5.25	We have to consider all minimal (P,Q,R)-chains.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(25) UsableRulesProof (EQUIVALENT)
17.17/5.25	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.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(26)
17.17/5.25	Obligation:
17.17/5.25	Q DP problem:
17.17/5.25	The TRS P consists of the following rules:
17.17/5.25	
17.17/5.25	   0^1(q2(1'(x1))) -> 0^1(1'(x1))
17.17/5.25	   0^1(q2(0(x1))) -> 0^1(0(x1))
17.17/5.25	
17.17/5.25	The TRS R consists of the following rules:
17.17/5.25	
17.17/5.25	   0(q2(0(x1))) -> q2(0(0(x1)))
17.17/5.25	   0(q2(1'(x1))) -> q2(0(1'(x1)))
17.17/5.25	   1'(q2(0(x1))) -> q2(1'(0(x1)))
17.17/5.25	   1'(q2(1'(x1))) -> q2(1'(1'(x1)))
17.17/5.25	
17.17/5.25	Q is empty.
17.17/5.25	We have to consider all minimal (P,Q,R)-chains.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(27) QDPSizeChangeProof (EQUIVALENT)
17.17/5.25	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. 
17.17/5.25	
17.17/5.25	From the DPs we obtained the following set of size-change graphs:
17.17/5.25	*0^1(q2(1'(x1))) -> 0^1(1'(x1))
17.17/5.25	The graph contains the following edges 1 > 1
17.17/5.25	
17.17/5.25	
17.17/5.25	*0^1(q2(0(x1))) -> 0^1(0(x1))
17.17/5.25	The graph contains the following edges 1 > 1
17.17/5.25	
17.17/5.25	
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(28)
17.17/5.25	YES
17.17/5.25	
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(29)
17.17/5.25	Obligation:
17.17/5.25	Q DP problem:
17.17/5.25	The TRS P consists of the following rules:
17.17/5.25	
17.17/5.25	   Q1(1'(x1)) -> Q1(x1)
17.17/5.25	   Q1(0(x1)) -> Q1(x1)
17.17/5.25	
17.17/5.25	The TRS R consists of the following rules:
17.17/5.25	
17.17/5.25	   q1(0(x1)) -> 0(q1(x1))
17.17/5.25	   q1(1'(x1)) -> 1'(q1(x1))
17.17/5.25	   0(q2(0(x1))) -> q2(0(0(x1)))
17.17/5.25	   0'(q2(0(x1))) -> q2(0'(0(x1)))
17.17/5.25	   1'(q2(0(x1))) -> q2(1'(0(x1)))
17.17/5.25	   0(q2(1'(x1))) -> q2(0(1'(x1)))
17.17/5.25	   0'(q2(1'(x1))) -> q2(0'(1'(x1)))
17.17/5.25	   1'(q2(1'(x1))) -> q2(1'(1'(x1)))
17.17/5.25	   q3(1'(x1)) -> 1'(q3(x1))
17.17/5.25	
17.17/5.25	Q is empty.
17.17/5.25	We have to consider all minimal (P,Q,R)-chains.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(30) UsableRulesProof (EQUIVALENT)
17.17/5.25	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.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(31)
17.17/5.25	Obligation:
17.17/5.25	Q DP problem:
17.17/5.25	The TRS P consists of the following rules:
17.17/5.25	
17.17/5.25	   Q1(1'(x1)) -> Q1(x1)
17.17/5.25	   Q1(0(x1)) -> Q1(x1)
17.17/5.25	
17.17/5.25	R is empty.
17.17/5.25	Q is empty.
17.17/5.25	We have to consider all minimal (P,Q,R)-chains.
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(32) QDPSizeChangeProof (EQUIVALENT)
17.17/5.25	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. 
17.17/5.25	
17.17/5.25	From the DPs we obtained the following set of size-change graphs:
17.17/5.25	*Q1(1'(x1)) -> Q1(x1)
17.17/5.25	The graph contains the following edges 1 > 1
17.17/5.25	
17.17/5.25	
17.17/5.25	*Q1(0(x1)) -> Q1(x1)
17.17/5.25	The graph contains the following edges 1 > 1
17.17/5.25	
17.17/5.25	
17.17/5.25	----------------------------------------
17.17/5.25	
17.17/5.25	(33)
17.17/5.25	YES
17.38/5.35	EOF