2.80/2.89 YES 2.80/2.89 2.80/2.89 Problem 1: 2.80/2.89 2.80/2.89 (VAR v_NonEmpty:S X:S X1:S X2:S X3:S Y:S) 2.80/2.89 (RULES 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ) 2.80/2.89 (STRATEGY INNERMOST) 2.80/2.89 2.80/2.89 Problem 1: 2.80/2.89 2.80/2.89 Dependency Pairs Processor: 2.80/2.89 -> Pairs: 2.80/2.89 ACTIVE(f(X:S)) -> ACTIVE(X:S) 2.80/2.89 ACTIVE(f(X:S)) -> F(active(X:S)) 2.80/2.89 ACTIVE(f(X:S)) -> IF(X:S,c,f(ttrue)) 2.80/2.89 ACTIVE(if(X1:S,X2:S,X3:S)) -> ACTIVE(X1:S) 2.80/2.89 ACTIVE(if(X1:S,X2:S,X3:S)) -> ACTIVE(X2:S) 2.80/2.89 ACTIVE(if(X1:S,X2:S,X3:S)) -> IF(active(X1:S),X2:S,X3:S) 2.80/2.89 ACTIVE(if(X1:S,X2:S,X3:S)) -> IF(X1:S,active(X2:S),X3:S) 2.80/2.89 F(mark(X:S)) -> F(X:S) 2.80/2.89 F(ok(X:S)) -> F(X:S) 2.80/2.89 IF(mark(X1:S),X2:S,X3:S) -> IF(X1:S,X2:S,X3:S) 2.80/2.89 IF(ok(X1:S),ok(X2:S),ok(X3:S)) -> IF(X1:S,X2:S,X3:S) 2.80/2.89 IF(X1:S,mark(X2:S),X3:S) -> IF(X1:S,X2:S,X3:S) 2.80/2.89 PROPER(f(X:S)) -> F(proper(X:S)) 2.80/2.89 PROPER(f(X:S)) -> PROPER(X:S) 2.80/2.89 PROPER(if(X1:S,X2:S,X3:S)) -> IF(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X1:S) 2.80/2.89 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X2:S) 2.80/2.89 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X3:S) 2.80/2.89 TOP(mark(X:S)) -> PROPER(X:S) 2.80/2.89 TOP(mark(X:S)) -> TOP(proper(X:S)) 2.80/2.89 TOP(ok(X:S)) -> ACTIVE(X:S) 2.80/2.89 TOP(ok(X:S)) -> TOP(active(X:S)) 2.80/2.89 -> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 2.80/2.89 Problem 1: 2.80/2.89 2.80/2.89 SCC Processor: 2.80/2.89 -> Pairs: 2.80/2.89 ACTIVE(f(X:S)) -> ACTIVE(X:S) 2.80/2.89 ACTIVE(f(X:S)) -> F(active(X:S)) 2.80/2.89 ACTIVE(f(X:S)) -> IF(X:S,c,f(ttrue)) 2.80/2.89 ACTIVE(if(X1:S,X2:S,X3:S)) -> ACTIVE(X1:S) 2.80/2.89 ACTIVE(if(X1:S,X2:S,X3:S)) -> ACTIVE(X2:S) 2.80/2.89 ACTIVE(if(X1:S,X2:S,X3:S)) -> IF(active(X1:S),X2:S,X3:S) 2.80/2.89 ACTIVE(if(X1:S,X2:S,X3:S)) -> IF(X1:S,active(X2:S),X3:S) 2.80/2.89 F(mark(X:S)) -> F(X:S) 2.80/2.89 F(ok(X:S)) -> F(X:S) 2.80/2.89 IF(mark(X1:S),X2:S,X3:S) -> IF(X1:S,X2:S,X3:S) 2.80/2.89 IF(ok(X1:S),ok(X2:S),ok(X3:S)) -> IF(X1:S,X2:S,X3:S) 2.80/2.89 IF(X1:S,mark(X2:S),X3:S) -> IF(X1:S,X2:S,X3:S) 2.80/2.89 PROPER(f(X:S)) -> F(proper(X:S)) 2.80/2.89 PROPER(f(X:S)) -> PROPER(X:S) 2.80/2.89 PROPER(if(X1:S,X2:S,X3:S)) -> IF(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X1:S) 2.80/2.89 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X2:S) 2.80/2.89 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X3:S) 2.80/2.89 TOP(mark(X:S)) -> PROPER(X:S) 2.80/2.89 TOP(mark(X:S)) -> TOP(proper(X:S)) 2.80/2.89 TOP(ok(X:S)) -> ACTIVE(X:S) 2.80/2.89 TOP(ok(X:S)) -> TOP(active(X:S)) 2.80/2.89 -> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->Strongly Connected Components: 2.80/2.89 ->->Cycle: 2.80/2.89 ->->-> Pairs: 2.80/2.89 IF(mark(X1:S),X2:S,X3:S) -> IF(X1:S,X2:S,X3:S) 2.80/2.89 IF(ok(X1:S),ok(X2:S),ok(X3:S)) -> IF(X1:S,X2:S,X3:S) 2.80/2.89 IF(X1:S,mark(X2:S),X3:S) -> IF(X1:S,X2:S,X3:S) 2.80/2.89 ->->-> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->->Cycle: 2.80/2.89 ->->-> Pairs: 2.80/2.89 F(mark(X:S)) -> F(X:S) 2.80/2.89 F(ok(X:S)) -> F(X:S) 2.80/2.89 ->->-> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->->Cycle: 2.80/2.89 ->->-> Pairs: 2.80/2.89 PROPER(f(X:S)) -> PROPER(X:S) 2.80/2.89 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X1:S) 2.80/2.89 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X2:S) 2.80/2.89 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X3:S) 2.80/2.89 ->->-> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->->Cycle: 2.80/2.89 ->->-> Pairs: 2.80/2.89 ACTIVE(f(X:S)) -> ACTIVE(X:S) 2.80/2.89 ACTIVE(if(X1:S,X2:S,X3:S)) -> ACTIVE(X1:S) 2.80/2.89 ACTIVE(if(X1:S,X2:S,X3:S)) -> ACTIVE(X2:S) 2.80/2.89 ->->-> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->->Cycle: 2.80/2.89 ->->-> Pairs: 2.80/2.89 TOP(mark(X:S)) -> TOP(proper(X:S)) 2.80/2.89 TOP(ok(X:S)) -> TOP(active(X:S)) 2.80/2.89 ->->-> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 2.80/2.89 2.80/2.89 The problem is decomposed in 5 subproblems. 2.80/2.89 2.80/2.89 Problem 1.1: 2.80/2.89 2.80/2.89 Subterm Processor: 2.80/2.89 -> Pairs: 2.80/2.89 IF(mark(X1:S),X2:S,X3:S) -> IF(X1:S,X2:S,X3:S) 2.80/2.89 IF(ok(X1:S),ok(X2:S),ok(X3:S)) -> IF(X1:S,X2:S,X3:S) 2.80/2.89 IF(X1:S,mark(X2:S),X3:S) -> IF(X1:S,X2:S,X3:S) 2.80/2.89 -> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->Projection: 2.80/2.89 pi(IF) = 1 2.80/2.89 2.80/2.89 Problem 1.1: 2.80/2.89 2.80/2.89 SCC Processor: 2.80/2.89 -> Pairs: 2.80/2.89 IF(X1:S,mark(X2:S),X3:S) -> IF(X1:S,X2:S,X3:S) 2.80/2.89 -> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->Strongly Connected Components: 2.80/2.89 ->->Cycle: 2.80/2.89 ->->-> Pairs: 2.80/2.89 IF(X1:S,mark(X2:S),X3:S) -> IF(X1:S,X2:S,X3:S) 2.80/2.89 ->->-> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 2.80/2.89 Problem 1.1: 2.80/2.89 2.80/2.89 Subterm Processor: 2.80/2.89 -> Pairs: 2.80/2.89 IF(X1:S,mark(X2:S),X3:S) -> IF(X1:S,X2:S,X3:S) 2.80/2.89 -> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->Projection: 2.80/2.89 pi(IF) = 2 2.80/2.89 2.80/2.89 Problem 1.1: 2.80/2.89 2.80/2.89 SCC Processor: 2.80/2.89 -> Pairs: 2.80/2.89 Empty 2.80/2.89 -> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->Strongly Connected Components: 2.80/2.89 There is no strongly connected component 2.80/2.89 2.80/2.89 The problem is finite. 2.80/2.89 2.80/2.89 Problem 1.2: 2.80/2.89 2.80/2.89 Subterm Processor: 2.80/2.89 -> Pairs: 2.80/2.89 F(mark(X:S)) -> F(X:S) 2.80/2.89 F(ok(X:S)) -> F(X:S) 2.80/2.89 -> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->Projection: 2.80/2.89 pi(F) = 1 2.80/2.89 2.80/2.89 Problem 1.2: 2.80/2.89 2.80/2.89 SCC Processor: 2.80/2.89 -> Pairs: 2.80/2.89 Empty 2.80/2.89 -> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->Strongly Connected Components: 2.80/2.89 There is no strongly connected component 2.80/2.89 2.80/2.89 The problem is finite. 2.80/2.89 2.80/2.89 Problem 1.3: 2.80/2.89 2.80/2.89 Subterm Processor: 2.80/2.89 -> Pairs: 2.80/2.89 PROPER(f(X:S)) -> PROPER(X:S) 2.80/2.89 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X1:S) 2.80/2.89 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X2:S) 2.80/2.89 PROPER(if(X1:S,X2:S,X3:S)) -> PROPER(X3:S) 2.80/2.89 -> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->Projection: 2.80/2.89 pi(PROPER) = 1 2.80/2.89 2.80/2.89 Problem 1.3: 2.80/2.89 2.80/2.89 SCC Processor: 2.80/2.89 -> Pairs: 2.80/2.89 Empty 2.80/2.89 -> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->Strongly Connected Components: 2.80/2.89 There is no strongly connected component 2.80/2.89 2.80/2.89 The problem is finite. 2.80/2.89 2.80/2.89 Problem 1.4: 2.80/2.89 2.80/2.89 Subterm Processor: 2.80/2.89 -> Pairs: 2.80/2.89 ACTIVE(f(X:S)) -> ACTIVE(X:S) 2.80/2.89 ACTIVE(if(X1:S,X2:S,X3:S)) -> ACTIVE(X1:S) 2.80/2.89 ACTIVE(if(X1:S,X2:S,X3:S)) -> ACTIVE(X2:S) 2.80/2.89 -> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->Projection: 2.80/2.89 pi(ACTIVE) = 1 2.80/2.89 2.80/2.89 Problem 1.4: 2.80/2.89 2.80/2.89 SCC Processor: 2.80/2.89 -> Pairs: 2.80/2.89 Empty 2.80/2.89 -> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->Strongly Connected Components: 2.80/2.89 There is no strongly connected component 2.80/2.89 2.80/2.89 The problem is finite. 2.80/2.89 2.80/2.89 Problem 1.5: 2.80/2.89 2.80/2.89 Reduction Pairs Processor: 2.80/2.89 -> Pairs: 2.80/2.89 TOP(mark(X:S)) -> TOP(proper(X:S)) 2.80/2.89 TOP(ok(X:S)) -> TOP(active(X:S)) 2.80/2.89 -> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 -> Usable rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 ->Interpretation type: 2.80/2.89 Simple mixed 2.80/2.89 ->Coefficients: 2.80/2.89 All rationals 2.80/2.89 ->Dimension: 2.80/2.89 1 2.80/2.89 ->Bound: 2.80/2.89 2 2.80/2.89 ->Interpretation: 2.80/2.89 2.80/2.89 [active](X) = X 2.80/2.89 [f](X) = 2.X + 1 2.80/2.89 [if](X1,X2,X3) = 1/2.X1.X3 + X1 + X2 2.80/2.89 [proper](X) = X 2.80/2.89 [top](X) = 0 2.80/2.89 [c] = 0 2.80/2.89 [fSNonEmpty] = 0 2.80/2.89 [false] = 2 2.80/2.89 [mark](X) = X + 1/2 2.80/2.89 [ok](X) = X 2.80/2.89 [true] = 1/2 2.80/2.89 [ACTIVE](X) = 0 2.80/2.89 [F](X) = 0 2.80/2.89 [IF](X1,X2,X3) = 0 2.80/2.89 [PROPER](X) = 0 2.80/2.89 [TOP](X) = 1/2.X 2.80/2.89 2.80/2.89 Problem 1.5: 2.80/2.89 2.80/2.89 SCC Processor: 2.80/2.89 -> Pairs: 2.80/2.89 TOP(ok(X:S)) -> TOP(active(X:S)) 2.80/2.89 -> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->Strongly Connected Components: 2.80/2.89 ->->Cycle: 2.80/2.89 ->->-> Pairs: 2.80/2.89 TOP(ok(X:S)) -> TOP(active(X:S)) 2.80/2.89 ->->-> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 2.80/2.89 Problem 1.5: 2.80/2.89 2.80/2.89 Reduction Pairs Processor: 2.80/2.89 -> Pairs: 2.80/2.89 TOP(ok(X:S)) -> TOP(active(X:S)) 2.80/2.89 -> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 -> Usable rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 ->Interpretation type: 2.80/2.89 Linear 2.80/2.89 ->Coefficients: 2.80/2.89 Natural Numbers 2.80/2.89 ->Dimension: 2.80/2.89 1 2.80/2.89 ->Bound: 2.80/2.89 2 2.80/2.89 ->Interpretation: 2.80/2.89 2.80/2.89 [active](X) = 2.X + 1 2.80/2.89 [f](X) = 2.X + 1 2.80/2.89 [if](X1,X2,X3) = 2.X1 + 2.X2 + X3 + 2 2.80/2.89 [proper](X) = 0 2.80/2.89 [top](X) = 0 2.80/2.89 [c] = 0 2.80/2.89 [fSNonEmpty] = 0 2.80/2.89 [false] = 0 2.80/2.89 [mark](X) = X 2.80/2.89 [ok](X) = 2.X + 2 2.80/2.89 [true] = 0 2.80/2.89 [ACTIVE](X) = 0 2.80/2.89 [F](X) = 0 2.80/2.89 [IF](X1,X2,X3) = 0 2.80/2.89 [PROPER](X) = 0 2.80/2.89 [TOP](X) = 2.X 2.80/2.89 2.80/2.89 Problem 1.5: 2.80/2.89 2.80/2.89 SCC Processor: 2.80/2.89 -> Pairs: 2.80/2.89 Empty 2.80/2.89 -> Rules: 2.80/2.89 active(f(X:S)) -> f(active(X:S)) 2.80/2.89 active(f(X:S)) -> mark(if(X:S,c,f(ttrue))) 2.80/2.89 active(if(ffalse,X:S,Y:S)) -> mark(Y:S) 2.80/2.89 active(if(ttrue,X:S,Y:S)) -> mark(X:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(active(X1:S),X2:S,X3:S) 2.80/2.89 active(if(X1:S,X2:S,X3:S)) -> if(X1:S,active(X2:S),X3:S) 2.80/2.89 f(mark(X:S)) -> mark(f(X:S)) 2.80/2.89 f(ok(X:S)) -> ok(f(X:S)) 2.80/2.89 if(mark(X1:S),X2:S,X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(ok(X1:S),ok(X2:S),ok(X3:S)) -> ok(if(X1:S,X2:S,X3:S)) 2.80/2.89 if(X1:S,mark(X2:S),X3:S) -> mark(if(X1:S,X2:S,X3:S)) 2.80/2.89 proper(f(X:S)) -> f(proper(X:S)) 2.80/2.89 proper(if(X1:S,X2:S,X3:S)) -> if(proper(X1:S),proper(X2:S),proper(X3:S)) 2.80/2.89 proper(c) -> ok(c) 2.80/2.89 proper(ffalse) -> ok(ffalse) 2.80/2.89 proper(ttrue) -> ok(ttrue) 2.80/2.89 top(mark(X:S)) -> top(proper(X:S)) 2.80/2.89 top(ok(X:S)) -> top(active(X:S)) 2.80/2.89 ->Strongly Connected Components: 2.80/2.89 There is no strongly connected component 2.80/2.89 2.80/2.89 The problem is finite. 2.80/2.89 EOF