3.17/3.26 YES 3.17/3.26 3.17/3.26 Problem 1: 3.17/3.26 3.17/3.26 (VAR v_NonEmpty:S X:S X1:S X2:S X3:S Y:S) 3.17/3.26 (RULES 3.17/3.26 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.26 active(div(0,s(Y:S))) -> mark(0) 3.17/3.26 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.26 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.26 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.26 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.26 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.26 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.26 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.26 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.26 active(minus(0,Y:S)) -> mark(0) 3.17/3.26 active(s(X:S)) -> s(active(X:S)) 3.17/3.26 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.26 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.26 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.26 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.26 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.26 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.26 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.26 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.26 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.26 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.26 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.26 proper(0) -> ok(0) 3.17/3.26 proper(ffalse) -> ok(ffalse) 3.17/3.26 proper(ttrue) -> ok(ttrue) 3.17/3.26 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.26 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.26 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.26 top(ok(X:S)) -> top(active(X:S)) 3.17/3.26 ) 3.17/3.26 (STRATEGY INNERMOST) 3.17/3.26 3.17/3.26 Problem 1: 3.17/3.26 3.17/3.26 Dependency Pairs Processor: 3.17/3.26 -> Pairs: 3.17/3.26 ACTIVE(div(s(X:S),s(Y:S))) -> DIV(minus(X:S,Y:S),s(Y:S)) 3.17/3.26 ACTIVE(div(s(X:S),s(Y:S))) -> GEQ(X:S,Y:S) 3.17/3.26 ACTIVE(div(s(X:S),s(Y:S))) -> IF(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0) 3.17/3.26 ACTIVE(div(s(X:S),s(Y:S))) -> MINUS(X:S,Y:S) 3.17/3.26 ACTIVE(div(s(X:S),s(Y:S))) -> S(div(minus(X:S,Y:S),s(Y:S))) 3.17/3.26 ACTIVE(div(X1:S,X2:S)) -> ACTIVE(X1:S) 3.17/3.26 ACTIVE(div(X1:S,X2:S)) -> DIV(active(X1:S),X2:S) 3.17/3.26 ACTIVE(geq(s(X:S),s(Y:S))) -> GEQ(X:S,Y:S) 3.17/3.26 ACTIVE(if(X1:S,X2:S,X3:S)) -> ACTIVE(X1:S) 3.17/3.26 ACTIVE(if(X1:S,X2:S,X3:S)) -> IF(active(X1:S),X2:S,X3:S) 3.17/3.26 ACTIVE(minus(s(X:S),s(Y:S))) -> MINUS(X:S,Y:S) 3.17/3.26 ACTIVE(s(X:S)) -> ACTIVE(X:S) 3.17/3.26 ACTIVE(s(X:S)) -> S(active(X:S)) 3.17/3.26 DIV(mark(X1:S),X2:S) -> DIV(X1:S,X2:S) 3.17/3.26 DIV(ok(X1:S),ok(X2:S)) -> DIV(X1:S,X2:S) 3.17/3.26 GEQ(ok(X1:S),ok(X2:S)) -> GEQ(X1:S,X2:S) 3.17/3.26 IF(mark(X1:S),X2:S,X3:S) -> IF(X1:S,X2:S,X3:S) 3.17/3.26 IF(ok(X1:S),ok(X2:S),ok(X3:S)) -> IF(X1:S,X2:S,X3:S) 3.17/3.26 MINUS(ok(X1:S),ok(X2:S)) -> MINUS(X1:S,X2:S) 3.17/3.26 PROPER(div(X1:S,X2:S)) -> DIV(proper(X1:S),proper(X2:S)) 3.17/3.26 PROPER(div(X1:S,X2:S)) -> PROPER(X1:S) 3.17/3.26 PROPER(div(X1:S,X2:S)) -> PROPER(X2:S) 3.17/3.26 PROPER(geq(X1:S,X2:S)) -> GEQ(proper(X1:S),proper(X2:S)) 3.17/3.26 PROPER(geq(X1:S,X2:S)) -> PROPER(X1:S) 3.17/3.26 PROPER(geq(X1:S,X2:S)) -> PROPER(X2:S) 3.17/3.26 PROPER(if(X1:S,X2:S,X3:S)) -> IF(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.26 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X1:S) 3.17/3.26 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X2:S) 3.17/3.26 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X3:S) 3.17/3.26 PROPER(minus(X1:S,X2:S)) -> MINUS(proper(X1:S),proper(X2:S)) 3.17/3.26 PROPER(minus(X1:S,X2:S)) -> PROPER(X1:S) 3.17/3.26 PROPER(minus(X1:S,X2:S)) -> PROPER(X2:S) 3.17/3.26 PROPER(s(X:S)) -> PROPER(X:S) 3.17/3.26 PROPER(s(X:S)) -> S(proper(X:S)) 3.17/3.26 S(mark(X:S)) -> S(X:S) 3.17/3.26 S(ok(X:S)) -> S(X:S) 3.17/3.26 TOP(mark(X:S)) -> PROPER(X:S) 3.17/3.26 TOP(mark(X:S)) -> TOP(proper(X:S)) 3.17/3.26 TOP(ok(X:S)) -> ACTIVE(X:S) 3.17/3.26 TOP(ok(X:S)) -> TOP(active(X:S)) 3.17/3.26 -> Rules: 3.17/3.26 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.26 active(div(0,s(Y:S))) -> mark(0) 3.17/3.26 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.26 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.26 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.26 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.26 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.26 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.26 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.26 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.26 active(minus(0,Y:S)) -> mark(0) 3.17/3.26 active(s(X:S)) -> s(active(X:S)) 3.17/3.26 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.26 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.26 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.26 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.26 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.26 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.26 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.26 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.26 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.26 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.26 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.26 proper(0) -> ok(0) 3.17/3.26 proper(ffalse) -> ok(ffalse) 3.17/3.26 proper(ttrue) -> ok(ttrue) 3.17/3.26 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.26 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.26 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.26 top(ok(X:S)) -> top(active(X:S)) 3.17/3.26 3.17/3.26 Problem 1: 3.17/3.26 3.17/3.26 SCC Processor: 3.17/3.26 -> Pairs: 3.17/3.26 ACTIVE(div(s(X:S),s(Y:S))) -> DIV(minus(X:S,Y:S),s(Y:S)) 3.17/3.26 ACTIVE(div(s(X:S),s(Y:S))) -> GEQ(X:S,Y:S) 3.17/3.26 ACTIVE(div(s(X:S),s(Y:S))) -> IF(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0) 3.17/3.26 ACTIVE(div(s(X:S),s(Y:S))) -> MINUS(X:S,Y:S) 3.17/3.26 ACTIVE(div(s(X:S),s(Y:S))) -> S(div(minus(X:S,Y:S),s(Y:S))) 3.17/3.26 ACTIVE(div(X1:S,X2:S)) -> ACTIVE(X1:S) 3.17/3.26 ACTIVE(div(X1:S,X2:S)) -> DIV(active(X1:S),X2:S) 3.17/3.26 ACTIVE(geq(s(X:S),s(Y:S))) -> GEQ(X:S,Y:S) 3.17/3.26 ACTIVE(if(X1:S,X2:S,X3:S)) -> ACTIVE(X1:S) 3.17/3.26 ACTIVE(if(X1:S,X2:S,X3:S)) -> IF(active(X1:S),X2:S,X3:S) 3.17/3.26 ACTIVE(minus(s(X:S),s(Y:S))) -> MINUS(X:S,Y:S) 3.17/3.26 ACTIVE(s(X:S)) -> ACTIVE(X:S) 3.17/3.26 ACTIVE(s(X:S)) -> S(active(X:S)) 3.17/3.26 DIV(mark(X1:S),X2:S) -> DIV(X1:S,X2:S) 3.17/3.26 DIV(ok(X1:S),ok(X2:S)) -> DIV(X1:S,X2:S) 3.17/3.26 GEQ(ok(X1:S),ok(X2:S)) -> GEQ(X1:S,X2:S) 3.17/3.26 IF(mark(X1:S),X2:S,X3:S) -> IF(X1:S,X2:S,X3:S) 3.17/3.26 IF(ok(X1:S),ok(X2:S),ok(X3:S)) -> IF(X1:S,X2:S,X3:S) 3.17/3.26 MINUS(ok(X1:S),ok(X2:S)) -> MINUS(X1:S,X2:S) 3.17/3.26 PROPER(div(X1:S,X2:S)) -> DIV(proper(X1:S),proper(X2:S)) 3.17/3.26 PROPER(div(X1:S,X2:S)) -> PROPER(X1:S) 3.17/3.26 PROPER(div(X1:S,X2:S)) -> PROPER(X2:S) 3.17/3.26 PROPER(geq(X1:S,X2:S)) -> GEQ(proper(X1:S),proper(X2:S)) 3.17/3.26 PROPER(geq(X1:S,X2:S)) -> PROPER(X1:S) 3.17/3.26 PROPER(geq(X1:S,X2:S)) -> PROPER(X2:S) 3.17/3.26 PROPER(if(X1:S,X2:S,X3:S)) -> IF(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.26 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X1:S) 3.17/3.26 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X2:S) 3.17/3.26 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X3:S) 3.17/3.26 PROPER(minus(X1:S,X2:S)) -> MINUS(proper(X1:S),proper(X2:S)) 3.17/3.26 PROPER(minus(X1:S,X2:S)) -> PROPER(X1:S) 3.17/3.26 PROPER(minus(X1:S,X2:S)) -> PROPER(X2:S) 3.17/3.26 PROPER(s(X:S)) -> PROPER(X:S) 3.17/3.26 PROPER(s(X:S)) -> S(proper(X:S)) 3.17/3.26 S(mark(X:S)) -> S(X:S) 3.17/3.26 S(ok(X:S)) -> S(X:S) 3.17/3.26 TOP(mark(X:S)) -> PROPER(X:S) 3.17/3.26 TOP(mark(X:S)) -> TOP(proper(X:S)) 3.17/3.26 TOP(ok(X:S)) -> ACTIVE(X:S) 3.17/3.26 TOP(ok(X:S)) -> TOP(active(X:S)) 3.17/3.26 -> Rules: 3.17/3.26 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.26 active(div(0,s(Y:S))) -> mark(0) 3.17/3.26 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.26 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.26 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.26 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.26 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.26 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.26 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.26 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.26 active(minus(0,Y:S)) -> mark(0) 3.17/3.26 active(s(X:S)) -> s(active(X:S)) 3.17/3.26 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.26 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.26 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.26 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.26 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Strongly Connected Components: 3.17/3.27 ->->Cycle: 3.17/3.27 ->->-> Pairs: 3.17/3.27 S(mark(X:S)) -> S(X:S) 3.17/3.27 S(ok(X:S)) -> S(X:S) 3.17/3.27 ->->-> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->->Cycle: 3.17/3.27 ->->-> Pairs: 3.17/3.27 MINUS(ok(X1:S),ok(X2:S)) -> MINUS(X1:S,X2:S) 3.17/3.27 ->->-> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->->Cycle: 3.17/3.27 ->->-> Pairs: 3.17/3.27 IF(mark(X1:S),X2:S,X3:S) -> IF(X1:S,X2:S,X3:S) 3.17/3.27 IF(ok(X1:S),ok(X2:S),ok(X3:S)) -> IF(X1:S,X2:S,X3:S) 3.17/3.27 ->->-> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->->Cycle: 3.17/3.27 ->->-> Pairs: 3.17/3.27 GEQ(ok(X1:S),ok(X2:S)) -> GEQ(X1:S,X2:S) 3.17/3.27 ->->-> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->->Cycle: 3.17/3.27 ->->-> Pairs: 3.17/3.27 DIV(mark(X1:S),X2:S) -> DIV(X1:S,X2:S) 3.17/3.27 DIV(ok(X1:S),ok(X2:S)) -> DIV(X1:S,X2:S) 3.17/3.27 ->->-> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->->Cycle: 3.17/3.27 ->->-> Pairs: 3.17/3.27 PROPER(div(X1:S,X2:S)) -> PROPER(X1:S) 3.17/3.27 PROPER(div(X1:S,X2:S)) -> PROPER(X2:S) 3.17/3.27 PROPER(geq(X1:S,X2:S)) -> PROPER(X1:S) 3.17/3.27 PROPER(geq(X1:S,X2:S)) -> PROPER(X2:S) 3.17/3.27 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X1:S) 3.17/3.27 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X2:S) 3.17/3.27 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X3:S) 3.17/3.27 PROPER(minus(X1:S,X2:S)) -> PROPER(X1:S) 3.17/3.27 PROPER(minus(X1:S,X2:S)) -> PROPER(X2:S) 3.17/3.27 PROPER(s(X:S)) -> PROPER(X:S) 3.17/3.27 ->->-> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->->Cycle: 3.17/3.27 ->->-> Pairs: 3.17/3.27 ACTIVE(div(X1:S,X2:S)) -> ACTIVE(X1:S) 3.17/3.27 ACTIVE(if(X1:S,X2:S,X3:S)) -> ACTIVE(X1:S) 3.17/3.27 ACTIVE(s(X:S)) -> ACTIVE(X:S) 3.17/3.27 ->->-> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->->Cycle: 3.17/3.27 ->->-> Pairs: 3.17/3.27 TOP(mark(X:S)) -> TOP(proper(X:S)) 3.17/3.27 TOP(ok(X:S)) -> TOP(active(X:S)) 3.17/3.27 ->->-> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 3.17/3.27 3.17/3.27 The problem is decomposed in 8 subproblems. 3.17/3.27 3.17/3.27 Problem 1.1: 3.17/3.27 3.17/3.27 Subterm Processor: 3.17/3.27 -> Pairs: 3.17/3.27 S(mark(X:S)) -> S(X:S) 3.17/3.27 S(ok(X:S)) -> S(X:S) 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Projection: 3.17/3.27 pi(S) = 1 3.17/3.27 3.17/3.27 Problem 1.1: 3.17/3.27 3.17/3.27 SCC Processor: 3.17/3.27 -> Pairs: 3.17/3.27 Empty 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Strongly Connected Components: 3.17/3.27 There is no strongly connected component 3.17/3.27 3.17/3.27 The problem is finite. 3.17/3.27 3.17/3.27 Problem 1.2: 3.17/3.27 3.17/3.27 Subterm Processor: 3.17/3.27 -> Pairs: 3.17/3.27 MINUS(ok(X1:S),ok(X2:S)) -> MINUS(X1:S,X2:S) 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Projection: 3.17/3.27 pi(MINUS) = 1 3.17/3.27 3.17/3.27 Problem 1.2: 3.17/3.27 3.17/3.27 SCC Processor: 3.17/3.27 -> Pairs: 3.17/3.27 Empty 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Strongly Connected Components: 3.17/3.27 There is no strongly connected component 3.17/3.27 3.17/3.27 The problem is finite. 3.17/3.27 3.17/3.27 Problem 1.3: 3.17/3.27 3.17/3.27 Subterm Processor: 3.17/3.27 -> Pairs: 3.17/3.27 IF(mark(X1:S),X2:S,X3:S) -> IF(X1:S,X2:S,X3:S) 3.17/3.27 IF(ok(X1:S),ok(X2:S),ok(X3:S)) -> IF(X1:S,X2:S,X3:S) 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Projection: 3.17/3.27 pi(IF) = 1 3.17/3.27 3.17/3.27 Problem 1.3: 3.17/3.27 3.17/3.27 SCC Processor: 3.17/3.27 -> Pairs: 3.17/3.27 Empty 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Strongly Connected Components: 3.17/3.27 There is no strongly connected component 3.17/3.27 3.17/3.27 The problem is finite. 3.17/3.27 3.17/3.27 Problem 1.4: 3.17/3.27 3.17/3.27 Subterm Processor: 3.17/3.27 -> Pairs: 3.17/3.27 GEQ(ok(X1:S),ok(X2:S)) -> GEQ(X1:S,X2:S) 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Projection: 3.17/3.27 pi(GEQ) = 1 3.17/3.27 3.17/3.27 Problem 1.4: 3.17/3.27 3.17/3.27 SCC Processor: 3.17/3.27 -> Pairs: 3.17/3.27 Empty 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Strongly Connected Components: 3.17/3.27 There is no strongly connected component 3.17/3.27 3.17/3.27 The problem is finite. 3.17/3.27 3.17/3.27 Problem 1.5: 3.17/3.27 3.17/3.27 Subterm Processor: 3.17/3.27 -> Pairs: 3.17/3.27 DIV(mark(X1:S),X2:S) -> DIV(X1:S,X2:S) 3.17/3.27 DIV(ok(X1:S),ok(X2:S)) -> DIV(X1:S,X2:S) 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Projection: 3.17/3.27 pi(DIV) = 1 3.17/3.27 3.17/3.27 Problem 1.5: 3.17/3.27 3.17/3.27 SCC Processor: 3.17/3.27 -> Pairs: 3.17/3.27 Empty 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Strongly Connected Components: 3.17/3.27 There is no strongly connected component 3.17/3.27 3.17/3.27 The problem is finite. 3.17/3.27 3.17/3.27 Problem 1.6: 3.17/3.27 3.17/3.27 Subterm Processor: 3.17/3.27 -> Pairs: 3.17/3.27 PROPER(div(X1:S,X2:S)) -> PROPER(X1:S) 3.17/3.27 PROPER(div(X1:S,X2:S)) -> PROPER(X2:S) 3.17/3.27 PROPER(geq(X1:S,X2:S)) -> PROPER(X1:S) 3.17/3.27 PROPER(geq(X1:S,X2:S)) -> PROPER(X2:S) 3.17/3.27 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X1:S) 3.17/3.27 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X2:S) 3.17/3.27 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X3:S) 3.17/3.27 PROPER(minus(X1:S,X2:S)) -> PROPER(X1:S) 3.17/3.27 PROPER(minus(X1:S,X2:S)) -> PROPER(X2:S) 3.17/3.27 PROPER(s(X:S)) -> PROPER(X:S) 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Projection: 3.17/3.27 pi(PROPER) = 1 3.17/3.27 3.17/3.27 Problem 1.6: 3.17/3.27 3.17/3.27 SCC Processor: 3.17/3.27 -> Pairs: 3.17/3.27 Empty 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Strongly Connected Components: 3.17/3.27 There is no strongly connected component 3.17/3.27 3.17/3.27 The problem is finite. 3.17/3.27 3.17/3.27 Problem 1.7: 3.17/3.27 3.17/3.27 Subterm Processor: 3.17/3.27 -> Pairs: 3.17/3.27 ACTIVE(div(X1:S,X2:S)) -> ACTIVE(X1:S) 3.17/3.27 ACTIVE(if(X1:S,X2:S,X3:S)) -> ACTIVE(X1:S) 3.17/3.27 ACTIVE(s(X:S)) -> ACTIVE(X:S) 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Projection: 3.17/3.27 pi(ACTIVE) = 1 3.17/3.27 3.17/3.27 Problem 1.7: 3.17/3.27 3.17/3.27 SCC Processor: 3.17/3.27 -> Pairs: 3.17/3.27 Empty 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Strongly Connected Components: 3.17/3.27 There is no strongly connected component 3.17/3.27 3.17/3.27 The problem is finite. 3.17/3.27 3.17/3.27 Problem 1.8: 3.17/3.27 3.17/3.27 Reduction Pairs Processor: 3.17/3.27 -> Pairs: 3.17/3.27 TOP(mark(X:S)) -> TOP(proper(X:S)) 3.17/3.27 TOP(ok(X:S)) -> TOP(active(X:S)) 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 -> Usable rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 ->Interpretation type: 3.17/3.27 Linear 3.17/3.27 ->Coefficients: 3.17/3.27 All rationals 3.17/3.27 ->Dimension: 3.17/3.27 1 3.17/3.27 ->Bound: 3.17/3.27 4 3.17/3.27 ->Interpretation: 3.17/3.27 3.17/3.27 [active](X) = X 3.17/3.27 [div](X1,X2) = 3.X1 + X2 + 3 3.17/3.27 [geq](X1,X2) = 1/2.X1 + 4/3 3.17/3.27 [if](X1,X2,X3) = X1 + X2 + X3 + 4/3 3.17/3.27 [minus](X1,X2) = 1/3.X1 + 4/3 3.17/3.27 [proper](X) = X 3.17/3.27 [s](X) = X + 4 3.17/3.27 [top](X) = 0 3.17/3.27 [0] = 0 3.17/3.27 [fSNonEmpty] = 0 3.17/3.27 [false] = 0 3.17/3.27 [mark](X) = X + 4/3 3.17/3.27 [ok](X) = X 3.17/3.27 [true] = 0 3.17/3.27 [ACTIVE](X) = 0 3.17/3.27 [DIV](X1,X2) = 0 3.17/3.27 [GEQ](X1,X2) = 0 3.17/3.27 [IF](X1,X2,X3) = 0 3.17/3.27 [MINUS](X1,X2) = 0 3.17/3.27 [PROPER](X) = 0 3.17/3.27 [S](X) = 0 3.17/3.27 [TOP](X) = 1/3.X 3.17/3.27 3.17/3.27 Problem 1.8: 3.17/3.27 3.17/3.27 SCC Processor: 3.17/3.27 -> Pairs: 3.17/3.27 TOP(ok(X:S)) -> TOP(active(X:S)) 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Strongly Connected Components: 3.17/3.27 ->->Cycle: 3.17/3.27 ->->-> Pairs: 3.17/3.27 TOP(ok(X:S)) -> TOP(active(X:S)) 3.17/3.27 ->->-> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 3.17/3.27 Problem 1.8: 3.17/3.27 3.17/3.27 Reduction Pairs Processor: 3.17/3.27 -> Pairs: 3.17/3.27 TOP(ok(X:S)) -> TOP(active(X:S)) 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 -> Usable rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 ->Interpretation type: 3.17/3.27 Linear 3.17/3.27 ->Coefficients: 3.17/3.27 Natural Numbers 3.17/3.27 ->Dimension: 3.17/3.27 1 3.17/3.27 ->Bound: 3.17/3.27 2 3.17/3.27 ->Interpretation: 3.17/3.27 3.17/3.27 [active](X) = 1 3.17/3.27 [div](X1,X2) = X1 3.17/3.27 [geq](X1,X2) = 2.X1 3.17/3.27 [if](X1,X2,X3) = X1 3.17/3.27 [minus](X1,X2) = 2.X1 + 2.X2 3.17/3.27 [proper](X) = 0 3.17/3.27 [s](X) = X 3.17/3.27 [top](X) = 0 3.17/3.27 [0] = 2 3.17/3.27 [fSNonEmpty] = 0 3.17/3.27 [false] = 2 3.17/3.27 [mark](X) = 1 3.17/3.27 [ok](X) = 2 3.17/3.27 [true] = 1 3.17/3.27 [ACTIVE](X) = 0 3.17/3.27 [DIV](X1,X2) = 0 3.17/3.27 [GEQ](X1,X2) = 0 3.17/3.27 [IF](X1,X2,X3) = 0 3.17/3.27 [MINUS](X1,X2) = 0 3.17/3.27 [PROPER](X) = 0 3.17/3.27 [S](X) = 0 3.17/3.27 [TOP](X) = 2.X 3.17/3.27 3.17/3.27 Problem 1.8: 3.17/3.27 3.17/3.27 SCC Processor: 3.17/3.27 -> Pairs: 3.17/3.27 Empty 3.17/3.27 -> Rules: 3.17/3.27 active(div(s(X:S),s(Y:S))) -> mark(if(geq(X:S,Y:S),s(div(minus(X:S,Y:S),s(Y:S))),0)) 3.17/3.27 active(div(0,s(Y:S))) -> mark(0) 3.17/3.27 active(div(X1:S,X2:S)) -> div(active(X1:S),X2:S) 3.17/3.27 active(geq(s(X:S),s(Y:S))) -> mark(geq(X:S,Y:S)) 3.17/3.27 active(geq(0,s(Y:S))) -> mark(ffalse) 3.17/3.27 active(geq(X:S,0)) -> mark(ttrue) 3.17/3.27 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 3.17/3.27 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 3.17/3.27 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 3.17/3.27 active(minus(s(X:S),s(Y:S))) -> mark(minus(X:S,Y:S)) 3.17/3.27 active(minus(0,Y:S)) -> mark(0) 3.17/3.27 active(s(X:S)) -> s(active(X:S)) 3.17/3.27 div(mark(X1:S),X2:S) -> mark(div(X1:S,X2:S)) 3.17/3.27 div(ok(X1:S),ok(X2:S)) -> ok(div(X1:S,X2:S)) 3.17/3.27 geq(ok(X1:S),ok(X2:S)) -> ok(geq(X1:S,X2:S)) 3.17/3.27 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 3.17/3.27 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 3.17/3.27 minus(ok(X1:S),ok(X2:S)) -> ok(minus(X1:S,X2:S)) 3.17/3.27 proper(div(X1:S,X2:S)) -> div(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(geq(X1:S,X2:S)) -> geq(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 3.17/3.27 proper(minus(X1:S,X2:S)) -> minus(proper(X1:S),proper(X2:S)) 3.17/3.27 proper(s(X:S)) -> s(proper(X:S)) 3.17/3.27 proper(0) -> ok(0) 3.17/3.27 proper(ffalse) -> ok(ffalse) 3.17/3.27 proper(ttrue) -> ok(ttrue) 3.17/3.27 s(mark(X:S)) -> mark(s(X:S)) 3.17/3.27 s(ok(X:S)) -> ok(s(X:S)) 3.17/3.27 top(mark(X:S)) -> top(proper(X:S)) 3.17/3.27 top(ok(X:S)) -> top(active(X:S)) 3.17/3.27 ->Strongly Connected Components: 3.17/3.27 There is no strongly connected component 3.17/3.27 3.17/3.27 The problem is finite. 3.17/3.27 EOF