0.00/0.42 YES 0.00/0.42 0.00/0.42 Problem 1: 0.00/0.42 0.00/0.42 (VAR v_NonEmpty:S x:S y:S z:S) 0.00/0.42 (RULES 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 ) 0.00/0.42 (STRATEGY INNERMOST) 0.00/0.42 0.00/0.42 Problem 1: 0.00/0.42 0.00/0.42 Dependency Pairs Processor: 0.00/0.42 -> Pairs: 0.00/0.42 GT(s(x:S),s(y:S)) -> GT(x:S,y:S) 0.00/0.42 NOT(x:S) -> IF(x:S,ffalse,ttrue) 0.00/0.42 PLUS(s(x:S),s(y:S)) -> GT(x:S,y:S) 0.00/0.42 PLUS(s(x:S),s(y:S)) -> ID(x:S) 0.00/0.42 PLUS(s(x:S),s(y:S)) -> ID(y:S) 0.00/0.42 PLUS(s(x:S),s(y:S)) -> IF(gt(x:S,y:S),x:S,y:S) 0.00/0.42 PLUS(s(x:S),s(y:S)) -> IF(not(gt(x:S,y:S)),id(x:S),id(y:S)) 0.00/0.42 PLUS(s(x:S),s(y:S)) -> NOT(gt(x:S,y:S)) 0.00/0.42 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.00/0.42 PLUS(s(x:S),x:S) -> GT(x:S,x:S) 0.00/0.42 PLUS(s(x:S),x:S) -> ID(x:S) 0.00/0.42 PLUS(s(x:S),x:S) -> IF(gt(x:S,x:S),id(x:S),id(x:S)) 0.00/0.42 PLUS(s(x:S),x:S) -> PLUS(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 QUOT(s(x:S),s(y:S),z:S) -> QUOT(x:S,y:S,z:S) 0.00/0.42 QUOT(x:S,0,s(z:S)) -> PLUS(z:S,s(0)) 0.00/0.42 QUOT(x:S,0,s(z:S)) -> QUOT(x:S,plus(z:S,s(0)),s(z:S)) 0.00/0.42 -> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 0.00/0.42 Problem 1: 0.00/0.42 0.00/0.42 SCC Processor: 0.00/0.42 -> Pairs: 0.00/0.42 GT(s(x:S),s(y:S)) -> GT(x:S,y:S) 0.00/0.42 NOT(x:S) -> IF(x:S,ffalse,ttrue) 0.00/0.42 PLUS(s(x:S),s(y:S)) -> GT(x:S,y:S) 0.00/0.42 PLUS(s(x:S),s(y:S)) -> ID(x:S) 0.00/0.42 PLUS(s(x:S),s(y:S)) -> ID(y:S) 0.00/0.42 PLUS(s(x:S),s(y:S)) -> IF(gt(x:S,y:S),x:S,y:S) 0.00/0.42 PLUS(s(x:S),s(y:S)) -> IF(not(gt(x:S,y:S)),id(x:S),id(y:S)) 0.00/0.42 PLUS(s(x:S),s(y:S)) -> NOT(gt(x:S,y:S)) 0.00/0.42 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.00/0.42 PLUS(s(x:S),x:S) -> GT(x:S,x:S) 0.00/0.42 PLUS(s(x:S),x:S) -> ID(x:S) 0.00/0.42 PLUS(s(x:S),x:S) -> IF(gt(x:S,x:S),id(x:S),id(x:S)) 0.00/0.42 PLUS(s(x:S),x:S) -> PLUS(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 QUOT(s(x:S),s(y:S),z:S) -> QUOT(x:S,y:S,z:S) 0.00/0.42 QUOT(x:S,0,s(z:S)) -> PLUS(z:S,s(0)) 0.00/0.42 QUOT(x:S,0,s(z:S)) -> QUOT(x:S,plus(z:S,s(0)),s(z:S)) 0.00/0.42 -> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 ->Strongly Connected Components: 0.00/0.42 ->->Cycle: 0.00/0.42 ->->-> Pairs: 0.00/0.42 GT(s(x:S),s(y:S)) -> GT(x:S,y:S) 0.00/0.42 ->->-> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 ->->Cycle: 0.00/0.42 ->->-> Pairs: 0.00/0.42 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.00/0.42 PLUS(s(x:S),x:S) -> PLUS(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 ->->-> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 ->->Cycle: 0.00/0.42 ->->-> Pairs: 0.00/0.42 QUOT(s(x:S),s(y:S),z:S) -> QUOT(x:S,y:S,z:S) 0.00/0.42 QUOT(x:S,0,s(z:S)) -> QUOT(x:S,plus(z:S,s(0)),s(z:S)) 0.00/0.42 ->->-> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 0.00/0.42 0.00/0.42 The problem is decomposed in 3 subproblems. 0.00/0.42 0.00/0.42 Problem 1.1: 0.00/0.42 0.00/0.42 Subterm Processor: 0.00/0.42 -> Pairs: 0.00/0.42 GT(s(x:S),s(y:S)) -> GT(x:S,y:S) 0.00/0.42 -> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 ->Projection: 0.00/0.42 pi(GT) = 1 0.00/0.42 0.00/0.42 Problem 1.1: 0.00/0.42 0.00/0.42 SCC Processor: 0.00/0.42 -> Pairs: 0.00/0.42 Empty 0.00/0.42 -> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 ->Strongly Connected Components: 0.00/0.42 There is no strongly connected component 0.00/0.42 0.00/0.42 The problem is finite. 0.00/0.42 0.00/0.42 Problem 1.2: 0.00/0.42 0.00/0.42 Reduction Pairs Processor: 0.00/0.42 -> Pairs: 0.00/0.42 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.00/0.42 PLUS(s(x:S),x:S) -> PLUS(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 -> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 -> Usable rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 ->Interpretation type: 0.00/0.42 Linear 0.00/0.42 ->Coefficients: 0.00/0.42 All rationals 0.00/0.42 ->Dimension: 0.00/0.42 1 0.00/0.42 ->Bound: 0.00/0.42 4 0.00/0.42 ->Interpretation: 0.00/0.42 0.00/0.42 [gt](X1,X2) = 3.X1 + 1 0.00/0.42 [id](X) = X 0.00/0.42 [if](X1,X2,X3) = X2 + X3 0.00/0.42 [not](X) = 3.X + 4 0.00/0.42 [plus](X1,X2) = 0 0.00/0.42 [quot](X1,X2,X3) = 0 0.00/0.42 [0] = 0 0.00/0.42 [fSNonEmpty] = 0 0.00/0.42 [false] = 3 0.00/0.42 [s](X) = 4.X + 3/2 0.00/0.42 [true] = 0 0.00/0.42 [zero] = 3/4 0.00/0.42 [GT](X1,X2) = 0 0.00/0.42 [ID](X) = 0 0.00/0.42 [IF](X1,X2,X3) = 0 0.00/0.42 [NOT](X) = 0 0.00/0.42 [PLUS](X1,X2) = 4.X1 + 2.X2 0.00/0.42 [QUOT](X1,X2,X3) = 0 0.00/0.42 0.00/0.42 Problem 1.2: 0.00/0.42 0.00/0.42 SCC Processor: 0.00/0.42 -> Pairs: 0.00/0.42 PLUS(s(x:S),x:S) -> PLUS(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 -> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 ->Strongly Connected Components: 0.00/0.42 ->->Cycle: 0.00/0.42 ->->-> Pairs: 0.00/0.42 PLUS(s(x:S),x:S) -> PLUS(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 ->->-> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 0.00/0.42 Problem 1.2: 0.00/0.42 0.00/0.42 Reduction Pairs Processor: 0.00/0.42 -> Pairs: 0.00/0.42 PLUS(s(x:S),x:S) -> PLUS(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 -> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 -> Usable rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 ->Interpretation type: 0.00/0.42 Linear 0.00/0.42 ->Coefficients: 0.00/0.42 Natural Numbers 0.00/0.42 ->Dimension: 0.00/0.42 1 0.00/0.42 ->Bound: 0.00/0.42 2 0.00/0.42 ->Interpretation: 0.00/0.42 0.00/0.42 [gt](X1,X2) = 2.X1 + 2 0.00/0.42 [id](X) = X 0.00/0.42 [if](X1,X2,X3) = X2 + X3 0.00/0.42 [not](X) = 0 0.00/0.42 [plus](X1,X2) = 0 0.00/0.42 [quot](X1,X2,X3) = 0 0.00/0.42 [0] = 0 0.00/0.42 [fSNonEmpty] = 0 0.00/0.42 [false] = 2 0.00/0.42 [s](X) = 2.X + 1 0.00/0.42 [true] = 1 0.00/0.42 [zero] = 2 0.00/0.42 [GT](X1,X2) = 0 0.00/0.42 [ID](X) = 0 0.00/0.42 [IF](X1,X2,X3) = 0 0.00/0.42 [NOT](X) = 0 0.00/0.42 [PLUS](X1,X2) = 2.X1 0.00/0.42 [QUOT](X1,X2,X3) = 0 0.00/0.42 0.00/0.42 Problem 1.2: 0.00/0.42 0.00/0.42 SCC Processor: 0.00/0.42 -> Pairs: 0.00/0.42 Empty 0.00/0.42 -> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 ->Strongly Connected Components: 0.00/0.42 There is no strongly connected component 0.00/0.42 0.00/0.42 The problem is finite. 0.00/0.42 0.00/0.42 Problem 1.3: 0.00/0.42 0.00/0.42 Subterm Processor: 0.00/0.42 -> Pairs: 0.00/0.42 QUOT(s(x:S),s(y:S),z:S) -> QUOT(x:S,y:S,z:S) 0.00/0.42 QUOT(x:S,0,s(z:S)) -> QUOT(x:S,plus(z:S,s(0)),s(z:S)) 0.00/0.42 -> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 ->Projection: 0.00/0.42 pi(QUOT) = 1 0.00/0.42 0.00/0.42 Problem 1.3: 0.00/0.42 0.00/0.42 SCC Processor: 0.00/0.42 -> Pairs: 0.00/0.42 QUOT(x:S,0,s(z:S)) -> QUOT(x:S,plus(z:S,s(0)),s(z:S)) 0.00/0.42 -> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 ->Strongly Connected Components: 0.00/0.42 ->->Cycle: 0.00/0.42 ->->-> Pairs: 0.00/0.42 QUOT(x:S,0,s(z:S)) -> QUOT(x:S,plus(z:S,s(0)),s(z:S)) 0.00/0.42 ->->-> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 0.00/0.42 Problem 1.3: 0.00/0.42 0.00/0.42 Reduction Pairs Processor: 0.00/0.42 -> Pairs: 0.00/0.42 QUOT(x:S,0,s(z:S)) -> QUOT(x:S,plus(z:S,s(0)),s(z:S)) 0.00/0.42 -> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 -> Usable rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 ->Interpretation type: 0.00/0.42 Linear 0.00/0.42 ->Coefficients: 0.00/0.42 Natural Numbers 0.00/0.42 ->Dimension: 0.00/0.42 1 0.00/0.42 ->Bound: 0.00/0.42 2 0.00/0.42 ->Interpretation: 0.00/0.42 0.00/0.42 [gt](X1,X2) = 2 0.00/0.42 [id](X) = X + 2 0.00/0.42 [if](X1,X2,X3) = 2.X2 + X3 0.00/0.42 [not](X) = 2 0.00/0.42 [plus](X1,X2) = X2 0.00/0.42 [quot](X1,X2,X3) = 0 0.00/0.42 [0] = 2 0.00/0.42 [fSNonEmpty] = 0 0.00/0.42 [false] = 0 0.00/0.42 [s](X) = 0 0.00/0.42 [true] = 2 0.00/0.42 [zero] = 2 0.00/0.42 [GT](X1,X2) = 0 0.00/0.42 [ID](X) = 0 0.00/0.42 [IF](X1,X2,X3) = 0 0.00/0.42 [NOT](X) = 0 0.00/0.42 [PLUS](X1,X2) = 0 0.00/0.42 [QUOT](X1,X2,X3) = 2.X2 0.00/0.42 0.00/0.42 Problem 1.3: 0.00/0.42 0.00/0.42 SCC Processor: 0.00/0.42 -> Pairs: 0.00/0.42 Empty 0.00/0.42 -> Rules: 0.00/0.42 gt(s(x:S),s(y:S)) -> gt(x:S,y:S) 0.00/0.42 gt(s(x:S),zero) -> ttrue 0.00/0.42 gt(zero,y:S) -> ffalse 0.00/0.42 id(x:S) -> x:S 0.00/0.42 if(ffalse,x:S,y:S) -> y:S 0.00/0.42 if(ttrue,x:S,y:S) -> x:S 0.00/0.42 not(x:S) -> if(x:S,ffalse,ttrue) 0.00/0.42 plus(id(x:S),s(y:S)) -> s(plus(x:S,if(gt(s(y:S),y:S),y:S,s(y:S)))) 0.00/0.42 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.00/0.42 plus(s(x:S),x:S) -> plus(if(gt(x:S,x:S),id(x:S),id(x:S)),s(x:S)) 0.00/0.42 plus(zero,y:S) -> y:S 0.00/0.42 quot(0,s(y:S),s(z:S)) -> 0 0.00/0.42 quot(s(x:S),s(y:S),z:S) -> quot(x:S,y:S,z:S) 0.00/0.42 quot(x:S,0,s(z:S)) -> s(quot(x:S,plus(z:S,s(0)),s(z:S))) 0.00/0.42 ->Strongly Connected Components: 0.00/0.42 There is no strongly connected component 0.00/0.42 0.00/0.42 The problem is finite. 0.00/0.42 EOF