203.64/204.41 YES 203.64/204.41 203.64/204.41 Problem 1: 203.64/204.41 203.64/204.41 (VAR v_NonEmpty:S x:S y:S) 203.64/204.41 (RULES 203.64/204.41 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.41 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.41 le(0,y:S) -> ttrue 203.64/204.41 le(s(x:S),0) -> ffalse 203.64/204.41 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.41 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.41 minus(x:S,0) -> x:S 203.64/204.41 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 ) 203.64/204.41 (STRATEGY INNERMOST) 203.64/204.41 203.64/204.41 Problem 1: 203.64/204.41 203.64/204.41 Dependency Pairs Processor: 203.64/204.41 -> Pairs: 203.64/204.41 IF_QUOT(ttrue,x:S,y:S) -> MINUS(x:S,y:S) 203.64/204.41 IF_QUOT(ttrue,x:S,y:S) -> QUOT(minus(x:S,y:S),y:S) 203.64/204.41 LE(s(x:S),s(y:S)) -> LE(x:S,y:S) 203.64/204.41 MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) 203.64/204.41 QUOT(x:S,s(y:S)) -> IF_QUOT(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 QUOT(x:S,s(y:S)) -> LE(s(y:S),x:S) 203.64/204.41 -> Rules: 203.64/204.41 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.41 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.41 le(0,y:S) -> ttrue 203.64/204.41 le(s(x:S),0) -> ffalse 203.64/204.41 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.41 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.41 minus(x:S,0) -> x:S 203.64/204.41 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 203.64/204.41 Problem 1: 203.64/204.41 203.64/204.41 SCC Processor: 203.64/204.41 -> Pairs: 203.64/204.41 IF_QUOT(ttrue,x:S,y:S) -> MINUS(x:S,y:S) 203.64/204.41 IF_QUOT(ttrue,x:S,y:S) -> QUOT(minus(x:S,y:S),y:S) 203.64/204.41 LE(s(x:S),s(y:S)) -> LE(x:S,y:S) 203.64/204.41 MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) 203.64/204.41 QUOT(x:S,s(y:S)) -> IF_QUOT(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 QUOT(x:S,s(y:S)) -> LE(s(y:S),x:S) 203.64/204.41 -> Rules: 203.64/204.41 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.41 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.41 le(0,y:S) -> ttrue 203.64/204.41 le(s(x:S),0) -> ffalse 203.64/204.41 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.41 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.41 minus(x:S,0) -> x:S 203.64/204.41 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 ->Strongly Connected Components: 203.64/204.41 ->->Cycle: 203.64/204.41 ->->-> Pairs: 203.64/204.41 MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) 203.64/204.41 ->->-> Rules: 203.64/204.41 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.41 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.41 le(0,y:S) -> ttrue 203.64/204.41 le(s(x:S),0) -> ffalse 203.64/204.41 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.41 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.41 minus(x:S,0) -> x:S 203.64/204.41 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 ->->Cycle: 203.64/204.41 ->->-> Pairs: 203.64/204.41 LE(s(x:S),s(y:S)) -> LE(x:S,y:S) 203.64/204.41 ->->-> Rules: 203.64/204.41 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.41 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.41 le(0,y:S) -> ttrue 203.64/204.41 le(s(x:S),0) -> ffalse 203.64/204.41 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.41 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.41 minus(x:S,0) -> x:S 203.64/204.41 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 ->->Cycle: 203.64/204.41 ->->-> Pairs: 203.64/204.41 IF_QUOT(ttrue,x:S,y:S) -> QUOT(minus(x:S,y:S),y:S) 203.64/204.41 QUOT(x:S,s(y:S)) -> IF_QUOT(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 ->->-> Rules: 203.64/204.41 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.41 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.41 le(0,y:S) -> ttrue 203.64/204.41 le(s(x:S),0) -> ffalse 203.64/204.41 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.41 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.41 minus(x:S,0) -> x:S 203.64/204.41 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 203.64/204.41 203.64/204.41 The problem is decomposed in 3 subproblems. 203.64/204.41 203.64/204.41 Problem 1.1: 203.64/204.41 203.64/204.41 Subterm Processor: 203.64/204.41 -> Pairs: 203.64/204.41 MINUS(s(x:S),s(y:S)) -> MINUS(x:S,y:S) 203.64/204.41 -> Rules: 203.64/204.41 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.41 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.41 le(0,y:S) -> ttrue 203.64/204.41 le(s(x:S),0) -> ffalse 203.64/204.41 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.41 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.41 minus(x:S,0) -> x:S 203.64/204.41 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 ->Projection: 203.64/204.41 pi(MINUS) = 1 203.64/204.41 203.64/204.41 Problem 1.1: 203.64/204.41 203.64/204.41 SCC Processor: 203.64/204.41 -> Pairs: 203.64/204.41 Empty 203.64/204.41 -> Rules: 203.64/204.41 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.41 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.41 le(0,y:S) -> ttrue 203.64/204.41 le(s(x:S),0) -> ffalse 203.64/204.41 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.41 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.41 minus(x:S,0) -> x:S 203.64/204.41 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 ->Strongly Connected Components: 203.64/204.41 There is no strongly connected component 203.64/204.41 203.64/204.41 The problem is finite. 203.64/204.41 203.64/204.41 Problem 1.2: 203.64/204.41 203.64/204.41 Subterm Processor: 203.64/204.41 -> Pairs: 203.64/204.41 LE(s(x:S),s(y:S)) -> LE(x:S,y:S) 203.64/204.41 -> Rules: 203.64/204.41 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.41 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.41 le(0,y:S) -> ttrue 203.64/204.41 le(s(x:S),0) -> ffalse 203.64/204.41 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.41 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.41 minus(x:S,0) -> x:S 203.64/204.41 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 ->Projection: 203.64/204.41 pi(LE) = 1 203.64/204.41 203.64/204.41 Problem 1.2: 203.64/204.41 203.64/204.41 SCC Processor: 203.64/204.41 -> Pairs: 203.64/204.41 Empty 203.64/204.41 -> Rules: 203.64/204.41 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.41 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.41 le(0,y:S) -> ttrue 203.64/204.41 le(s(x:S),0) -> ffalse 203.64/204.41 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.41 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.41 minus(x:S,0) -> x:S 203.64/204.41 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 ->Strongly Connected Components: 203.64/204.41 There is no strongly connected component 203.64/204.41 203.64/204.41 The problem is finite. 203.64/204.41 203.64/204.41 Problem 1.3: 203.64/204.41 203.64/204.41 Narrowing Processor: 203.64/204.41 -> Pairs: 203.64/204.41 IF_QUOT(ttrue,x:S,y:S) -> QUOT(minus(x:S,y:S),y:S) 203.64/204.41 QUOT(x:S,s(y:S)) -> IF_QUOT(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 -> Rules: 203.64/204.41 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.41 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.41 le(0,y:S) -> ttrue 203.64/204.41 le(s(x:S),0) -> ffalse 203.64/204.41 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.41 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.41 minus(x:S,0) -> x:S 203.64/204.41 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 ->Narrowed Pairs: 203.64/204.41 ->->Original Pair: 203.64/204.41 QUOT(x:S,s(y:S)) -> IF_QUOT(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 ->-> Narrowed pairs: 203.64/204.41 QUOT(0,s(x:S)) -> IF_QUOT(ffalse,0,s(x:S)) 203.64/204.41 QUOT(s(y:S),s(x:S)) -> IF_QUOT(le(x:S,y:S),s(y:S),s(x:S)) 203.64/204.41 203.64/204.41 Problem 1.3: 203.64/204.41 203.64/204.41 SCC Processor: 203.64/204.41 -> Pairs: 203.64/204.41 IF_QUOT(ttrue,x:S,y:S) -> QUOT(minus(x:S,y:S),y:S) 203.64/204.41 QUOT(0,s(x:S)) -> IF_QUOT(ffalse,0,s(x:S)) 203.64/204.41 QUOT(s(y:S),s(x:S)) -> IF_QUOT(le(x:S,y:S),s(y:S),s(x:S)) 203.64/204.41 -> Rules: 203.64/204.41 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.41 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.41 le(0,y:S) -> ttrue 203.64/204.41 le(s(x:S),0) -> ffalse 203.64/204.41 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.41 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.41 minus(x:S,0) -> x:S 203.64/204.41 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 ->Strongly Connected Components: 203.64/204.41 ->->Cycle: 203.64/204.41 ->->-> Pairs: 203.64/204.41 IF_QUOT(ttrue,x:S,y:S) -> QUOT(minus(x:S,y:S),y:S) 203.64/204.41 QUOT(s(y:S),s(x:S)) -> IF_QUOT(le(x:S,y:S),s(y:S),s(x:S)) 203.64/204.41 ->->-> Rules: 203.64/204.41 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.41 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.41 le(0,y:S) -> ttrue 203.64/204.41 le(s(x:S),0) -> ffalse 203.64/204.41 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.41 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.41 minus(x:S,0) -> x:S 203.64/204.41 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 203.64/204.41 Problem 1.3: 203.64/204.41 203.64/204.41 Narrowing Processor: 203.64/204.41 -> Pairs: 203.64/204.41 IF_QUOT(ttrue,x:S,y:S) -> QUOT(minus(x:S,y:S),y:S) 203.64/204.41 QUOT(s(y:S),s(x:S)) -> IF_QUOT(le(x:S,y:S),s(y:S),s(x:S)) 203.64/204.41 -> Rules: 203.64/204.41 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.41 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.41 le(0,y:S) -> ttrue 203.64/204.41 le(s(x:S),0) -> ffalse 203.64/204.41 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.41 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.41 minus(x:S,0) -> x:S 203.64/204.41 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 ->Narrowed Pairs: 203.64/204.41 ->->Original Pair: 203.64/204.41 IF_QUOT(ttrue,x:S,y:S) -> QUOT(minus(x:S,y:S),y:S) 203.64/204.41 ->-> Narrowed pairs: 203.64/204.41 IF_QUOT(ttrue,s(x:S),s(y:S)) -> QUOT(minus(x:S,y:S),s(y:S)) 203.64/204.41 IF_QUOT(ttrue,x:S,0) -> QUOT(x:S,0) 203.64/204.41 ->->Original Pair: 203.64/204.41 QUOT(s(y:S),s(x:S)) -> IF_QUOT(le(x:S,y:S),s(y:S),s(x:S)) 203.64/204.41 ->-> Narrowed pairs: 203.64/204.41 QUOT(s(0),s(s(x:S))) -> IF_QUOT(ffalse,s(0),s(s(x:S))) 203.64/204.41 QUOT(s(s(y:S)),s(s(x:S))) -> IF_QUOT(le(x:S,y:S),s(s(y:S)),s(s(x:S))) 203.64/204.41 QUOT(s(y:S),s(0)) -> IF_QUOT(ttrue,s(y:S),s(0)) 203.64/204.41 203.64/204.41 Problem 1.3: 203.64/204.41 203.64/204.41 SCC Processor: 203.64/204.41 -> Pairs: 203.64/204.41 IF_QUOT(ttrue,s(x:S),s(y:S)) -> QUOT(minus(x:S,y:S),s(y:S)) 203.64/204.41 IF_QUOT(ttrue,x:S,0) -> QUOT(x:S,0) 203.64/204.41 QUOT(s(0),s(s(x:S))) -> IF_QUOT(ffalse,s(0),s(s(x:S))) 203.64/204.41 QUOT(s(s(y:S)),s(s(x:S))) -> IF_QUOT(le(x:S,y:S),s(s(y:S)),s(s(x:S))) 203.64/204.41 QUOT(s(y:S),s(0)) -> IF_QUOT(ttrue,s(y:S),s(0)) 203.64/204.41 -> Rules: 203.64/204.41 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.41 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.41 le(0,y:S) -> ttrue 203.64/204.41 le(s(x:S),0) -> ffalse 203.64/204.41 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.41 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.41 minus(x:S,0) -> x:S 203.64/204.41 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.41 ->Strongly Connected Components: 203.64/204.41 ->->Cycle: 203.64/204.41 ->->-> Pairs: 203.64/204.41 IF_QUOT(ttrue,s(x:S),s(y:S)) -> QUOT(minus(x:S,y:S),s(y:S)) 203.64/204.41 QUOT(s(s(y:S)),s(s(x:S))) -> IF_QUOT(le(x:S,y:S),s(s(y:S)),s(s(x:S))) 203.64/204.41 QUOT(s(y:S),s(0)) -> IF_QUOT(ttrue,s(y:S),s(0)) 203.64/204.41 ->->-> Rules: 203.64/204.41 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.41 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.41 le(0,y:S) -> ttrue 203.64/204.41 le(s(x:S),0) -> ffalse 203.64/204.41 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.41 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.41 minus(x:S,0) -> x:S 203.64/204.41 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.43 203.64/204.43 Problem 1.3: 203.64/204.43 203.64/204.43 Reduction Pairs Processor: 203.64/204.43 -> Pairs: 203.64/204.43 IF_QUOT(ttrue,s(x:S),s(y:S)) -> QUOT(minus(x:S,y:S),s(y:S)) 203.64/204.43 QUOT(s(s(y:S)),s(s(x:S))) -> IF_QUOT(le(x:S,y:S),s(s(y:S)),s(s(x:S))) 203.64/204.43 QUOT(s(y:S),s(0)) -> IF_QUOT(ttrue,s(y:S),s(0)) 203.64/204.43 -> Rules: 203.64/204.43 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.43 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.43 le(0,y:S) -> ttrue 203.64/204.43 le(s(x:S),0) -> ffalse 203.64/204.43 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.43 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.43 minus(x:S,0) -> x:S 203.64/204.43 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.43 -> Usable rules: 203.64/204.43 le(0,y:S) -> ttrue 203.64/204.43 le(s(x:S),0) -> ffalse 203.64/204.43 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.43 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.43 minus(x:S,0) -> x:S 203.64/204.43 ->Interpretation type: 203.64/204.43 Linear 203.64/204.43 ->Coefficients: 203.64/204.43 Natural Numbers 203.64/204.43 ->Dimension: 203.64/204.43 1 203.64/204.43 ->Bound: 203.64/204.43 2 203.64/204.43 ->Interpretation: 203.64/204.43 203.64/204.43 [if_quot](X1,X2,X3) = 0 203.64/204.43 [le](X1,X2) = 0 203.64/204.43 [minus](X1,X2) = 2.X1 + 1 203.64/204.43 [quot](X1,X2) = 0 203.64/204.43 [0] = 2 203.64/204.43 [fSNonEmpty] = 0 203.64/204.43 [false] = 0 203.64/204.43 [s](X) = 2.X + 2 203.64/204.43 [true] = 0 203.64/204.43 [IF_QUOT](X1,X2,X3) = 2.X1 + 2.X2 203.64/204.43 [LE](X1,X2) = 0 203.64/204.43 [MINUS](X1,X2) = 0 203.64/204.43 [QUOT](X1,X2) = 2.X1 203.64/204.43 203.64/204.43 Problem 1.3: 203.64/204.43 203.64/204.43 SCC Processor: 203.64/204.43 -> Pairs: 203.64/204.43 QUOT(s(s(y:S)),s(s(x:S))) -> IF_QUOT(le(x:S,y:S),s(s(y:S)),s(s(x:S))) 203.64/204.43 QUOT(s(y:S),s(0)) -> IF_QUOT(ttrue,s(y:S),s(0)) 203.64/204.43 -> Rules: 203.64/204.43 if_quot(ffalse,x:S,y:S) -> 0 203.64/204.43 if_quot(ttrue,x:S,y:S) -> s(quot(minus(x:S,y:S),y:S)) 203.64/204.43 le(0,y:S) -> ttrue 203.64/204.43 le(s(x:S),0) -> ffalse 203.64/204.43 le(s(x:S),s(y:S)) -> le(x:S,y:S) 203.64/204.43 minus(s(x:S),s(y:S)) -> minus(x:S,y:S) 203.64/204.43 minus(x:S,0) -> x:S 203.64/204.43 quot(x:S,s(y:S)) -> if_quot(le(s(y:S),x:S),x:S,s(y:S)) 203.64/204.43 ->Strongly Connected Components: 203.64/204.43 There is no strongly connected component 203.64/204.43 203.64/204.43 The problem is finite. 203.64/204.43 EOF