0.41/0.99 YES 0.41/0.99 0.41/0.99 Problem 1: 0.41/0.99 0.41/0.99 (VAR v_NonEmpty:S x:S y:S) 0.41/0.99 (RULES 0.41/0.99 even(0) -> ttrue 0.41/0.99 even(s(0)) -> ffalse 0.41/0.99 even(s(s(x:S))) -> even(x:S) 0.41/0.99 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.41/0.99 gt(s(x:S),zero) -> ttrue 0.41/0.99 gt(zero,y:S) -> ffalse 0.41/0.99 half(0) -> 0 0.41/0.99 half(s(s(x:S))) -> s(half(x:S)) 0.41/0.99 id(x:S) -> x:S 0.41/0.99 if(ffalse,x:S,y:S) -> y:S 0.41/0.99 if(ttrue,x:S,y:S) -> x:S 0.41/0.99 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.41/0.99 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.41/0.99 not(x:S) -> if(x:S,ffalse,ttrue) 0.41/0.99 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.41/0.99 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.41/0.99 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.41/0.99 plus(zero,y:S) -> y:S 0.41/0.99 times(0,y:S) -> 0 0.41/0.99 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.41/0.99 ) 0.41/0.99 (STRATEGY INNERMOST) 0.41/0.99 0.41/0.99 Problem 1: 0.41/0.99 0.41/0.99 Dependency Pairs Processor: 0.41/0.99 -> Pairs: 0.41/0.99 EVEN(s(s(x:S))) -> EVEN(x:S) 0.41/0.99 GT(s(x:S),s(y:S)) -> GT(x:S,y:S) 0.41/0.99 HALF(s(s(x:S))) -> HALF(x:S) 0.41/0.99 IF_TIMES(ffalse,s(x:S),y:S) -> PLUS(y:S,times(x:S,y:S)) 0.41/0.99 IF_TIMES(ffalse,s(x:S),y:S) -> TIMES(x:S,y:S) 0.41/0.99 IF_TIMES(ttrue,s(x:S),y:S) -> HALF(s(x:S)) 0.41/0.99 IF_TIMES(ttrue,s(x:S),y:S) -> PLUS(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.41/0.99 IF_TIMES(ttrue,s(x:S),y:S) -> TIMES(half(s(x:S)),y:S) 0.41/0.99 NOT(x:S) -> IF(x:S,ffalse,ttrue) 0.41/0.99 PLUS(s(x:S),s(y:S)) -> GT(x:S,y:S) 0.41/0.99 PLUS(s(x:S),s(y:S)) -> ID(x:S) 0.41/0.99 PLUS(s(x:S),s(y:S)) -> ID(y:S) 0.41/0.99 PLUS(s(x:S),s(y:S)) -> IF(gt(x:S,y:S),x:S,y:S) 0.41/0.99 PLUS(s(x:S),s(y:S)) -> IF(not(gt(x:S,y:S)),id(x:S),id(y:S)) 0.41/0.99 PLUS(s(x:S),s(y:S)) -> NOT(gt(x:S,y:S)) 0.41/0.99 PLUS(s(x:S),s(y:S)) -> PLUS(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))) 0.41/0.99 PLUS(s(x:S),x:S) -> GT(x:S,x:S) 0.41/0.99 PLUS(s(x:S),x:S) -> ID(x:S) 0.41/0.99 PLUS(s(x:S),x:S) -> IF(gt(x:S,x:S),id(x:S),id(x:S)) 0.41/0.99 PLUS(s(x:S),x:S) -> PLUS(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.41/0.99 TIMES(s(x:S),y:S) -> EVEN(s(x:S)) 0.41/0.99 TIMES(s(x:S),y:S) -> IF_TIMES(even(s(x:S)),s(x:S),y:S) 0.41/0.99 -> Rules: 0.41/0.99 even(0) -> ttrue 0.41/0.99 even(s(0)) -> ffalse 0.41/0.99 even(s(s(x:S))) -> even(x:S) 0.41/0.99 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.41/0.99 gt(s(x:S),zero) -> ttrue 0.41/0.99 gt(zero,y:S) -> ffalse 0.41/0.99 half(0) -> 0 0.41/0.99 half(s(s(x:S))) -> s(half(x:S)) 0.41/0.99 id(x:S) -> x:S 0.41/0.99 if(ffalse,x:S,y:S) -> y:S 0.41/0.99 if(ttrue,x:S,y:S) -> x:S 0.41/0.99 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.41/0.99 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.41/0.99 not(x:S) -> if(x:S,ffalse,ttrue) 0.41/0.99 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.41/0.99 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.41/0.99 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.41/0.99 plus(zero,y:S) -> y:S 0.41/0.99 times(0,y:S) -> 0 0.41/0.99 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.41/0.99 0.41/0.99 Problem 1: 0.41/0.99 0.41/0.99 SCC Processor: 0.41/0.99 -> Pairs: 0.41/0.99 EVEN(s(s(x:S))) -> EVEN(x:S) 0.41/0.99 GT(s(x:S),s(y:S)) -> GT(x:S,y:S) 0.41/0.99 HALF(s(s(x:S))) -> HALF(x:S) 0.41/0.99 IF_TIMES(ffalse,s(x:S),y:S) -> PLUS(y:S,times(x:S,y:S)) 0.41/0.99 IF_TIMES(ffalse,s(x:S),y:S) -> TIMES(x:S,y:S) 0.41/0.99 IF_TIMES(ttrue,s(x:S),y:S) -> HALF(s(x:S)) 0.41/0.99 IF_TIMES(ttrue,s(x:S),y:S) -> PLUS(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.41/0.99 IF_TIMES(ttrue,s(x:S),y:S) -> TIMES(half(s(x:S)),y:S) 0.41/0.99 NOT(x:S) -> IF(x:S,ffalse,ttrue) 0.41/0.99 PLUS(s(x:S),s(y:S)) -> GT(x:S,y:S) 0.41/0.99 PLUS(s(x:S),s(y:S)) -> ID(x:S) 0.41/0.99 PLUS(s(x:S),s(y:S)) -> ID(y:S) 0.41/0.99 PLUS(s(x:S),s(y:S)) -> IF(gt(x:S,y:S),x:S,y:S) 0.41/0.99 PLUS(s(x:S),s(y:S)) -> IF(not(gt(x:S,y:S)),id(x:S),id(y:S)) 0.41/0.99 PLUS(s(x:S),s(y:S)) -> NOT(gt(x:S,y:S)) 0.41/0.99 PLUS(s(x:S),s(y:S)) -> PLUS(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))) 0.41/0.99 PLUS(s(x:S),x:S) -> GT(x:S,x:S) 0.41/0.99 PLUS(s(x:S),x:S) -> ID(x:S) 0.41/0.99 PLUS(s(x:S),x:S) -> IF(gt(x:S,x:S),id(x:S),id(x:S)) 0.41/0.99 PLUS(s(x:S),x:S) -> PLUS(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.41/0.99 TIMES(s(x:S),y:S) -> EVEN(s(x:S)) 0.41/0.99 TIMES(s(x:S),y:S) -> IF_TIMES(even(s(x:S)),s(x:S),y:S) 0.41/0.99 -> Rules: 0.41/0.99 even(0) -> ttrue 0.41/0.99 even(s(0)) -> ffalse 0.41/0.99 even(s(s(x:S))) -> even(x:S) 0.41/0.99 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.41/0.99 gt(s(x:S),zero) -> ttrue 0.41/0.99 gt(zero,y:S) -> ffalse 0.41/0.99 half(0) -> 0 0.41/0.99 half(s(s(x:S))) -> s(half(x:S)) 0.41/0.99 id(x:S) -> x:S 0.41/0.99 if(ffalse,x:S,y:S) -> y:S 0.41/0.99 if(ttrue,x:S,y:S) -> x:S 0.41/0.99 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.41/0.99 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.41/0.99 not(x:S) -> if(x:S,ffalse,ttrue) 0.41/0.99 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.41/0.99 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.41/0.99 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.41/0.99 plus(zero,y:S) -> y:S 0.41/0.99 times(0,y:S) -> 0 0.41/0.99 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.41/0.99 ->Strongly Connected Components: 0.41/0.99 ->->Cycle: 0.41/0.99 ->->-> Pairs: 0.41/0.99 HALF(s(s(x:S))) -> HALF(x:S) 0.41/0.99 ->->-> Rules: 0.41/0.99 even(0) -> ttrue 0.41/0.99 even(s(0)) -> ffalse 0.41/0.99 even(s(s(x:S))) -> even(x:S) 0.41/0.99 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.41/0.99 gt(s(x:S),zero) -> ttrue 0.41/0.99 gt(zero,y:S) -> ffalse 0.41/0.99 half(0) -> 0 0.41/0.99 half(s(s(x:S))) -> s(half(x:S)) 0.41/0.99 id(x:S) -> x:S 0.41/0.99 if(ffalse,x:S,y:S) -> y:S 0.41/0.99 if(ttrue,x:S,y:S) -> x:S 0.41/0.99 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.41/0.99 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.41/0.99 not(x:S) -> if(x:S,ffalse,ttrue) 0.41/0.99 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.41/0.99 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.41/0.99 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.41/0.99 plus(zero,y:S) -> y:S 0.41/0.99 times(0,y:S) -> 0 0.41/0.99 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.41/0.99 ->->Cycle: 0.41/0.99 ->->-> Pairs: 0.41/0.99 GT(s(x:S),s(y:S)) -> GT(x:S,y:S) 0.41/0.99 ->->-> Rules: 0.41/0.99 even(0) -> ttrue 0.41/0.99 even(s(0)) -> ffalse 0.41/0.99 even(s(s(x:S))) -> even(x:S) 0.41/0.99 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.41/0.99 gt(s(x:S),zero) -> ttrue 0.41/0.99 gt(zero,y:S) -> ffalse 0.41/0.99 half(0) -> 0 0.41/0.99 half(s(s(x:S))) -> s(half(x:S)) 0.41/0.99 id(x:S) -> x:S 0.41/0.99 if(ffalse,x:S,y:S) -> y:S 0.41/0.99 if(ttrue,x:S,y:S) -> x:S 0.41/0.99 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.41/0.99 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.41/0.99 not(x:S) -> if(x:S,ffalse,ttrue) 0.41/0.99 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.41/0.99 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.41/0.99 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.41/0.99 plus(zero,y:S) -> y:S 0.41/0.99 times(0,y:S) -> 0 0.41/0.99 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.41/0.99 ->->Cycle: 0.41/0.99 ->->-> Pairs: 0.41/0.99 PLUS(s(x:S),s(y:S)) -> PLUS(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))) 0.41/0.99 PLUS(s(x:S),x:S) -> PLUS(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.41/0.99 ->->-> Rules: 0.41/0.99 even(0) -> ttrue 0.41/0.99 even(s(0)) -> ffalse 0.41/0.99 even(s(s(x:S))) -> even(x:S) 0.41/0.99 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.41/0.99 gt(s(x:S),zero) -> ttrue 0.41/0.99 gt(zero,y:S) -> ffalse 0.41/0.99 half(0) -> 0 0.41/0.99 half(s(s(x:S))) -> s(half(x:S)) 0.41/0.99 id(x:S) -> x:S 0.41/0.99 if(ffalse,x:S,y:S) -> y:S 0.41/0.99 if(ttrue,x:S,y:S) -> x:S 0.41/0.99 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.41/0.99 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.41/0.99 not(x:S) -> if(x:S,ffalse,ttrue) 0.41/0.99 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.41/0.99 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.41/0.99 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.41/0.99 plus(zero,y:S) -> y:S 0.41/0.99 times(0,y:S) -> 0 0.41/0.99 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.41/0.99 ->->Cycle: 0.41/0.99 ->->-> Pairs: 0.41/0.99 EVEN(s(s(x:S))) -> EVEN(x:S) 0.41/0.99 ->->-> Rules: 0.41/0.99 even(0) -> ttrue 0.41/0.99 even(s(0)) -> ffalse 0.41/0.99 even(s(s(x:S))) -> even(x:S) 0.41/0.99 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.41/0.99 gt(s(x:S),zero) -> ttrue 0.41/0.99 gt(zero,y:S) -> ffalse 0.41/0.99 half(0) -> 0 0.41/0.99 half(s(s(x:S))) -> s(half(x:S)) 0.41/0.99 id(x:S) -> x:S 0.41/0.99 if(ffalse,x:S,y:S) -> y:S 0.41/0.99 if(ttrue,x:S,y:S) -> x:S 0.41/0.99 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.41/0.99 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.41/0.99 not(x:S) -> if(x:S,ffalse,ttrue) 0.41/0.99 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.41/0.99 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.41/0.99 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.41/0.99 plus(zero,y:S) -> y:S 0.41/0.99 times(0,y:S) -> 0 0.41/0.99 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.41/0.99 ->->Cycle: 0.46/1.00 ->->-> Pairs: 0.46/1.00 IF_TIMES(ffalse,s(x:S),y:S) -> TIMES(x:S,y:S) 0.46/1.00 IF_TIMES(ttrue,s(x:S),y:S) -> TIMES(half(s(x:S)),y:S) 0.46/1.00 TIMES(s(x:S),y:S) -> IF_TIMES(even(s(x:S)),s(x:S),y:S) 0.46/1.00 ->->-> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 0.46/1.00 0.46/1.00 The problem is decomposed in 5 subproblems. 0.46/1.00 0.46/1.00 Problem 1.1: 0.46/1.00 0.46/1.00 Subterm Processor: 0.46/1.00 -> Pairs: 0.46/1.00 HALF(s(s(x:S))) -> HALF(x:S) 0.46/1.00 -> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 ->Projection: 0.46/1.00 pi(HALF) = 1 0.46/1.00 0.46/1.00 Problem 1.1: 0.46/1.00 0.46/1.00 SCC Processor: 0.46/1.00 -> Pairs: 0.46/1.00 Empty 0.46/1.00 -> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 ->Strongly Connected Components: 0.46/1.00 There is no strongly connected component 0.46/1.00 0.46/1.00 The problem is finite. 0.46/1.00 0.46/1.00 Problem 1.2: 0.46/1.00 0.46/1.00 Subterm Processor: 0.46/1.00 -> Pairs: 0.46/1.00 GT(s(x:S),s(y:S)) -> GT(x:S,y:S) 0.46/1.00 -> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 ->Projection: 0.46/1.00 pi(GT) = 1 0.46/1.00 0.46/1.00 Problem 1.2: 0.46/1.00 0.46/1.00 SCC Processor: 0.46/1.00 -> Pairs: 0.46/1.00 Empty 0.46/1.00 -> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 ->Strongly Connected Components: 0.46/1.00 There is no strongly connected component 0.46/1.00 0.46/1.00 The problem is finite. 0.46/1.00 0.46/1.00 Problem 1.3: 0.46/1.00 0.46/1.00 Reduction Pairs Processor: 0.46/1.00 -> Pairs: 0.46/1.00 PLUS(s(x:S),s(y:S)) -> PLUS(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))) 0.46/1.00 PLUS(s(x:S),x:S) -> PLUS(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 -> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 -> Usable rules: 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 ->Interpretation type: 0.46/1.00 Linear 0.46/1.00 ->Coefficients: 0.46/1.00 All rationals 0.46/1.00 ->Dimension: 0.46/1.00 1 0.46/1.00 ->Bound: 0.46/1.00 4 0.46/1.00 ->Interpretation: 0.46/1.00 0.46/1.00 [even](X) = 0 0.46/1.00 [gt](X1,X2) = 3.X1 + 1 0.46/1.00 [half](X) = 0 0.46/1.00 [id](X) = X 0.46/1.00 [if](X1,X2,X3) = X2 + X3 0.46/1.00 [if_times](X1,X2,X3) = 0 0.46/1.00 [not](X) = 3.X + 4 0.46/1.00 [plus](X1,X2) = 0 0.46/1.00 [times](X1,X2) = 0 0.46/1.00 [0] = 0 0.46/1.00 [fSNonEmpty] = 0 0.46/1.00 [false] = 3 0.46/1.00 [s](X) = 4.X + 3/2 0.46/1.00 [true] = 0 0.46/1.00 [zero] = 3/4 0.46/1.00 [EVEN](X) = 0 0.46/1.00 [GT](X1,X2) = 0 0.46/1.00 [HALF](X) = 0 0.46/1.00 [ID](X) = 0 0.46/1.00 [IF](X1,X2,X3) = 0 0.46/1.00 [IF_TIMES](X1,X2,X3) = 0 0.46/1.00 [NOT](X) = 0 0.46/1.00 [PLUS](X1,X2) = 4.X1 + 2.X2 0.46/1.00 [TIMES](X1,X2) = 0 0.46/1.00 0.46/1.00 Problem 1.3: 0.46/1.00 0.46/1.00 SCC Processor: 0.46/1.00 -> Pairs: 0.46/1.00 PLUS(s(x:S),x:S) -> PLUS(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 -> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 ->Strongly Connected Components: 0.46/1.00 ->->Cycle: 0.46/1.00 ->->-> Pairs: 0.46/1.00 PLUS(s(x:S),x:S) -> PLUS(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 ->->-> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 0.46/1.00 Problem 1.3: 0.46/1.00 0.46/1.00 Reduction Pairs Processor: 0.46/1.00 -> Pairs: 0.46/1.00 PLUS(s(x:S),x:S) -> PLUS(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 -> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 -> Usable rules: 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 ->Interpretation type: 0.46/1.00 Linear 0.46/1.00 ->Coefficients: 0.46/1.00 Natural Numbers 0.46/1.00 ->Dimension: 0.46/1.00 1 0.46/1.00 ->Bound: 0.46/1.00 2 0.46/1.00 ->Interpretation: 0.46/1.00 0.46/1.00 [even](X) = 0 0.46/1.00 [gt](X1,X2) = 2.X1 + 2 0.46/1.00 [half](X) = 0 0.46/1.00 [id](X) = X 0.46/1.00 [if](X1,X2,X3) = X2 + X3 0.46/1.00 [if_times](X1,X2,X3) = 0 0.46/1.00 [not](X) = 0 0.46/1.00 [plus](X1,X2) = 0 0.46/1.00 [times](X1,X2) = 0 0.46/1.00 [0] = 0 0.46/1.00 [fSNonEmpty] = 0 0.46/1.00 [false] = 2 0.46/1.00 [s](X) = 2.X + 1 0.46/1.00 [true] = 1 0.46/1.00 [zero] = 2 0.46/1.00 [EVEN](X) = 0 0.46/1.00 [GT](X1,X2) = 0 0.46/1.00 [HALF](X) = 0 0.46/1.00 [ID](X) = 0 0.46/1.00 [IF](X1,X2,X3) = 0 0.46/1.00 [IF_TIMES](X1,X2,X3) = 0 0.46/1.00 [NOT](X) = 0 0.46/1.00 [PLUS](X1,X2) = 2.X1 0.46/1.00 [TIMES](X1,X2) = 0 0.46/1.00 0.46/1.00 Problem 1.3: 0.46/1.00 0.46/1.00 SCC Processor: 0.46/1.00 -> Pairs: 0.46/1.00 Empty 0.46/1.00 -> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 ->Strongly Connected Components: 0.46/1.00 There is no strongly connected component 0.46/1.00 0.46/1.00 The problem is finite. 0.46/1.00 0.46/1.00 Problem 1.4: 0.46/1.00 0.46/1.00 Subterm Processor: 0.46/1.00 -> Pairs: 0.46/1.00 EVEN(s(s(x:S))) -> EVEN(x:S) 0.46/1.00 -> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 ->Projection: 0.46/1.00 pi(EVEN) = 1 0.46/1.00 0.46/1.00 Problem 1.4: 0.46/1.00 0.46/1.00 SCC Processor: 0.46/1.00 -> Pairs: 0.46/1.00 Empty 0.46/1.00 -> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 ->Strongly Connected Components: 0.46/1.00 There is no strongly connected component 0.46/1.00 0.46/1.00 The problem is finite. 0.46/1.00 0.46/1.00 Problem 1.5: 0.46/1.00 0.46/1.00 Reduction Pairs Processor: 0.46/1.00 -> Pairs: 0.46/1.00 IF_TIMES(ffalse,s(x:S),y:S) -> TIMES(x:S,y:S) 0.46/1.00 IF_TIMES(ttrue,s(x:S),y:S) -> TIMES(half(s(x:S)),y:S) 0.46/1.00 TIMES(s(x:S),y:S) -> IF_TIMES(even(s(x:S)),s(x:S),y:S) 0.46/1.00 -> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 -> Usable rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 ->Interpretation type: 0.46/1.00 Linear 0.46/1.00 ->Coefficients: 0.46/1.00 Natural Numbers 0.46/1.00 ->Dimension: 0.46/1.00 1 0.46/1.00 ->Bound: 0.46/1.00 2 0.46/1.00 ->Interpretation: 0.46/1.00 0.46/1.00 [even](X) = 1 0.46/1.00 [gt](X1,X2) = 0 0.46/1.00 [half](X) = X 0.46/1.00 [id](X) = 0 0.46/1.00 [if](X1,X2,X3) = 0 0.46/1.00 [if_times](X1,X2,X3) = 0 0.46/1.00 [not](X) = 0 0.46/1.00 [plus](X1,X2) = 0 0.46/1.00 [times](X1,X2) = 0 0.46/1.00 [0] = 0 0.46/1.00 [fSNonEmpty] = 0 0.46/1.00 [false] = 1 0.46/1.00 [s](X) = 2.X + 2 0.46/1.00 [true] = 1 0.46/1.00 [zero] = 0 0.46/1.00 [EVEN](X) = 0 0.46/1.00 [GT](X1,X2) = 0 0.46/1.00 [HALF](X) = 0 0.46/1.00 [ID](X) = 0 0.46/1.00 [IF](X1,X2,X3) = 0 0.46/1.00 [IF_TIMES](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 0.46/1.00 [NOT](X) = 0 0.46/1.00 [PLUS](X1,X2) = 0 0.46/1.00 [TIMES](X1,X2) = 2.X1 + 2.X2 + 2 0.46/1.00 0.46/1.00 Problem 1.5: 0.46/1.00 0.46/1.00 SCC Processor: 0.46/1.00 -> Pairs: 0.46/1.00 IF_TIMES(ttrue,s(x:S),y:S) -> TIMES(half(s(x:S)),y:S) 0.46/1.00 TIMES(s(x:S),y:S) -> IF_TIMES(even(s(x:S)),s(x:S),y:S) 0.46/1.00 -> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 ->Strongly Connected Components: 0.46/1.00 ->->Cycle: 0.46/1.00 ->->-> Pairs: 0.46/1.00 IF_TIMES(ttrue,s(x:S),y:S) -> TIMES(half(s(x:S)),y:S) 0.46/1.00 TIMES(s(x:S),y:S) -> IF_TIMES(even(s(x:S)),s(x:S),y:S) 0.46/1.00 ->->-> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 0.46/1.00 Problem 1.5: 0.46/1.00 0.46/1.00 Reduction Pairs Processor: 0.46/1.00 -> Pairs: 0.46/1.00 IF_TIMES(ttrue,s(x:S),y:S) -> TIMES(half(s(x:S)),y:S) 0.46/1.00 TIMES(s(x:S),y:S) -> IF_TIMES(even(s(x:S)),s(x:S),y:S) 0.46/1.00 -> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 -> Usable rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 ->Interpretation type: 0.46/1.00 Linear 0.46/1.00 ->Coefficients: 0.46/1.00 All rationals 0.46/1.00 ->Dimension: 0.46/1.00 1 0.46/1.00 ->Bound: 0.46/1.00 2 0.46/1.00 ->Interpretation: 0.46/1.00 0.46/1.00 [even](X) = 1/2.X + 1/2 0.46/1.00 [gt](X1,X2) = 0 0.46/1.00 [half](X) = 1/2.X + 1/2 0.46/1.00 [id](X) = 0 0.46/1.00 [if](X1,X2,X3) = 0 0.46/1.00 [if_times](X1,X2,X3) = 0 0.46/1.00 [not](X) = 0 0.46/1.00 [plus](X1,X2) = 0 0.46/1.00 [times](X1,X2) = 0 0.46/1.00 [0] = 1 0.46/1.00 [fSNonEmpty] = 0 0.46/1.00 [false] = 1/2 0.46/1.00 [s](X) = 2.X + 2 0.46/1.00 [true] = 1 0.46/1.00 [zero] = 0 0.46/1.00 [EVEN](X) = 0 0.46/1.00 [GT](X1,X2) = 0 0.46/1.00 [HALF](X) = 0 0.46/1.00 [ID](X) = 0 0.46/1.00 [IF](X1,X2,X3) = 0 0.46/1.00 [IF_TIMES](X1,X2,X3) = X1 + X2 + 1/2.X3 + 1/2 0.46/1.00 [NOT](X) = 0 0.46/1.00 [PLUS](X1,X2) = 0 0.46/1.00 [TIMES](X1,X2) = 2.X1 + 1/2.X2 0.46/1.00 0.46/1.00 Problem 1.5: 0.46/1.00 0.46/1.00 SCC Processor: 0.46/1.00 -> Pairs: 0.46/1.00 TIMES(s(x:S),y:S) -> IF_TIMES(even(s(x:S)),s(x:S),y:S) 0.46/1.00 -> Rules: 0.46/1.00 even(0) -> ttrue 0.46/1.00 even(s(0)) -> ffalse 0.46/1.00 even(s(s(x:S))) -> even(x:S) 0.46/1.00 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.46/1.00 gt(s(x:S),zero) -> ttrue 0.46/1.00 gt(zero,y:S) -> ffalse 0.46/1.00 half(0) -> 0 0.46/1.00 half(s(s(x:S))) -> s(half(x:S)) 0.46/1.00 id(x:S) -> x:S 0.46/1.00 if(ffalse,x:S,y:S) -> y:S 0.46/1.00 if(ttrue,x:S,y:S) -> x:S 0.46/1.00 if_times(ffalse,s(x:S),y:S) -> plus(y:S,times(x:S,y:S)) 0.46/1.00 if_times(ttrue,s(x:S),y:S) -> plus(times(half(s(x:S)),y:S),times(half(s(x:S)),y:S)) 0.46/1.00 not(x:S) -> if(x:S,ffalse,ttrue) 0.46/1.00 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.46/1.00 plus(s(x:S),s(y:S)) -> s(s(plus(if(gt(x:S,y:S),x:S,y:S),if(not(gt(x:S,y:S)),id(x:S),id(y:S))))) 0.46/1.00 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.46/1.00 plus(zero,y:S) -> y:S 0.46/1.00 times(0,y:S) -> 0 0.46/1.00 times(s(x:S),y:S) -> if_times(even(s(x:S)),s(x:S),y:S) 0.46/1.00 ->Strongly Connected Components: 0.46/1.00 There is no strongly connected component 0.46/1.00 0.46/1.00 The problem is finite. 0.46/1.00 EOF