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