0.57/0.77 YES 0.57/0.77 0.57/0.77 Problem 1: 0.57/0.77 0.57/0.77 (VAR v_NonEmpty:S X:S X1:S X2:S) 0.57/0.77 (RULES 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ) 0.57/0.77 (STRATEGY INNERMOST) 0.57/0.77 0.57/0.77 Problem 1: 0.57/0.77 0.57/0.77 Dependency Pairs Processor: 0.57/0.77 -> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 ACTIVE(f(0)) -> MARK(cons(0,f(s(0)))) 0.57/0.77 ACTIVE(p(s(X:S))) -> MARK(X:S) 0.57/0.77 CONS(active(X1:S),X2:S) -> CONS(X1:S,X2:S) 0.57/0.77 CONS(mark(X1:S),X2:S) -> CONS(X1:S,X2:S) 0.57/0.77 CONS(X1:S,active(X2:S)) -> CONS(X1:S,X2:S) 0.57/0.77 CONS(X1:S,mark(X2:S)) -> CONS(X1:S,X2:S) 0.57/0.77 F(active(X:S)) -> F(X:S) 0.57/0.77 F(mark(X:S)) -> F(X:S) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> ACTIVE(cons(mark(X1:S),X2:S)) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> CONS(mark(X1:S),X2:S) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> MARK(X1:S) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(f(X:S)) -> F(mark(X:S)) 0.57/0.77 MARK(f(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> P(mark(X:S)) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> S(mark(X:S)) 0.57/0.77 P(active(X:S)) -> P(X:S) 0.57/0.77 P(mark(X:S)) -> P(X:S) 0.57/0.77 S(active(X:S)) -> S(X:S) 0.57/0.77 S(mark(X:S)) -> S(X:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 0.57/0.77 Problem 1: 0.57/0.77 0.57/0.77 SCC Processor: 0.57/0.77 -> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 ACTIVE(f(0)) -> MARK(cons(0,f(s(0)))) 0.57/0.77 ACTIVE(p(s(X:S))) -> MARK(X:S) 0.57/0.77 CONS(active(X1:S),X2:S) -> CONS(X1:S,X2:S) 0.57/0.77 CONS(mark(X1:S),X2:S) -> CONS(X1:S,X2:S) 0.57/0.77 CONS(X1:S,active(X2:S)) -> CONS(X1:S,X2:S) 0.57/0.77 CONS(X1:S,mark(X2:S)) -> CONS(X1:S,X2:S) 0.57/0.77 F(active(X:S)) -> F(X:S) 0.57/0.77 F(mark(X:S)) -> F(X:S) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> ACTIVE(cons(mark(X1:S),X2:S)) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> CONS(mark(X1:S),X2:S) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> MARK(X1:S) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(f(X:S)) -> F(mark(X:S)) 0.57/0.77 MARK(f(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> P(mark(X:S)) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> S(mark(X:S)) 0.57/0.77 P(active(X:S)) -> P(X:S) 0.57/0.77 P(mark(X:S)) -> P(X:S) 0.57/0.77 S(active(X:S)) -> S(X:S) 0.57/0.77 S(mark(X:S)) -> S(X:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Strongly Connected Components: 0.57/0.77 ->->Cycle: 0.57/0.77 ->->-> Pairs: 0.57/0.77 S(active(X:S)) -> S(X:S) 0.57/0.77 S(mark(X:S)) -> S(X:S) 0.57/0.77 ->->-> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->->Cycle: 0.57/0.77 ->->-> Pairs: 0.57/0.77 P(active(X:S)) -> P(X:S) 0.57/0.77 P(mark(X:S)) -> P(X:S) 0.57/0.77 ->->-> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->->Cycle: 0.57/0.77 ->->-> Pairs: 0.57/0.77 F(active(X:S)) -> F(X:S) 0.57/0.77 F(mark(X:S)) -> F(X:S) 0.57/0.77 ->->-> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->->Cycle: 0.57/0.77 ->->-> Pairs: 0.57/0.77 CONS(active(X1:S),X2:S) -> CONS(X1:S,X2:S) 0.57/0.77 CONS(mark(X1:S),X2:S) -> CONS(X1:S,X2:S) 0.57/0.77 CONS(X1:S,active(X2:S)) -> CONS(X1:S,X2:S) 0.57/0.77 CONS(X1:S,mark(X2:S)) -> CONS(X1:S,X2:S) 0.57/0.77 ->->-> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->->Cycle: 0.57/0.77 ->->-> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 ACTIVE(f(0)) -> MARK(cons(0,f(s(0)))) 0.57/0.77 ACTIVE(p(s(X:S))) -> MARK(X:S) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> ACTIVE(cons(mark(X1:S),X2:S)) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> MARK(X1:S) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(f(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 ->->-> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 0.57/0.77 0.57/0.77 The problem is decomposed in 5 subproblems. 0.57/0.77 0.57/0.77 Problem 1.1: 0.57/0.77 0.57/0.77 Subterm Processor: 0.57/0.77 -> Pairs: 0.57/0.77 S(active(X:S)) -> S(X:S) 0.57/0.77 S(mark(X:S)) -> S(X:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Projection: 0.57/0.77 pi(S) = 1 0.57/0.77 0.57/0.77 Problem 1.1: 0.57/0.77 0.57/0.77 SCC Processor: 0.57/0.77 -> Pairs: 0.57/0.77 Empty 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Strongly Connected Components: 0.57/0.77 There is no strongly connected component 0.57/0.77 0.57/0.77 The problem is finite. 0.57/0.77 0.57/0.77 Problem 1.2: 0.57/0.77 0.57/0.77 Subterm Processor: 0.57/0.77 -> Pairs: 0.57/0.77 P(active(X:S)) -> P(X:S) 0.57/0.77 P(mark(X:S)) -> P(X:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Projection: 0.57/0.77 pi(P) = 1 0.57/0.77 0.57/0.77 Problem 1.2: 0.57/0.77 0.57/0.77 SCC Processor: 0.57/0.77 -> Pairs: 0.57/0.77 Empty 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Strongly Connected Components: 0.57/0.77 There is no strongly connected component 0.57/0.77 0.57/0.77 The problem is finite. 0.57/0.77 0.57/0.77 Problem 1.3: 0.57/0.77 0.57/0.77 Subterm Processor: 0.57/0.77 -> Pairs: 0.57/0.77 F(active(X:S)) -> F(X:S) 0.57/0.77 F(mark(X:S)) -> F(X:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Projection: 0.57/0.77 pi(F) = 1 0.57/0.77 0.57/0.77 Problem 1.3: 0.57/0.77 0.57/0.77 SCC Processor: 0.57/0.77 -> Pairs: 0.57/0.77 Empty 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Strongly Connected Components: 0.57/0.77 There is no strongly connected component 0.57/0.77 0.57/0.77 The problem is finite. 0.57/0.77 0.57/0.77 Problem 1.4: 0.57/0.77 0.57/0.77 Subterm Processor: 0.57/0.77 -> Pairs: 0.57/0.77 CONS(active(X1:S),X2:S) -> CONS(X1:S,X2:S) 0.57/0.77 CONS(mark(X1:S),X2:S) -> CONS(X1:S,X2:S) 0.57/0.77 CONS(X1:S,active(X2:S)) -> CONS(X1:S,X2:S) 0.57/0.77 CONS(X1:S,mark(X2:S)) -> CONS(X1:S,X2:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Projection: 0.57/0.77 pi(CONS) = 1 0.57/0.77 0.57/0.77 Problem 1.4: 0.57/0.77 0.57/0.77 SCC Processor: 0.57/0.77 -> Pairs: 0.57/0.77 CONS(X1:S,active(X2:S)) -> CONS(X1:S,X2:S) 0.57/0.77 CONS(X1:S,mark(X2:S)) -> CONS(X1:S,X2:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Strongly Connected Components: 0.57/0.77 ->->Cycle: 0.57/0.77 ->->-> Pairs: 0.57/0.77 CONS(X1:S,active(X2:S)) -> CONS(X1:S,X2:S) 0.57/0.77 CONS(X1:S,mark(X2:S)) -> CONS(X1:S,X2:S) 0.57/0.77 ->->-> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 0.57/0.77 Problem 1.4: 0.57/0.77 0.57/0.77 Subterm Processor: 0.57/0.77 -> Pairs: 0.57/0.77 CONS(X1:S,active(X2:S)) -> CONS(X1:S,X2:S) 0.57/0.77 CONS(X1:S,mark(X2:S)) -> CONS(X1:S,X2:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Projection: 0.57/0.77 pi(CONS) = 2 0.57/0.77 0.57/0.77 Problem 1.4: 0.57/0.77 0.57/0.77 SCC Processor: 0.57/0.77 -> Pairs: 0.57/0.77 Empty 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Strongly Connected Components: 0.57/0.77 There is no strongly connected component 0.57/0.77 0.57/0.77 The problem is finite. 0.57/0.77 0.57/0.77 Problem 1.5: 0.57/0.77 0.57/0.77 Reduction Pairs Processor: 0.57/0.77 -> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 ACTIVE(f(0)) -> MARK(cons(0,f(s(0)))) 0.57/0.77 ACTIVE(p(s(X:S))) -> MARK(X:S) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> ACTIVE(cons(mark(X1:S),X2:S)) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> MARK(X1:S) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(f(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 -> Usable rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Interpretation type: 0.57/0.77 Linear 0.57/0.77 ->Coefficients: 0.57/0.77 Natural Numbers 0.57/0.77 ->Dimension: 0.57/0.77 1 0.57/0.77 ->Bound: 0.57/0.77 2 0.57/0.77 ->Interpretation: 0.57/0.77 0.57/0.77 [active](X) = X 0.57/0.77 [cons](X1,X2) = X1 + 1 0.57/0.77 [f](X) = 2.X + 2 0.57/0.77 [mark](X) = X 0.57/0.77 [p](X) = X 0.57/0.77 [s](X) = X + 2 0.57/0.77 [0] = 2 0.57/0.77 [fSNonEmpty] = 0 0.57/0.77 [ACTIVE](X) = 2.X + 2 0.57/0.77 [CONS](X1,X2) = 0 0.57/0.77 [F](X) = 0 0.57/0.77 [MARK](X) = 2.X + 2 0.57/0.77 [P](X) = 0 0.57/0.77 [S](X) = 0 0.57/0.77 0.57/0.77 Problem 1.5: 0.57/0.77 0.57/0.77 SCC Processor: 0.57/0.77 -> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 ACTIVE(p(s(X:S))) -> MARK(X:S) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> ACTIVE(cons(mark(X1:S),X2:S)) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> MARK(X1:S) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(f(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Strongly Connected Components: 0.57/0.77 ->->Cycle: 0.57/0.77 ->->-> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 ACTIVE(p(s(X:S))) -> MARK(X:S) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> ACTIVE(cons(mark(X1:S),X2:S)) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> MARK(X1:S) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(f(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 ->->-> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 0.57/0.77 Problem 1.5: 0.57/0.77 0.57/0.77 Reduction Pairs Processor: 0.57/0.77 -> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 ACTIVE(p(s(X:S))) -> MARK(X:S) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> ACTIVE(cons(mark(X1:S),X2:S)) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> MARK(X1:S) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(f(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 -> Usable rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Interpretation type: 0.57/0.77 Linear 0.57/0.77 ->Coefficients: 0.57/0.77 Natural Numbers 0.57/0.77 ->Dimension: 0.57/0.77 1 0.57/0.77 ->Bound: 0.57/0.77 2 0.57/0.77 ->Interpretation: 0.57/0.77 0.57/0.77 [active](X) = X 0.57/0.77 [cons](X1,X2) = 2.X1 + 1 0.57/0.77 [f](X) = 2.X + 2 0.57/0.77 [mark](X) = X 0.57/0.77 [p](X) = X 0.57/0.77 [s](X) = 2.X + 2 0.57/0.77 [0] = 0 0.57/0.77 [fSNonEmpty] = 0 0.57/0.77 [ACTIVE](X) = X + 2 0.57/0.77 [CONS](X1,X2) = 0 0.57/0.77 [F](X) = 0 0.57/0.77 [MARK](X) = X + 2 0.57/0.77 [P](X) = 0 0.57/0.77 [S](X) = 0 0.57/0.77 0.57/0.77 Problem 1.5: 0.57/0.77 0.57/0.77 SCC Processor: 0.57/0.77 -> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> ACTIVE(cons(mark(X1:S),X2:S)) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> MARK(X1:S) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(f(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Strongly Connected Components: 0.57/0.77 ->->Cycle: 0.57/0.77 ->->-> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> ACTIVE(cons(mark(X1:S),X2:S)) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> MARK(X1:S) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(f(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 ->->-> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 0.57/0.77 Problem 1.5: 0.57/0.77 0.57/0.77 Reduction Pairs Processor: 0.57/0.77 -> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> ACTIVE(cons(mark(X1:S),X2:S)) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> MARK(X1:S) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(f(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 -> Usable rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Interpretation type: 0.57/0.77 Linear 0.57/0.77 ->Coefficients: 0.57/0.77 Natural Numbers 0.57/0.77 ->Dimension: 0.57/0.77 1 0.57/0.77 ->Bound: 0.57/0.77 2 0.57/0.77 ->Interpretation: 0.57/0.77 0.57/0.77 [active](X) = 2 0.57/0.77 [cons](X1,X2) = 0 0.57/0.77 [f](X) = 1 0.57/0.77 [mark](X) = 2 0.57/0.77 [p](X) = 0 0.57/0.77 [s](X) = 1 0.57/0.77 [0] = 0 0.57/0.77 [fSNonEmpty] = 0 0.57/0.77 [ACTIVE](X) = 2.X 0.57/0.77 [CONS](X1,X2) = 0 0.57/0.77 [F](X) = 0 0.57/0.77 [MARK](X) = 2 0.57/0.77 [P](X) = 0 0.57/0.77 [S](X) = 0 0.57/0.77 0.57/0.77 Problem 1.5: 0.57/0.77 0.57/0.77 SCC Processor: 0.57/0.77 -> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> MARK(X1:S) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(f(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Strongly Connected Components: 0.57/0.77 ->->Cycle: 0.57/0.77 ->->-> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> MARK(X1:S) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(f(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 ->->-> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 0.57/0.77 Problem 1.5: 0.57/0.77 0.57/0.77 Reduction Pairs Processor: 0.57/0.77 -> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 MARK(cons(X1:S,X2:S)) -> MARK(X1:S) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(f(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 -> Usable rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Interpretation type: 0.57/0.77 Linear 0.57/0.77 ->Coefficients: 0.57/0.77 Natural Numbers 0.57/0.77 ->Dimension: 0.57/0.77 1 0.57/0.77 ->Bound: 0.57/0.77 2 0.57/0.77 ->Interpretation: 0.57/0.77 0.57/0.77 [active](X) = X 0.57/0.77 [cons](X1,X2) = X1 + 2 0.57/0.77 [f](X) = 2.X + 2 0.57/0.77 [mark](X) = X 0.57/0.77 [p](X) = X 0.57/0.77 [s](X) = 2.X + 2 0.57/0.77 [0] = 2 0.57/0.77 [fSNonEmpty] = 0 0.57/0.77 [ACTIVE](X) = X + 1 0.57/0.77 [CONS](X1,X2) = 0 0.57/0.77 [F](X) = 0 0.57/0.77 [MARK](X) = X + 1 0.57/0.77 [P](X) = 0 0.57/0.77 [S](X) = 0 0.57/0.77 0.57/0.77 Problem 1.5: 0.57/0.77 0.57/0.77 SCC Processor: 0.57/0.77 -> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(f(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Strongly Connected Components: 0.57/0.77 ->->Cycle: 0.57/0.77 ->->-> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(f(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 ->->-> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 0.57/0.77 Problem 1.5: 0.57/0.77 0.57/0.77 Reduction Pairs Processor: 0.57/0.77 -> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(f(X:S)) -> MARK(X:S) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 -> Usable rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Interpretation type: 0.57/0.77 Linear 0.57/0.77 ->Coefficients: 0.57/0.77 Natural Numbers 0.57/0.77 ->Dimension: 0.57/0.77 1 0.57/0.77 ->Bound: 0.57/0.77 2 0.57/0.77 ->Interpretation: 0.57/0.77 0.57/0.77 [active](X) = X 0.57/0.77 [cons](X1,X2) = X1 + 1 0.57/0.77 [f](X) = X + 1 0.57/0.77 [mark](X) = X 0.57/0.77 [p](X) = X 0.57/0.77 [s](X) = 2.X + 2 0.57/0.77 [0] = 2 0.57/0.77 [fSNonEmpty] = 0 0.57/0.77 [ACTIVE](X) = 2.X + 2 0.57/0.77 [CONS](X1,X2) = 0 0.57/0.77 [F](X) = 0 0.57/0.77 [MARK](X) = 2.X + 2 0.57/0.77 [P](X) = 0 0.57/0.77 [S](X) = 0 0.57/0.77 0.57/0.77 Problem 1.5: 0.57/0.77 0.57/0.77 SCC Processor: 0.57/0.77 -> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> ACTIVE(p(mark(X:S))) 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> ACTIVE(s(mark(X:S))) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Strongly Connected Components: 0.57/0.77 ->->Cycle: 0.57/0.77 ->->-> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 ->->-> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->->Cycle: 0.57/0.77 ->->-> Pairs: 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 ->->-> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 0.57/0.77 0.57/0.77 The problem is decomposed in 2 subproblems. 0.57/0.77 0.57/0.77 Problem 1.5.1: 0.57/0.77 0.57/0.77 Reduction Pairs Processor: 0.57/0.77 -> Pairs: 0.57/0.77 ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 -> Usable rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Interpretation type: 0.57/0.77 Linear 0.57/0.77 ->Coefficients: 0.57/0.77 All rationals 0.57/0.77 ->Dimension: 0.57/0.77 1 0.57/0.77 ->Bound: 0.57/0.77 2 0.57/0.77 ->Interpretation: 0.57/0.77 0.57/0.77 [active](X) = X 0.57/0.77 [cons](X1,X2) = 1/2.X2 0.57/0.77 [f](X) = 1/2.X + 1 0.57/0.77 [mark](X) = X 0.57/0.77 [p](X) = 1/2.X + 1/2 0.57/0.77 [s](X) = 2.X + 1/2 0.57/0.77 [0] = 1/2 0.57/0.77 [fSNonEmpty] = 0 0.57/0.77 [ACTIVE](X) = X + 1/2 0.57/0.77 [CONS](X1,X2) = 0 0.57/0.77 [F](X) = 0 0.57/0.77 [MARK](X) = X + 1/2 0.57/0.77 [P](X) = 0 0.57/0.77 [S](X) = 0 0.57/0.77 0.57/0.77 Problem 1.5.1: 0.57/0.77 0.57/0.77 SCC Processor: 0.57/0.77 -> Pairs: 0.57/0.77 MARK(f(X:S)) -> ACTIVE(f(mark(X:S))) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Strongly Connected Components: 0.57/0.77 There is no strongly connected component 0.57/0.77 0.57/0.77 The problem is finite. 0.57/0.77 0.57/0.77 Problem 1.5.2: 0.57/0.77 0.57/0.77 Subterm Processor: 0.57/0.77 -> Pairs: 0.57/0.77 MARK(p(X:S)) -> MARK(X:S) 0.57/0.77 MARK(s(X:S)) -> MARK(X:S) 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Projection: 0.57/0.77 pi(MARK) = 1 0.57/0.77 0.57/0.77 Problem 1.5.2: 0.57/0.77 0.57/0.77 SCC Processor: 0.57/0.77 -> Pairs: 0.57/0.77 Empty 0.57/0.77 -> Rules: 0.57/0.77 active(f(s(0))) -> mark(f(p(s(0)))) 0.57/0.77 active(f(0)) -> mark(cons(0,f(s(0)))) 0.57/0.77 active(p(s(X:S))) -> mark(X:S) 0.57/0.77 cons(active(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(mark(X1:S),X2:S) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,active(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 cons(X1:S,mark(X2:S)) -> cons(X1:S,X2:S) 0.57/0.77 f(active(X:S)) -> f(X:S) 0.57/0.77 f(mark(X:S)) -> f(X:S) 0.57/0.77 mark(cons(X1:S,X2:S)) -> active(cons(mark(X1:S),X2:S)) 0.57/0.77 mark(f(X:S)) -> active(f(mark(X:S))) 0.57/0.77 mark(p(X:S)) -> active(p(mark(X:S))) 0.57/0.77 mark(s(X:S)) -> active(s(mark(X:S))) 0.57/0.77 mark(0) -> active(0) 0.57/0.77 p(active(X:S)) -> p(X:S) 0.57/0.77 p(mark(X:S)) -> p(X:S) 0.57/0.77 s(active(X:S)) -> s(X:S) 0.57/0.77 s(mark(X:S)) -> s(X:S) 0.57/0.77 ->Strongly Connected Components: 0.57/0.77 There is no strongly connected component 0.57/0.77 0.57/0.77 The problem is finite. 0.57/0.77 EOF