27.01/7.87	YES
27.34/7.90	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
27.34/7.90	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
27.34/7.90	
27.34/7.90	
27.34/7.90	Termination w.r.t. Q of the given QTRS could be proven:
27.34/7.90	
27.34/7.90	(0) QTRS
27.34/7.90	(1) DependencyPairsProof [EQUIVALENT, 37 ms]
27.34/7.90	(2) QDP
27.34/7.90	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
27.34/7.90	(4) AND
27.34/7.90	    (5) QDP
27.34/7.90	        (6) UsableRulesProof [EQUIVALENT, 3 ms]
27.34/7.90	        (7) QDP
27.34/7.90	        (8) QDPSizeChangeProof [EQUIVALENT, 0 ms]
27.34/7.90	        (9) YES
27.34/7.90	    (10) QDP
27.34/7.90	        (11) UsableRulesProof [EQUIVALENT, 2 ms]
27.34/7.90	        (12) QDP
27.34/7.90	        (13) QDPSizeChangeProof [EQUIVALENT, 0 ms]
27.34/7.90	        (14) YES
27.34/7.90	    (15) QDP
27.34/7.90	        (16) UsableRulesProof [EQUIVALENT, 0 ms]
27.34/7.90	        (17) QDP
27.34/7.90	        (18) MRRProof [EQUIVALENT, 23 ms]
27.34/7.90	        (19) QDP
27.34/7.90	        (20) MNOCProof [EQUIVALENT, 0 ms]
27.34/7.90	        (21) QDP
27.34/7.90	        (22) UsableRulesProof [EQUIVALENT, 0 ms]
27.34/7.90	        (23) QDP
27.34/7.90	        (24) QDPOrderProof [EQUIVALENT, 15 ms]
27.34/7.90	        (25) QDP
27.34/7.90	        (26) PisEmptyProof [EQUIVALENT, 0 ms]
27.34/7.90	        (27) YES
27.34/7.90	    (28) QDP
27.34/7.90	        (29) UsableRulesProof [EQUIVALENT, 0 ms]
27.34/7.90	        (30) QDP
27.34/7.90	        (31) MRRProof [EQUIVALENT, 42 ms]
27.34/7.90	        (32) QDP
27.34/7.90	        (33) MNOCProof [EQUIVALENT, 0 ms]
27.34/7.90	        (34) QDP
27.34/7.90	        (35) UsableRulesProof [EQUIVALENT, 0 ms]
27.34/7.90	        (36) QDP
27.34/7.90	        (37) QDPOrderProof [EQUIVALENT, 177 ms]
27.34/7.90	        (38) QDP
27.34/7.90	        (39) DependencyGraphProof [EQUIVALENT, 0 ms]
27.34/7.90	        (40) TRUE
27.34/7.90	
27.34/7.90	
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(0)
27.34/7.90	Obligation:
27.34/7.90	Q restricted rewrite system:
27.34/7.90	The TRS R consists of the following rules:
27.34/7.90	
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(p(s(x1))) -> p(x1)
27.34/7.90	   f(s(x1)) -> g(s(x1))
27.34/7.90	   g(x1) -> i(s(half(x1)))
27.34/7.90	   i(x1) -> f(p(x1))
27.34/7.90	   half(0(x1)) -> 0(s(s(half(x1))))
27.34/7.90	   half(s(s(x1))) -> s(half(p(p(s(s(x1))))))
27.34/7.90	   0(x1) -> x1
27.34/7.90	   rd(0(x1)) -> 0(0(0(0(0(0(rd(x1)))))))
27.34/7.90	
27.34/7.90	Q is empty.
27.34/7.90	
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(1) DependencyPairsProof (EQUIVALENT)
27.34/7.90	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(2)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	The TRS P consists of the following rules:
27.34/7.90	
27.34/7.90	   P(0(x1)) -> 0^1(s(s(p(x1))))
27.34/7.90	   P(0(x1)) -> P(x1)
27.34/7.90	   P(p(s(x1))) -> P(x1)
27.34/7.90	   F(s(x1)) -> G(s(x1))
27.34/7.90	   G(x1) -> I(s(half(x1)))
27.34/7.90	   G(x1) -> HALF(x1)
27.34/7.90	   I(x1) -> F(p(x1))
27.34/7.90	   I(x1) -> P(x1)
27.34/7.90	   HALF(0(x1)) -> 0^1(s(s(half(x1))))
27.34/7.90	   HALF(0(x1)) -> HALF(x1)
27.34/7.90	   HALF(s(s(x1))) -> HALF(p(p(s(s(x1)))))
27.34/7.90	   HALF(s(s(x1))) -> P(p(s(s(x1))))
27.34/7.90	   HALF(s(s(x1))) -> P(s(s(x1)))
27.34/7.90	   RD(0(x1)) -> 0^1(0(0(0(0(0(rd(x1)))))))
27.34/7.90	   RD(0(x1)) -> 0^1(0(0(0(0(rd(x1))))))
27.34/7.90	   RD(0(x1)) -> 0^1(0(0(0(rd(x1)))))
27.34/7.90	   RD(0(x1)) -> 0^1(0(0(rd(x1))))
27.34/7.90	   RD(0(x1)) -> 0^1(0(rd(x1)))
27.34/7.90	   RD(0(x1)) -> 0^1(rd(x1))
27.34/7.90	   RD(0(x1)) -> RD(x1)
27.34/7.90	
27.34/7.90	The TRS R consists of the following rules:
27.34/7.90	
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(p(s(x1))) -> p(x1)
27.34/7.90	   f(s(x1)) -> g(s(x1))
27.34/7.90	   g(x1) -> i(s(half(x1)))
27.34/7.90	   i(x1) -> f(p(x1))
27.34/7.90	   half(0(x1)) -> 0(s(s(half(x1))))
27.34/7.90	   half(s(s(x1))) -> s(half(p(p(s(s(x1))))))
27.34/7.90	   0(x1) -> x1
27.34/7.90	   rd(0(x1)) -> 0(0(0(0(0(0(rd(x1)))))))
27.34/7.90	
27.34/7.90	Q is empty.
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(3) DependencyGraphProof (EQUIVALENT)
27.34/7.90	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 12 less nodes.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(4)
27.34/7.90	Complex Obligation (AND)
27.34/7.90	
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(5)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	The TRS P consists of the following rules:
27.34/7.90	
27.34/7.90	   RD(0(x1)) -> RD(x1)
27.34/7.90	
27.34/7.90	The TRS R consists of the following rules:
27.34/7.90	
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(p(s(x1))) -> p(x1)
27.34/7.90	   f(s(x1)) -> g(s(x1))
27.34/7.90	   g(x1) -> i(s(half(x1)))
27.34/7.90	   i(x1) -> f(p(x1))
27.34/7.90	   half(0(x1)) -> 0(s(s(half(x1))))
27.34/7.90	   half(s(s(x1))) -> s(half(p(p(s(s(x1))))))
27.34/7.90	   0(x1) -> x1
27.34/7.90	   rd(0(x1)) -> 0(0(0(0(0(0(rd(x1)))))))
27.34/7.90	
27.34/7.90	Q is empty.
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(6) UsableRulesProof (EQUIVALENT)
27.34/7.90	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.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(7)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	The TRS P consists of the following rules:
27.34/7.90	
27.34/7.90	   RD(0(x1)) -> RD(x1)
27.34/7.90	
27.34/7.90	R is empty.
27.34/7.90	Q is empty.
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(8) QDPSizeChangeProof (EQUIVALENT)
27.34/7.90	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. 
27.34/7.90	
27.34/7.90	From the DPs we obtained the following set of size-change graphs:
27.34/7.90	*RD(0(x1)) -> RD(x1)
27.34/7.90	The graph contains the following edges 1 > 1
27.34/7.90	
27.34/7.90	
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(9)
27.34/7.90	YES
27.34/7.90	
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(10)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	The TRS P consists of the following rules:
27.34/7.90	
27.34/7.90	   P(p(s(x1))) -> P(x1)
27.34/7.90	   P(0(x1)) -> P(x1)
27.34/7.90	
27.34/7.90	The TRS R consists of the following rules:
27.34/7.90	
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(p(s(x1))) -> p(x1)
27.34/7.90	   f(s(x1)) -> g(s(x1))
27.34/7.90	   g(x1) -> i(s(half(x1)))
27.34/7.90	   i(x1) -> f(p(x1))
27.34/7.90	   half(0(x1)) -> 0(s(s(half(x1))))
27.34/7.90	   half(s(s(x1))) -> s(half(p(p(s(s(x1))))))
27.34/7.90	   0(x1) -> x1
27.34/7.90	   rd(0(x1)) -> 0(0(0(0(0(0(rd(x1)))))))
27.34/7.90	
27.34/7.90	Q is empty.
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(11) UsableRulesProof (EQUIVALENT)
27.34/7.90	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.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(12)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	The TRS P consists of the following rules:
27.34/7.90	
27.34/7.90	   P(p(s(x1))) -> P(x1)
27.34/7.90	   P(0(x1)) -> P(x1)
27.34/7.90	
27.34/7.90	R is empty.
27.34/7.90	Q is empty.
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(13) QDPSizeChangeProof (EQUIVALENT)
27.34/7.90	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. 
27.34/7.90	
27.34/7.90	From the DPs we obtained the following set of size-change graphs:
27.34/7.90	*P(p(s(x1))) -> P(x1)
27.34/7.90	The graph contains the following edges 1 > 1
27.34/7.90	
27.34/7.90	
27.34/7.90	*P(0(x1)) -> P(x1)
27.34/7.90	The graph contains the following edges 1 > 1
27.34/7.90	
27.34/7.90	
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(14)
27.34/7.90	YES
27.34/7.90	
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(15)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	The TRS P consists of the following rules:
27.34/7.90	
27.34/7.90	   HALF(s(s(x1))) -> HALF(p(p(s(s(x1)))))
27.34/7.90	   HALF(0(x1)) -> HALF(x1)
27.34/7.90	
27.34/7.90	The TRS R consists of the following rules:
27.34/7.90	
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(p(s(x1))) -> p(x1)
27.34/7.90	   f(s(x1)) -> g(s(x1))
27.34/7.90	   g(x1) -> i(s(half(x1)))
27.34/7.90	   i(x1) -> f(p(x1))
27.34/7.90	   half(0(x1)) -> 0(s(s(half(x1))))
27.34/7.90	   half(s(s(x1))) -> s(half(p(p(s(s(x1))))))
27.34/7.90	   0(x1) -> x1
27.34/7.90	   rd(0(x1)) -> 0(0(0(0(0(0(rd(x1)))))))
27.34/7.90	
27.34/7.90	Q is empty.
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(16) UsableRulesProof (EQUIVALENT)
27.34/7.90	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.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(17)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	The TRS P consists of the following rules:
27.34/7.90	
27.34/7.90	   HALF(s(s(x1))) -> HALF(p(p(s(s(x1)))))
27.34/7.90	   HALF(0(x1)) -> HALF(x1)
27.34/7.90	
27.34/7.90	The TRS R consists of the following rules:
27.34/7.90	
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	   p(p(s(x1))) -> p(x1)
27.34/7.90	   0(x1) -> x1
27.34/7.90	
27.34/7.90	Q is empty.
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(18) MRRProof (EQUIVALENT)
27.34/7.90	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.
27.34/7.90	
27.34/7.90	Strictly oriented dependency pairs:
27.34/7.90	
27.34/7.90	   HALF(0(x1)) -> HALF(x1)
27.34/7.90	
27.34/7.90	Strictly oriented rules of the TRS R:
27.34/7.90	
27.34/7.90	   0(x1) -> x1
27.34/7.90	
27.34/7.90	Used ordering: Polynomial interpretation [POLO]:
27.34/7.90	
27.34/7.90	   POL(0(x_1)) = 2 + 2*x_1
27.34/7.90	   POL(HALF(x_1)) = x_1
27.34/7.90	   POL(p(x_1)) = x_1
27.34/7.90	   POL(s(x_1)) = x_1
27.34/7.90	
27.34/7.90	
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(19)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	The TRS P consists of the following rules:
27.34/7.90	
27.34/7.90	   HALF(s(s(x1))) -> HALF(p(p(s(s(x1)))))
27.34/7.90	
27.34/7.90	The TRS R consists of the following rules:
27.34/7.90	
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	   p(p(s(x1))) -> p(x1)
27.34/7.90	
27.34/7.90	Q is empty.
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(20) MNOCProof (EQUIVALENT)
27.34/7.90	We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(21)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	The TRS P consists of the following rules:
27.34/7.90	
27.34/7.90	   HALF(s(s(x1))) -> HALF(p(p(s(s(x1)))))
27.34/7.90	
27.34/7.90	The TRS R consists of the following rules:
27.34/7.90	
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	   p(p(s(x1))) -> p(x1)
27.34/7.90	
27.34/7.90	The set Q consists of the following terms:
27.34/7.90	
27.34/7.90	   p(s(x0))
27.34/7.90	   p(0(x0))
27.34/7.90	
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(22) UsableRulesProof (EQUIVALENT)
27.34/7.90	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(23)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	The TRS P consists of the following rules:
27.34/7.90	
27.34/7.90	   HALF(s(s(x1))) -> HALF(p(p(s(s(x1)))))
27.34/7.90	
27.34/7.90	The TRS R consists of the following rules:
27.34/7.90	
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	
27.34/7.90	The set Q consists of the following terms:
27.34/7.90	
27.34/7.90	   p(s(x0))
27.34/7.90	   p(0(x0))
27.34/7.90	
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(24) QDPOrderProof (EQUIVALENT)
27.34/7.90	We use the reduction pair processor [LPAR04,JAR06].
27.34/7.90	
27.34/7.90	
27.34/7.90	The following pairs can be oriented strictly and are deleted.
27.34/7.90	
27.34/7.90	   HALF(s(s(x1))) -> HALF(p(p(s(s(x1)))))
27.34/7.90	The remaining pairs can at least be oriented weakly.
27.34/7.90	Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:
27.34/7.90	
27.34/7.90	POL( HALF_1(x_1) ) = 2x_1 + 2
27.34/7.90	POL( p_1(x_1) ) = max{0, x_1 - 2}
27.34/7.90	POL( s_1(x_1) ) = 2x_1 + 2
27.34/7.90	POL( 0_1(x_1) ) = max{0, -2}
27.34/7.90	
27.34/7.90	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
27.34/7.90	
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	
27.34/7.90	
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(25)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	P is empty.
27.34/7.90	The TRS R consists of the following rules:
27.34/7.90	
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	
27.34/7.90	The set Q consists of the following terms:
27.34/7.90	
27.34/7.90	   p(s(x0))
27.34/7.90	   p(0(x0))
27.34/7.90	
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(26) PisEmptyProof (EQUIVALENT)
27.34/7.90	The TRS P is empty. Hence, there is no (P,Q,R) chain.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(27)
27.34/7.90	YES
27.34/7.90	
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(28)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	The TRS P consists of the following rules:
27.34/7.90	
27.34/7.90	   I(x1) -> F(p(x1))
27.34/7.90	   F(s(x1)) -> G(s(x1))
27.34/7.90	   G(x1) -> I(s(half(x1)))
27.34/7.90	
27.34/7.90	The TRS R consists of the following rules:
27.34/7.90	
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(p(s(x1))) -> p(x1)
27.34/7.90	   f(s(x1)) -> g(s(x1))
27.34/7.90	   g(x1) -> i(s(half(x1)))
27.34/7.90	   i(x1) -> f(p(x1))
27.34/7.90	   half(0(x1)) -> 0(s(s(half(x1))))
27.34/7.90	   half(s(s(x1))) -> s(half(p(p(s(s(x1))))))
27.34/7.90	   0(x1) -> x1
27.34/7.90	   rd(0(x1)) -> 0(0(0(0(0(0(rd(x1)))))))
27.34/7.90	
27.34/7.90	Q is empty.
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(29) UsableRulesProof (EQUIVALENT)
27.34/7.90	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.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(30)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	The TRS P consists of the following rules:
27.34/7.90	
27.34/7.90	   I(x1) -> F(p(x1))
27.34/7.90	   F(s(x1)) -> G(s(x1))
27.34/7.90	   G(x1) -> I(s(half(x1)))
27.34/7.90	
27.34/7.90	The TRS R consists of the following rules:
27.34/7.90	
27.34/7.90	   half(0(x1)) -> 0(s(s(half(x1))))
27.34/7.90	   half(s(s(x1))) -> s(half(p(p(s(s(x1))))))
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	   p(p(s(x1))) -> p(x1)
27.34/7.90	   0(x1) -> x1
27.34/7.90	
27.34/7.90	Q is empty.
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(31) MRRProof (EQUIVALENT)
27.34/7.90	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.
27.34/7.90	
27.34/7.90	
27.34/7.90	Strictly oriented rules of the TRS R:
27.34/7.90	
27.34/7.90	   0(x1) -> x1
27.34/7.90	
27.34/7.90	Used ordering: Polynomial interpretation [POLO]:
27.34/7.90	
27.34/7.90	   POL(0(x_1)) = 2 + x_1
27.34/7.90	   POL(F(x_1)) = x_1
27.34/7.90	   POL(G(x_1)) = x_1
27.34/7.90	   POL(I(x_1)) = x_1
27.34/7.90	   POL(half(x_1)) = x_1
27.34/7.90	   POL(p(x_1)) = x_1
27.34/7.90	   POL(s(x_1)) = x_1
27.34/7.90	
27.34/7.90	
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(32)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	The TRS P consists of the following rules:
27.34/7.90	
27.34/7.90	   I(x1) -> F(p(x1))
27.34/7.90	   F(s(x1)) -> G(s(x1))
27.34/7.90	   G(x1) -> I(s(half(x1)))
27.34/7.90	
27.34/7.90	The TRS R consists of the following rules:
27.34/7.90	
27.34/7.90	   half(0(x1)) -> 0(s(s(half(x1))))
27.34/7.90	   half(s(s(x1))) -> s(half(p(p(s(s(x1))))))
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	   p(p(s(x1))) -> p(x1)
27.34/7.90	
27.34/7.90	Q is empty.
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(33) MNOCProof (EQUIVALENT)
27.34/7.90	We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(34)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	The TRS P consists of the following rules:
27.34/7.90	
27.34/7.90	   I(x1) -> F(p(x1))
27.34/7.90	   F(s(x1)) -> G(s(x1))
27.34/7.90	   G(x1) -> I(s(half(x1)))
27.34/7.90	
27.34/7.90	The TRS R consists of the following rules:
27.34/7.90	
27.34/7.90	   half(0(x1)) -> 0(s(s(half(x1))))
27.34/7.90	   half(s(s(x1))) -> s(half(p(p(s(s(x1))))))
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	   p(p(s(x1))) -> p(x1)
27.34/7.90	
27.34/7.90	The set Q consists of the following terms:
27.34/7.90	
27.34/7.90	   half(0(x0))
27.34/7.90	   half(s(s(x0)))
27.34/7.90	   p(s(x0))
27.34/7.90	   p(0(x0))
27.34/7.90	
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(35) UsableRulesProof (EQUIVALENT)
27.34/7.90	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(36)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	The TRS P consists of the following rules:
27.34/7.90	
27.34/7.90	   I(x1) -> F(p(x1))
27.34/7.90	   F(s(x1)) -> G(s(x1))
27.34/7.90	   G(x1) -> I(s(half(x1)))
27.34/7.90	
27.34/7.90	The TRS R consists of the following rules:
27.34/7.90	
27.34/7.90	   half(0(x1)) -> 0(s(s(half(x1))))
27.34/7.90	   half(s(s(x1))) -> s(half(p(p(s(s(x1))))))
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	
27.34/7.90	The set Q consists of the following terms:
27.34/7.90	
27.34/7.90	   half(0(x0))
27.34/7.90	   half(s(s(x0)))
27.34/7.90	   p(s(x0))
27.34/7.90	   p(0(x0))
27.34/7.90	
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(37) QDPOrderProof (EQUIVALENT)
27.34/7.90	We use the reduction pair processor [LPAR04,JAR06].
27.34/7.90	
27.34/7.90	
27.34/7.90	The following pairs can be oriented strictly and are deleted.
27.34/7.90	
27.34/7.90	   F(s(x1)) -> G(s(x1))
27.34/7.90	The remaining pairs can at least be oriented weakly.
27.34/7.90	Used ordering:  Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]:
27.34/7.90	
27.34/7.90	   <<<
27.34/7.90	 POL(I(x_1)) =  	[[0A]] 	 +  	[[-I, 0A, 0A]] 	* 	x_1
27.34/7.90	>>>
27.34/7.90	
27.34/7.90	   <<<
27.34/7.90	 POL(F(x_1)) =  	[[0A]] 	 +  	[[0A, 0A, 0A]] 	* 	x_1
27.34/7.90	>>>
27.34/7.90	
27.34/7.90	   <<<
27.34/7.90	 POL(p(x_1)) =  	[[0A], [-I], [0A]] 	 +  	[[-I, 0A, 0A], [-I, 0A, -I], [-I, 0A, -I]] 	* 	x_1
27.34/7.90	>>>
27.34/7.90	
27.34/7.90	   <<<
27.34/7.90	 POL(s(x_1)) =  	[[1A], [0A], [0A]] 	 +  	[[1A, 1A, 1A], [-I, 0A, 0A], [0A, 0A, 0A]] 	* 	x_1
27.34/7.90	>>>
27.34/7.90	
27.34/7.90	   <<<
27.34/7.90	 POL(G(x_1)) =  	[[0A]] 	 +  	[[-I, 0A, 0A]] 	* 	x_1
27.34/7.90	>>>
27.34/7.90	
27.34/7.90	   <<<
27.34/7.90	 POL(half(x_1)) =  	[[0A], [-I], [-I]] 	 +  	[[-I, 0A, 0A], [-I, 0A, 0A], [-I, 0A, 0A]] 	* 	x_1
27.34/7.90	>>>
27.34/7.90	
27.34/7.90	   <<<
27.34/7.90	 POL(0(x_1)) =  	[[0A], [0A], [-I]] 	 +  	[[-I, -I, -I], [-I, -I, -I], [-I, -I, -I]] 	* 	x_1
27.34/7.90	>>>
27.34/7.90	
27.34/7.90	
27.34/7.90	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
27.34/7.90	
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	   half(0(x1)) -> 0(s(s(half(x1))))
27.34/7.90	   half(s(s(x1))) -> s(half(p(p(s(s(x1))))))
27.34/7.90	
27.34/7.90	
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(38)
27.34/7.90	Obligation:
27.34/7.90	Q DP problem:
27.34/7.90	The TRS P consists of the following rules:
27.34/7.90	
27.34/7.90	   I(x1) -> F(p(x1))
27.34/7.90	   G(x1) -> I(s(half(x1)))
27.34/7.90	
27.34/7.90	The TRS R consists of the following rules:
27.34/7.90	
27.34/7.90	   half(0(x1)) -> 0(s(s(half(x1))))
27.34/7.90	   half(s(s(x1))) -> s(half(p(p(s(s(x1))))))
27.34/7.90	   p(s(x1)) -> x1
27.34/7.90	   p(0(x1)) -> 0(s(s(p(x1))))
27.34/7.90	
27.34/7.90	The set Q consists of the following terms:
27.34/7.90	
27.34/7.90	   half(0(x0))
27.34/7.90	   half(s(s(x0)))
27.34/7.90	   p(s(x0))
27.34/7.90	   p(0(x0))
27.34/7.90	
27.34/7.90	We have to consider all minimal (P,Q,R)-chains.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(39) DependencyGraphProof (EQUIVALENT)
27.34/7.90	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes.
27.34/7.90	----------------------------------------
27.34/7.90	
27.34/7.90	(40)
27.34/7.90	TRUE
27.43/7.97	EOF