9.67/9.80 YES 9.67/9.80 9.67/9.80 Problem 1: 9.67/9.80 9.67/9.80 (VAR v_NonEmpty:S X:S X1:S X2:S X3:S) 9.67/9.80 (RULES 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 ) 9.67/9.80 (STRATEGY INNERMOST) 9.67/9.80 9.67/9.80 Problem 1: 9.67/9.80 9.67/9.80 Dependency Pairs Processor: 9.67/9.80 -> Pairs: 9.67/9.80 ACTIVE(f(a,X:S,X:S)) -> F(X:S,b,b) 9.67/9.80 ACTIVE(f(a,X:S,X:S)) -> MARK(f(X:S,b,b)) 9.67/9.80 ACTIVE(b) -> MARK(a) 9.67/9.80 F(active(X1:S),X2:S,X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(mark(X1:S),X2:S,X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,active(X2:S),X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,mark(X2:S),X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,active(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,mark(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 MARK(f(X1:S,X2:S,X3:S)) -> ACTIVE(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 MARK(f(X1:S,X2:S,X3:S)) -> F(X1:S,mark(X2:S),X3:S) 9.67/9.80 MARK(f(X1:S,X2:S,X3:S)) -> MARK(X2:S) 9.67/9.80 MARK(b) -> ACTIVE(b) 9.67/9.80 -> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 9.67/9.80 Problem 1: 9.67/9.80 9.67/9.80 SCC Processor: 9.67/9.80 -> Pairs: 9.67/9.80 ACTIVE(f(a,X:S,X:S)) -> F(X:S,b,b) 9.67/9.80 ACTIVE(f(a,X:S,X:S)) -> MARK(f(X:S,b,b)) 9.67/9.80 ACTIVE(b) -> MARK(a) 9.67/9.80 F(active(X1:S),X2:S,X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(mark(X1:S),X2:S,X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,active(X2:S),X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,mark(X2:S),X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,active(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,mark(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 MARK(f(X1:S,X2:S,X3:S)) -> ACTIVE(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 MARK(f(X1:S,X2:S,X3:S)) -> F(X1:S,mark(X2:S),X3:S) 9.67/9.80 MARK(f(X1:S,X2:S,X3:S)) -> MARK(X2:S) 9.67/9.80 MARK(b) -> ACTIVE(b) 9.67/9.80 -> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 ->Strongly Connected Components: 9.67/9.80 ->->Cycle: 9.67/9.80 ->->-> Pairs: 9.67/9.80 F(active(X1:S),X2:S,X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(mark(X1:S),X2:S,X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,active(X2:S),X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,mark(X2:S),X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,active(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,mark(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 ->->-> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 ->->Cycle: 9.67/9.80 ->->-> Pairs: 9.67/9.80 ACTIVE(f(a,X:S,X:S)) -> MARK(f(X:S,b,b)) 9.67/9.80 MARK(f(X1:S,X2:S,X3:S)) -> ACTIVE(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 MARK(f(X1:S,X2:S,X3:S)) -> MARK(X2:S) 9.67/9.80 ->->-> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 9.67/9.80 9.67/9.80 The problem is decomposed in 2 subproblems. 9.67/9.80 9.67/9.80 Problem 1.1: 9.67/9.80 9.67/9.80 Subterm Processor: 9.67/9.80 -> Pairs: 9.67/9.80 F(active(X1:S),X2:S,X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(mark(X1:S),X2:S,X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,active(X2:S),X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,mark(X2:S),X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,active(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,mark(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 -> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 ->Projection: 9.67/9.80 pi(F) = 1 9.67/9.80 9.67/9.80 Problem 1.1: 9.67/9.80 9.67/9.80 SCC Processor: 9.67/9.80 -> Pairs: 9.67/9.80 F(X1:S,active(X2:S),X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,mark(X2:S),X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,active(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,mark(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 -> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 ->Strongly Connected Components: 9.67/9.80 ->->Cycle: 9.67/9.80 ->->-> Pairs: 9.67/9.80 F(X1:S,active(X2:S),X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,mark(X2:S),X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,active(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,mark(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 ->->-> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 9.67/9.80 Problem 1.1: 9.67/9.80 9.67/9.80 Subterm Processor: 9.67/9.80 -> Pairs: 9.67/9.80 F(X1:S,active(X2:S),X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,mark(X2:S),X3:S) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,active(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,mark(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 -> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 ->Projection: 9.67/9.80 pi(F) = 2 9.67/9.80 9.67/9.80 Problem 1.1: 9.67/9.80 9.67/9.80 SCC Processor: 9.67/9.80 -> Pairs: 9.67/9.80 F(X1:S,X2:S,active(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,mark(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 -> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 ->Strongly Connected Components: 9.67/9.80 ->->Cycle: 9.67/9.80 ->->-> Pairs: 9.67/9.80 F(X1:S,X2:S,active(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,mark(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 ->->-> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 9.67/9.80 Problem 1.1: 9.67/9.80 9.67/9.80 Subterm Processor: 9.67/9.80 -> Pairs: 9.67/9.80 F(X1:S,X2:S,active(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 F(X1:S,X2:S,mark(X3:S)) -> F(X1:S,X2:S,X3:S) 9.67/9.80 -> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 ->Projection: 9.67/9.80 pi(F) = 3 9.67/9.80 9.67/9.80 Problem 1.1: 9.67/9.80 9.67/9.80 SCC Processor: 9.67/9.80 -> Pairs: 9.67/9.80 Empty 9.67/9.80 -> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 ->Strongly Connected Components: 9.67/9.80 There is no strongly connected component 9.67/9.80 9.67/9.80 The problem is finite. 9.67/9.80 9.67/9.80 Problem 1.2: 9.67/9.80 9.67/9.80 Reduction Pairs Processor: 9.67/9.80 -> Pairs: 9.67/9.80 ACTIVE(f(a,X:S,X:S)) -> MARK(f(X:S,b,b)) 9.67/9.80 MARK(f(X1:S,X2:S,X3:S)) -> ACTIVE(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 MARK(f(X1:S,X2:S,X3:S)) -> MARK(X2:S) 9.67/9.80 -> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 -> Usable rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 ->Interpretation type: 9.67/9.80 Linear 9.67/9.80 ->Coefficients: 9.67/9.80 Natural Numbers 9.67/9.80 ->Dimension: 9.67/9.80 1 9.67/9.80 ->Bound: 9.67/9.80 2 9.67/9.80 ->Interpretation: 9.67/9.80 9.67/9.80 [active](X) = X 9.67/9.80 [f](X1,X2,X3) = 2.X1 + X2 + X3 + 1 9.67/9.80 [mark](X) = X 9.67/9.80 [a] = 1 9.67/9.80 [b] = 1 9.67/9.80 [fSNonEmpty] = 0 9.67/9.80 [ACTIVE](X) = 2.X + 2 9.67/9.80 [F](X1,X2,X3) = 0 9.67/9.80 [MARK](X) = 2.X + 2 9.67/9.80 9.67/9.80 Problem 1.2: 9.67/9.80 9.67/9.80 SCC Processor: 9.67/9.80 -> Pairs: 9.67/9.80 ACTIVE(f(a,X:S,X:S)) -> MARK(f(X:S,b,b)) 9.67/9.80 MARK(f(X1:S,X2:S,X3:S)) -> ACTIVE(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 -> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 ->Strongly Connected Components: 9.67/9.80 ->->Cycle: 9.67/9.80 ->->-> Pairs: 9.67/9.80 ACTIVE(f(a,X:S,X:S)) -> MARK(f(X:S,b,b)) 9.67/9.80 MARK(f(X1:S,X2:S,X3:S)) -> ACTIVE(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 ->->-> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 9.67/9.80 Problem 1.2: 9.67/9.80 9.67/9.80 Reduction Pairs Processor: 9.67/9.80 -> Pairs: 9.67/9.80 ACTIVE(f(a,X:S,X:S)) -> MARK(f(X:S,b,b)) 9.67/9.80 MARK(f(X1:S,X2:S,X3:S)) -> ACTIVE(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 -> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 -> Usable rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 ->Interpretation type: 9.67/9.80 Linear 9.67/9.80 ->Coefficients: 9.67/9.80 Natural Numbers 9.67/9.80 ->Dimension: 9.67/9.80 2 9.67/9.80 ->Bound: 9.67/9.80 1 9.67/9.80 ->Interpretation: 9.67/9.80 9.67/9.80 [active](X) = [1 1;0 1].X + [1;0] 9.67/9.80 [f](X1,X2,X3) = [1 0;1 0].X1 + [1 0;1 0].X3 + [1;0] 9.67/9.80 [mark](X) = [1 1;0 1].X + [1;1] 9.67/9.80 [a] = [1;0] 9.67/9.80 [b] = [0;1] 9.67/9.80 [fSNonEmpty] = 0 9.67/9.80 [ACTIVE](X) = [1 0;1 1].X + [0;1] 9.67/9.80 [F](X1,X2,X3) = 0 9.67/9.80 [MARK](X) = [0 1;1 1].X + [1;1] 9.67/9.80 9.67/9.80 Problem 1.2: 9.67/9.80 9.67/9.80 SCC Processor: 9.67/9.80 -> Pairs: 9.67/9.80 MARK(f(X1:S,X2:S,X3:S)) -> ACTIVE(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 -> Rules: 9.67/9.80 active(f(a,X:S,X:S)) -> mark(f(X:S,b,b)) 9.67/9.80 active(b) -> mark(a) 9.67/9.80 f(active(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(mark(X1:S),X2:S,X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,active(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,mark(X2:S),X3:S) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,active(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 f(X1:S,X2:S,mark(X3:S)) -> f(X1:S,X2:S,X3:S) 9.67/9.80 mark(f(X1:S,X2:S,X3:S)) -> active(f(X1:S,mark(X2:S),X3:S)) 9.67/9.80 mark(a) -> active(a) 9.67/9.80 mark(b) -> active(b) 9.67/9.80 ->Strongly Connected Components: 9.67/9.80 There is no strongly connected component 9.67/9.80 9.67/9.80 The problem is finite. 9.67/9.80 EOF