4.88/2.00	YES
4.88/2.02	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
4.88/2.02	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.88/2.02	
4.88/2.02	
4.88/2.02	Termination w.r.t. Q of the given QTRS could be proven:
4.88/2.02	
4.88/2.02	(0) QTRS
4.88/2.02	(1) DependencyPairsProof [EQUIVALENT, 5 ms]
4.88/2.02	(2) QDP
4.88/2.02	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
4.88/2.02	(4) AND
4.88/2.02	    (5) QDP
4.88/2.02	        (6) UsableRulesProof [EQUIVALENT, 0 ms]
4.88/2.02	        (7) QDP
4.88/2.02	        (8) QReductionProof [EQUIVALENT, 0 ms]
4.88/2.02	        (9) QDP
4.88/2.02	        (10) QDPSizeChangeProof [EQUIVALENT, 0 ms]
4.88/2.02	        (11) YES
4.88/2.02	    (12) QDP
4.88/2.02	        (13) UsableRulesProof [EQUIVALENT, 0 ms]
4.88/2.02	        (14) QDP
4.88/2.02	        (15) QReductionProof [EQUIVALENT, 0 ms]
4.88/2.02	        (16) QDP
4.88/2.02	        (17) QDPSizeChangeProof [EQUIVALENT, 0 ms]
4.88/2.02	        (18) YES
4.88/2.02	    (19) QDP
4.88/2.02	        (20) UsableRulesProof [EQUIVALENT, 0 ms]
4.88/2.02	        (21) QDP
4.88/2.02	        (22) QReductionProof [EQUIVALENT, 0 ms]
4.88/2.02	        (23) QDP
4.88/2.02	        (24) QDPSizeChangeProof [EQUIVALENT, 0 ms]
4.88/2.02	        (25) YES
4.88/2.02	    (26) QDP
4.88/2.02	        (27) UsableRulesProof [EQUIVALENT, 0 ms]
4.88/2.02	        (28) QDP
4.88/2.02	        (29) QReductionProof [EQUIVALENT, 0 ms]
4.88/2.02	        (30) QDP
4.88/2.02	        (31) QDPOrderProof [EQUIVALENT, 1 ms]
4.88/2.02	        (32) QDP
4.88/2.02	        (33) QDPOrderProof [EQUIVALENT, 25 ms]
4.88/2.02	        (34) QDP
4.88/2.02	        (35) PisEmptyProof [EQUIVALENT, 0 ms]
4.88/2.02	        (36) YES
4.88/2.02	
4.88/2.02	
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(0)
4.88/2.02	Obligation:
4.88/2.02	Q restricted rewrite system:
4.88/2.02	The TRS R consists of the following rules:
4.88/2.02	
4.88/2.02	   even(0) -> true
4.88/2.02	   even(s(0)) -> false
4.88/2.02	   even(s(s(x))) -> even(x)
4.88/2.02	   half(0) -> 0
4.88/2.02	   half(s(s(x))) -> s(half(x))
4.88/2.02	   plus(0, y) -> y
4.88/2.02	   plus(s(x), y) -> s(plus(x, y))
4.88/2.02	   times(0, y) -> 0
4.88/2.02	   times(s(x), y) -> if_times(even(s(x)), s(x), y)
4.88/2.02	   if_times(true, s(x), y) -> plus(times(half(s(x)), y), times(half(s(x)), y))
4.88/2.02	   if_times(false, s(x), y) -> plus(y, times(x, y))
4.88/2.02	
4.88/2.02	The set Q consists of the following terms:
4.88/2.02	
4.88/2.02	   even(0)
4.88/2.02	   even(s(0))
4.88/2.02	   even(s(s(x0)))
4.88/2.02	   half(0)
4.88/2.02	   half(s(s(x0)))
4.88/2.02	   plus(0, x0)
4.88/2.02	   plus(s(x0), x1)
4.88/2.02	   times(0, x0)
4.88/2.02	   times(s(x0), x1)
4.88/2.02	   if_times(true, s(x0), x1)
4.88/2.02	   if_times(false, s(x0), x1)
4.88/2.02	
4.88/2.02	
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(1) DependencyPairsProof (EQUIVALENT)
4.88/2.02	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(2)
4.88/2.02	Obligation:
4.88/2.02	Q DP problem:
4.88/2.02	The TRS P consists of the following rules:
4.88/2.02	
4.88/2.02	   EVEN(s(s(x))) -> EVEN(x)
4.88/2.02	   HALF(s(s(x))) -> HALF(x)
4.88/2.02	   PLUS(s(x), y) -> PLUS(x, y)
4.88/2.02	   TIMES(s(x), y) -> IF_TIMES(even(s(x)), s(x), y)
4.88/2.02	   TIMES(s(x), y) -> EVEN(s(x))
4.88/2.02	   IF_TIMES(true, s(x), y) -> PLUS(times(half(s(x)), y), times(half(s(x)), y))
4.88/2.02	   IF_TIMES(true, s(x), y) -> TIMES(half(s(x)), y)
4.88/2.02	   IF_TIMES(true, s(x), y) -> HALF(s(x))
4.88/2.02	   IF_TIMES(false, s(x), y) -> PLUS(y, times(x, y))
4.88/2.02	   IF_TIMES(false, s(x), y) -> TIMES(x, y)
4.88/2.02	
4.88/2.02	The TRS R consists of the following rules:
4.88/2.02	
4.88/2.02	   even(0) -> true
4.88/2.02	   even(s(0)) -> false
4.88/2.02	   even(s(s(x))) -> even(x)
4.88/2.02	   half(0) -> 0
4.88/2.02	   half(s(s(x))) -> s(half(x))
4.88/2.02	   plus(0, y) -> y
4.88/2.02	   plus(s(x), y) -> s(plus(x, y))
4.88/2.02	   times(0, y) -> 0
4.88/2.02	   times(s(x), y) -> if_times(even(s(x)), s(x), y)
4.88/2.02	   if_times(true, s(x), y) -> plus(times(half(s(x)), y), times(half(s(x)), y))
4.88/2.02	   if_times(false, s(x), y) -> plus(y, times(x, y))
4.88/2.02	
4.88/2.02	The set Q consists of the following terms:
4.88/2.02	
4.88/2.02	   even(0)
4.88/2.02	   even(s(0))
4.88/2.02	   even(s(s(x0)))
4.88/2.02	   half(0)
4.88/2.02	   half(s(s(x0)))
4.88/2.02	   plus(0, x0)
4.88/2.02	   plus(s(x0), x1)
4.88/2.02	   times(0, x0)
4.88/2.02	   times(s(x0), x1)
4.88/2.02	   if_times(true, s(x0), x1)
4.88/2.02	   if_times(false, s(x0), x1)
4.88/2.02	
4.88/2.02	We have to consider all minimal (P,Q,R)-chains.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(3) DependencyGraphProof (EQUIVALENT)
4.88/2.02	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 4 less nodes.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(4)
4.88/2.02	Complex Obligation (AND)
4.88/2.02	
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(5)
4.88/2.02	Obligation:
4.88/2.02	Q DP problem:
4.88/2.02	The TRS P consists of the following rules:
4.88/2.02	
4.88/2.02	   PLUS(s(x), y) -> PLUS(x, y)
4.88/2.02	
4.88/2.02	The TRS R consists of the following rules:
4.88/2.02	
4.88/2.02	   even(0) -> true
4.88/2.02	   even(s(0)) -> false
4.88/2.02	   even(s(s(x))) -> even(x)
4.88/2.02	   half(0) -> 0
4.88/2.02	   half(s(s(x))) -> s(half(x))
4.88/2.02	   plus(0, y) -> y
4.88/2.02	   plus(s(x), y) -> s(plus(x, y))
4.88/2.02	   times(0, y) -> 0
4.88/2.02	   times(s(x), y) -> if_times(even(s(x)), s(x), y)
4.88/2.02	   if_times(true, s(x), y) -> plus(times(half(s(x)), y), times(half(s(x)), y))
4.88/2.02	   if_times(false, s(x), y) -> plus(y, times(x, y))
4.88/2.02	
4.88/2.02	The set Q consists of the following terms:
4.88/2.02	
4.88/2.02	   even(0)
4.88/2.02	   even(s(0))
4.88/2.02	   even(s(s(x0)))
4.88/2.02	   half(0)
4.88/2.02	   half(s(s(x0)))
4.88/2.02	   plus(0, x0)
4.88/2.02	   plus(s(x0), x1)
4.88/2.02	   times(0, x0)
4.88/2.02	   times(s(x0), x1)
4.88/2.02	   if_times(true, s(x0), x1)
4.88/2.02	   if_times(false, s(x0), x1)
4.88/2.02	
4.88/2.02	We have to consider all minimal (P,Q,R)-chains.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(6) UsableRulesProof (EQUIVALENT)
4.88/2.02	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.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(7)
4.88/2.02	Obligation:
4.88/2.02	Q DP problem:
4.88/2.02	The TRS P consists of the following rules:
4.88/2.02	
4.88/2.02	   PLUS(s(x), y) -> PLUS(x, y)
4.88/2.02	
4.88/2.02	R is empty.
4.88/2.02	The set Q consists of the following terms:
4.88/2.02	
4.88/2.02	   even(0)
4.88/2.02	   even(s(0))
4.88/2.02	   even(s(s(x0)))
4.88/2.02	   half(0)
4.88/2.02	   half(s(s(x0)))
4.88/2.02	   plus(0, x0)
4.88/2.02	   plus(s(x0), x1)
4.88/2.02	   times(0, x0)
4.88/2.02	   times(s(x0), x1)
4.88/2.02	   if_times(true, s(x0), x1)
4.88/2.02	   if_times(false, s(x0), x1)
4.88/2.02	
4.88/2.02	We have to consider all minimal (P,Q,R)-chains.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(8) QReductionProof (EQUIVALENT)
4.88/2.02	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
4.88/2.02	
4.88/2.02	   even(0)
4.88/2.02	   even(s(0))
4.88/2.02	   even(s(s(x0)))
4.88/2.02	   half(0)
4.88/2.02	   half(s(s(x0)))
4.88/2.02	   plus(0, x0)
4.88/2.02	   plus(s(x0), x1)
4.88/2.02	   times(0, x0)
4.88/2.02	   times(s(x0), x1)
4.88/2.02	   if_times(true, s(x0), x1)
4.88/2.02	   if_times(false, s(x0), x1)
4.88/2.02	
4.88/2.02	
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(9)
4.88/2.02	Obligation:
4.88/2.02	Q DP problem:
4.88/2.02	The TRS P consists of the following rules:
4.88/2.02	
4.88/2.02	   PLUS(s(x), y) -> PLUS(x, y)
4.88/2.02	
4.88/2.02	R is empty.
4.88/2.02	Q is empty.
4.88/2.02	We have to consider all minimal (P,Q,R)-chains.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(10) QDPSizeChangeProof (EQUIVALENT)
4.88/2.02	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. 
4.88/2.02	
4.88/2.02	From the DPs we obtained the following set of size-change graphs:
4.88/2.02	*PLUS(s(x), y) -> PLUS(x, y)
4.88/2.02	The graph contains the following edges 1 > 1, 2 >= 2
4.88/2.02	
4.88/2.02	
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(11)
4.88/2.02	YES
4.88/2.02	
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(12)
4.88/2.02	Obligation:
4.88/2.02	Q DP problem:
4.88/2.02	The TRS P consists of the following rules:
4.88/2.02	
4.88/2.02	   HALF(s(s(x))) -> HALF(x)
4.88/2.02	
4.88/2.02	The TRS R consists of the following rules:
4.88/2.02	
4.88/2.02	   even(0) -> true
4.88/2.02	   even(s(0)) -> false
4.88/2.02	   even(s(s(x))) -> even(x)
4.88/2.02	   half(0) -> 0
4.88/2.02	   half(s(s(x))) -> s(half(x))
4.88/2.02	   plus(0, y) -> y
4.88/2.02	   plus(s(x), y) -> s(plus(x, y))
4.88/2.02	   times(0, y) -> 0
4.88/2.02	   times(s(x), y) -> if_times(even(s(x)), s(x), y)
4.88/2.02	   if_times(true, s(x), y) -> plus(times(half(s(x)), y), times(half(s(x)), y))
4.88/2.02	   if_times(false, s(x), y) -> plus(y, times(x, y))
4.88/2.02	
4.88/2.02	The set Q consists of the following terms:
4.88/2.02	
4.88/2.02	   even(0)
4.88/2.02	   even(s(0))
4.88/2.02	   even(s(s(x0)))
4.88/2.02	   half(0)
4.88/2.02	   half(s(s(x0)))
4.88/2.02	   plus(0, x0)
4.88/2.02	   plus(s(x0), x1)
4.88/2.02	   times(0, x0)
4.88/2.02	   times(s(x0), x1)
4.88/2.02	   if_times(true, s(x0), x1)
4.88/2.02	   if_times(false, s(x0), x1)
4.88/2.02	
4.88/2.02	We have to consider all minimal (P,Q,R)-chains.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(13) UsableRulesProof (EQUIVALENT)
4.88/2.02	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.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(14)
4.88/2.02	Obligation:
4.88/2.02	Q DP problem:
4.88/2.02	The TRS P consists of the following rules:
4.88/2.02	
4.88/2.02	   HALF(s(s(x))) -> HALF(x)
4.88/2.02	
4.88/2.02	R is empty.
4.88/2.02	The set Q consists of the following terms:
4.88/2.02	
4.88/2.02	   even(0)
4.88/2.02	   even(s(0))
4.88/2.02	   even(s(s(x0)))
4.88/2.02	   half(0)
4.88/2.02	   half(s(s(x0)))
4.88/2.02	   plus(0, x0)
4.88/2.02	   plus(s(x0), x1)
4.88/2.02	   times(0, x0)
4.88/2.02	   times(s(x0), x1)
4.88/2.02	   if_times(true, s(x0), x1)
4.88/2.02	   if_times(false, s(x0), x1)
4.88/2.02	
4.88/2.02	We have to consider all minimal (P,Q,R)-chains.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(15) QReductionProof (EQUIVALENT)
4.88/2.02	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
4.88/2.02	
4.88/2.02	   even(0)
4.88/2.02	   even(s(0))
4.88/2.02	   even(s(s(x0)))
4.88/2.02	   half(0)
4.88/2.02	   half(s(s(x0)))
4.88/2.02	   plus(0, x0)
4.88/2.02	   plus(s(x0), x1)
4.88/2.02	   times(0, x0)
4.88/2.02	   times(s(x0), x1)
4.88/2.02	   if_times(true, s(x0), x1)
4.88/2.02	   if_times(false, s(x0), x1)
4.88/2.02	
4.88/2.02	
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(16)
4.88/2.02	Obligation:
4.88/2.02	Q DP problem:
4.88/2.02	The TRS P consists of the following rules:
4.88/2.02	
4.88/2.02	   HALF(s(s(x))) -> HALF(x)
4.88/2.02	
4.88/2.02	R is empty.
4.88/2.02	Q is empty.
4.88/2.02	We have to consider all minimal (P,Q,R)-chains.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(17) QDPSizeChangeProof (EQUIVALENT)
4.88/2.02	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. 
4.88/2.02	
4.88/2.02	From the DPs we obtained the following set of size-change graphs:
4.88/2.02	*HALF(s(s(x))) -> HALF(x)
4.88/2.02	The graph contains the following edges 1 > 1
4.88/2.02	
4.88/2.02	
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(18)
4.88/2.02	YES
4.88/2.02	
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(19)
4.88/2.02	Obligation:
4.88/2.02	Q DP problem:
4.88/2.02	The TRS P consists of the following rules:
4.88/2.02	
4.88/2.02	   EVEN(s(s(x))) -> EVEN(x)
4.88/2.02	
4.88/2.02	The TRS R consists of the following rules:
4.88/2.02	
4.88/2.02	   even(0) -> true
4.88/2.02	   even(s(0)) -> false
4.88/2.02	   even(s(s(x))) -> even(x)
4.88/2.02	   half(0) -> 0
4.88/2.02	   half(s(s(x))) -> s(half(x))
4.88/2.02	   plus(0, y) -> y
4.88/2.02	   plus(s(x), y) -> s(plus(x, y))
4.88/2.02	   times(0, y) -> 0
4.88/2.02	   times(s(x), y) -> if_times(even(s(x)), s(x), y)
4.88/2.02	   if_times(true, s(x), y) -> plus(times(half(s(x)), y), times(half(s(x)), y))
4.88/2.02	   if_times(false, s(x), y) -> plus(y, times(x, y))
4.88/2.02	
4.88/2.02	The set Q consists of the following terms:
4.88/2.02	
4.88/2.02	   even(0)
4.88/2.02	   even(s(0))
4.88/2.02	   even(s(s(x0)))
4.88/2.02	   half(0)
4.88/2.02	   half(s(s(x0)))
4.88/2.02	   plus(0, x0)
4.88/2.02	   plus(s(x0), x1)
4.88/2.02	   times(0, x0)
4.88/2.02	   times(s(x0), x1)
4.88/2.02	   if_times(true, s(x0), x1)
4.88/2.02	   if_times(false, s(x0), x1)
4.88/2.02	
4.88/2.02	We have to consider all minimal (P,Q,R)-chains.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(20) UsableRulesProof (EQUIVALENT)
4.88/2.02	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.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(21)
4.88/2.02	Obligation:
4.88/2.02	Q DP problem:
4.88/2.02	The TRS P consists of the following rules:
4.88/2.02	
4.88/2.02	   EVEN(s(s(x))) -> EVEN(x)
4.88/2.02	
4.88/2.02	R is empty.
4.88/2.02	The set Q consists of the following terms:
4.88/2.02	
4.88/2.02	   even(0)
4.88/2.02	   even(s(0))
4.88/2.02	   even(s(s(x0)))
4.88/2.02	   half(0)
4.88/2.02	   half(s(s(x0)))
4.88/2.02	   plus(0, x0)
4.88/2.02	   plus(s(x0), x1)
4.88/2.02	   times(0, x0)
4.88/2.02	   times(s(x0), x1)
4.88/2.02	   if_times(true, s(x0), x1)
4.88/2.02	   if_times(false, s(x0), x1)
4.88/2.02	
4.88/2.02	We have to consider all minimal (P,Q,R)-chains.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(22) QReductionProof (EQUIVALENT)
4.88/2.02	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
4.88/2.02	
4.88/2.02	   even(0)
4.88/2.02	   even(s(0))
4.88/2.02	   even(s(s(x0)))
4.88/2.02	   half(0)
4.88/2.02	   half(s(s(x0)))
4.88/2.02	   plus(0, x0)
4.88/2.02	   plus(s(x0), x1)
4.88/2.02	   times(0, x0)
4.88/2.02	   times(s(x0), x1)
4.88/2.02	   if_times(true, s(x0), x1)
4.88/2.02	   if_times(false, s(x0), x1)
4.88/2.02	
4.88/2.02	
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(23)
4.88/2.02	Obligation:
4.88/2.02	Q DP problem:
4.88/2.02	The TRS P consists of the following rules:
4.88/2.02	
4.88/2.02	   EVEN(s(s(x))) -> EVEN(x)
4.88/2.02	
4.88/2.02	R is empty.
4.88/2.02	Q is empty.
4.88/2.02	We have to consider all minimal (P,Q,R)-chains.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(24) QDPSizeChangeProof (EQUIVALENT)
4.88/2.02	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. 
4.88/2.02	
4.88/2.02	From the DPs we obtained the following set of size-change graphs:
4.88/2.02	*EVEN(s(s(x))) -> EVEN(x)
4.88/2.02	The graph contains the following edges 1 > 1
4.88/2.02	
4.88/2.02	
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(25)
4.88/2.02	YES
4.88/2.02	
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(26)
4.88/2.02	Obligation:
4.88/2.02	Q DP problem:
4.88/2.02	The TRS P consists of the following rules:
4.88/2.02	
4.88/2.02	   TIMES(s(x), y) -> IF_TIMES(even(s(x)), s(x), y)
4.88/2.02	   IF_TIMES(true, s(x), y) -> TIMES(half(s(x)), y)
4.88/2.02	   IF_TIMES(false, s(x), y) -> TIMES(x, y)
4.88/2.02	
4.88/2.02	The TRS R consists of the following rules:
4.88/2.02	
4.88/2.02	   even(0) -> true
4.88/2.02	   even(s(0)) -> false
4.88/2.02	   even(s(s(x))) -> even(x)
4.88/2.02	   half(0) -> 0
4.88/2.02	   half(s(s(x))) -> s(half(x))
4.88/2.02	   plus(0, y) -> y
4.88/2.02	   plus(s(x), y) -> s(plus(x, y))
4.88/2.02	   times(0, y) -> 0
4.88/2.02	   times(s(x), y) -> if_times(even(s(x)), s(x), y)
4.88/2.02	   if_times(true, s(x), y) -> plus(times(half(s(x)), y), times(half(s(x)), y))
4.88/2.02	   if_times(false, s(x), y) -> plus(y, times(x, y))
4.88/2.02	
4.88/2.02	The set Q consists of the following terms:
4.88/2.02	
4.88/2.02	   even(0)
4.88/2.02	   even(s(0))
4.88/2.02	   even(s(s(x0)))
4.88/2.02	   half(0)
4.88/2.02	   half(s(s(x0)))
4.88/2.02	   plus(0, x0)
4.88/2.02	   plus(s(x0), x1)
4.88/2.02	   times(0, x0)
4.88/2.02	   times(s(x0), x1)
4.88/2.02	   if_times(true, s(x0), x1)
4.88/2.02	   if_times(false, s(x0), x1)
4.88/2.02	
4.88/2.02	We have to consider all minimal (P,Q,R)-chains.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(27) UsableRulesProof (EQUIVALENT)
4.88/2.02	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.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(28)
4.88/2.02	Obligation:
4.88/2.02	Q DP problem:
4.88/2.02	The TRS P consists of the following rules:
4.88/2.02	
4.88/2.02	   TIMES(s(x), y) -> IF_TIMES(even(s(x)), s(x), y)
4.88/2.02	   IF_TIMES(true, s(x), y) -> TIMES(half(s(x)), y)
4.88/2.02	   IF_TIMES(false, s(x), y) -> TIMES(x, y)
4.88/2.02	
4.88/2.02	The TRS R consists of the following rules:
4.88/2.02	
4.88/2.02	   half(s(s(x))) -> s(half(x))
4.88/2.02	   half(0) -> 0
4.88/2.02	   even(s(0)) -> false
4.88/2.02	   even(s(s(x))) -> even(x)
4.88/2.02	   even(0) -> true
4.88/2.02	
4.88/2.02	The set Q consists of the following terms:
4.88/2.02	
4.88/2.02	   even(0)
4.88/2.02	   even(s(0))
4.88/2.02	   even(s(s(x0)))
4.88/2.02	   half(0)
4.88/2.02	   half(s(s(x0)))
4.88/2.02	   plus(0, x0)
4.88/2.02	   plus(s(x0), x1)
4.88/2.02	   times(0, x0)
4.88/2.02	   times(s(x0), x1)
4.88/2.02	   if_times(true, s(x0), x1)
4.88/2.02	   if_times(false, s(x0), x1)
4.88/2.02	
4.88/2.02	We have to consider all minimal (P,Q,R)-chains.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(29) QReductionProof (EQUIVALENT)
4.88/2.02	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
4.88/2.02	
4.88/2.02	   plus(0, x0)
4.88/2.02	   plus(s(x0), x1)
4.88/2.02	   times(0, x0)
4.88/2.02	   times(s(x0), x1)
4.88/2.02	   if_times(true, s(x0), x1)
4.88/2.02	   if_times(false, s(x0), x1)
4.88/2.02	
4.88/2.02	
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(30)
4.88/2.02	Obligation:
4.88/2.02	Q DP problem:
4.88/2.02	The TRS P consists of the following rules:
4.88/2.02	
4.88/2.02	   TIMES(s(x), y) -> IF_TIMES(even(s(x)), s(x), y)
4.88/2.02	   IF_TIMES(true, s(x), y) -> TIMES(half(s(x)), y)
4.88/2.02	   IF_TIMES(false, s(x), y) -> TIMES(x, y)
4.88/2.02	
4.88/2.02	The TRS R consists of the following rules:
4.88/2.02	
4.88/2.02	   half(s(s(x))) -> s(half(x))
4.88/2.02	   half(0) -> 0
4.88/2.02	   even(s(0)) -> false
4.88/2.02	   even(s(s(x))) -> even(x)
4.88/2.02	   even(0) -> true
4.88/2.02	
4.88/2.02	The set Q consists of the following terms:
4.88/2.02	
4.88/2.02	   even(0)
4.88/2.02	   even(s(0))
4.88/2.02	   even(s(s(x0)))
4.88/2.02	   half(0)
4.88/2.02	   half(s(s(x0)))
4.88/2.02	
4.88/2.02	We have to consider all minimal (P,Q,R)-chains.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(31) QDPOrderProof (EQUIVALENT)
4.88/2.02	We use the reduction pair processor [LPAR04,JAR06].
4.88/2.02	
4.88/2.02	
4.88/2.02	The following pairs can be oriented strictly and are deleted.
4.88/2.02	
4.88/2.02	   IF_TIMES(false, s(x), y) -> TIMES(x, y)
4.88/2.02	The remaining pairs can at least be oriented weakly.
4.88/2.02	Used ordering:  Combined order from the following AFS and order.
4.88/2.02	TIMES(x1, x2)  =  x1
4.88/2.02	
4.88/2.02	s(x1)  =  s(x1)
4.88/2.02	
4.88/2.02	IF_TIMES(x1, x2, x3)  =  x2
4.88/2.02	
4.88/2.02	half(x1)  =  x1
4.88/2.02	
4.88/2.02	0  =  0
4.88/2.02	
4.88/2.02	
4.88/2.02	Knuth-Bendix order [KBO] with precedence:trivial
4.88/2.02	
4.88/2.02	and weight map:
4.88/2.02	
4.88/2.02	   s_1=1
4.88/2.02	   0=1
4.88/2.02	
4.88/2.02	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
4.88/2.02	
4.88/2.02	   half(s(s(x))) -> s(half(x))
4.88/2.02	   half(0) -> 0
4.88/2.02	
4.88/2.02	
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(32)
4.88/2.02	Obligation:
4.88/2.02	Q DP problem:
4.88/2.02	The TRS P consists of the following rules:
4.88/2.02	
4.88/2.02	   TIMES(s(x), y) -> IF_TIMES(even(s(x)), s(x), y)
4.88/2.02	   IF_TIMES(true, s(x), y) -> TIMES(half(s(x)), y)
4.88/2.02	
4.88/2.02	The TRS R consists of the following rules:
4.88/2.02	
4.88/2.02	   half(s(s(x))) -> s(half(x))
4.88/2.02	   half(0) -> 0
4.88/2.02	   even(s(0)) -> false
4.88/2.02	   even(s(s(x))) -> even(x)
4.88/2.02	   even(0) -> true
4.88/2.02	
4.88/2.02	The set Q consists of the following terms:
4.88/2.02	
4.88/2.02	   even(0)
4.88/2.02	   even(s(0))
4.88/2.02	   even(s(s(x0)))
4.88/2.02	   half(0)
4.88/2.02	   half(s(s(x0)))
4.88/2.02	
4.88/2.02	We have to consider all minimal (P,Q,R)-chains.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(33) QDPOrderProof (EQUIVALENT)
4.88/2.02	We use the reduction pair processor [LPAR04,JAR06].
4.88/2.02	
4.88/2.02	
4.88/2.02	The following pairs can be oriented strictly and are deleted.
4.88/2.02	
4.88/2.02	   TIMES(s(x), y) -> IF_TIMES(even(s(x)), s(x), y)
4.88/2.02	   IF_TIMES(true, s(x), y) -> TIMES(half(s(x)), y)
4.88/2.02	The remaining pairs can at least be oriented weakly.
4.88/2.02	Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:
4.88/2.02	
4.88/2.02	POL( IF_TIMES_3(x_1, ..., x_3) ) = max{0, x_1 + 2x_2 + 2x_3 - 1}
4.88/2.02	POL( even_1(x_1) ) = 1
4.88/2.02	POL( s_1(x_1) ) = 2x_1 + 2
4.88/2.02	POL( 0 ) = 0
4.88/2.02	POL( false ) = 1
4.88/2.02	POL( TIMES_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2
4.88/2.02	POL( half_1(x_1) ) = max{0, x_1 - 2}
4.88/2.02	POL( true ) = 0
4.88/2.02	
4.88/2.02	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
4.88/2.02	
4.88/2.02	   even(s(0)) -> false
4.88/2.02	   even(s(s(x))) -> even(x)
4.88/2.02	   half(s(s(x))) -> s(half(x))
4.88/2.02	   half(0) -> 0
4.88/2.02	   even(0) -> true
4.88/2.02	
4.88/2.02	
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(34)
4.88/2.02	Obligation:
4.88/2.02	Q DP problem:
4.88/2.02	P is empty.
4.88/2.02	The TRS R consists of the following rules:
4.88/2.02	
4.88/2.02	   half(s(s(x))) -> s(half(x))
4.88/2.02	   half(0) -> 0
4.88/2.02	   even(s(0)) -> false
4.88/2.02	   even(s(s(x))) -> even(x)
4.88/2.02	   even(0) -> true
4.88/2.02	
4.88/2.02	The set Q consists of the following terms:
4.88/2.02	
4.88/2.02	   even(0)
4.88/2.02	   even(s(0))
4.88/2.02	   even(s(s(x0)))
4.88/2.02	   half(0)
4.88/2.02	   half(s(s(x0)))
4.88/2.02	
4.88/2.02	We have to consider all minimal (P,Q,R)-chains.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(35) PisEmptyProof (EQUIVALENT)
4.88/2.02	The TRS P is empty. Hence, there is no (P,Q,R) chain.
4.88/2.02	----------------------------------------
4.88/2.02	
4.88/2.02	(36)
4.88/2.02	YES
4.88/2.05	EOF