1.01/1.30 YES 1.01/1.30 1.01/1.30 Problem 1: 1.01/1.30 1.01/1.30 (VAR x y) 1.01/1.30 (THEORY 1.01/1.30 (AC plus times)) 1.01/1.30 (RULES 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 ) 1.01/1.30 1.01/1.30 Problem 1: 1.01/1.30 1.01/1.30 Dependency Pairs Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 PLUS(plus(x2,x3),x4) = PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) = PLUS(x3,x2) 1.01/1.30 TIMES(times(x2,x3),x4) = TIMES(x2,times(x3,x4)) 1.01/1.30 TIMES(x2,x3) = TIMES(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 PLUS(plus(x,0),x2) -> PLUS(x,x2) 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(s(plus(x,y)),x2) 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(x,y) 1.01/1.30 PLUS(x,s(y)) -> PLUS(x,y) 1.01/1.30 POWER(x,s(y)) -> POWER(x,y) 1.01/1.30 POWER(x,s(y)) -> TIMES(x,power(x,y)) 1.01/1.30 TIMES(times(x,0),x2) -> TIMES(0,x2) 1.01/1.30 TIMES(times(x,s(y)),x2) -> PLUS(x,times(x,y)) 1.01/1.30 TIMES(times(x,s(y)),x2) -> TIMES(plus(x,times(x,y)),x2) 1.01/1.30 TIMES(times(x,s(y)),x2) -> TIMES(x,y) 1.01/1.30 TIMES(x,s(y)) -> PLUS(x,times(x,y)) 1.01/1.30 TIMES(x,s(y)) -> TIMES(x,y) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(plus(x2,x3),x4) -> PLUS(x2,x3) 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,x3) 1.01/1.30 TIMES(x2,times(x3,x4)) -> TIMES(x3,x4) 1.01/1.30 1.01/1.30 Problem 1: 1.01/1.30 1.01/1.30 SCC Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 PLUS(plus(x2,x3),x4) = PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) = PLUS(x3,x2) 1.01/1.30 TIMES(times(x2,x3),x4) = TIMES(x2,times(x3,x4)) 1.01/1.30 TIMES(x2,x3) = TIMES(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 PLUS(plus(x,0),x2) -> PLUS(x,x2) 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(s(plus(x,y)),x2) 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(x,y) 1.01/1.30 PLUS(x,s(y)) -> PLUS(x,y) 1.01/1.30 POWER(x,s(y)) -> POWER(x,y) 1.01/1.30 POWER(x,s(y)) -> TIMES(x,power(x,y)) 1.01/1.30 TIMES(times(x,0),x2) -> TIMES(0,x2) 1.01/1.30 TIMES(times(x,s(y)),x2) -> PLUS(x,times(x,y)) 1.01/1.30 TIMES(times(x,s(y)),x2) -> TIMES(plus(x,times(x,y)),x2) 1.01/1.30 TIMES(times(x,s(y)),x2) -> TIMES(x,y) 1.01/1.30 TIMES(x,s(y)) -> PLUS(x,times(x,y)) 1.01/1.30 TIMES(x,s(y)) -> TIMES(x,y) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(plus(x2,x3),x4) -> PLUS(x2,x3) 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,x3) 1.01/1.30 TIMES(x2,times(x3,x4)) -> TIMES(x3,x4) 1.01/1.30 ->Strongly Connected Components: 1.01/1.30 ->->Cycle: 1.01/1.30 ->->-> Pairs: 1.01/1.30 PLUS(plus(x,0),x2) -> PLUS(x,x2) 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(s(plus(x,y)),x2) 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(x,y) 1.01/1.30 PLUS(x,s(y)) -> PLUS(x,y) 1.01/1.30 -> FAxioms: 1.01/1.30 plus(plus(x2,x3),x4) -> plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) -> plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) -> times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) -> times(x3,x2) 1.01/1.30 PLUS(plus(x2,x3),x4) -> PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) -> PLUS(x3,x2) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 ->->-> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(plus(x2,x3),x4) -> PLUS(x2,x3) 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 ->->Cycle: 1.01/1.30 ->->-> Pairs: 1.01/1.30 TIMES(times(x,0),x2) -> TIMES(0,x2) 1.01/1.30 TIMES(times(x,s(y)),x2) -> TIMES(plus(x,times(x,y)),x2) 1.01/1.30 TIMES(times(x,s(y)),x2) -> TIMES(x,y) 1.01/1.30 TIMES(x,s(y)) -> TIMES(x,y) 1.01/1.30 -> FAxioms: 1.01/1.30 plus(plus(x2,x3),x4) -> plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) -> plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) -> times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) -> times(x3,x2) 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,times(x3,x4)) 1.01/1.30 TIMES(x2,x3) -> TIMES(x3,x2) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 ->->-> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,x3) 1.01/1.30 TIMES(x2,times(x3,x4)) -> TIMES(x3,x4) 1.01/1.30 ->->Cycle: 1.01/1.30 ->->-> Pairs: 1.01/1.30 POWER(x,s(y)) -> POWER(x,y) 1.01/1.30 -> FAxioms: 1.01/1.30 plus(plus(x2,x3),x4) -> plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) -> plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) -> times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) -> times(x3,x2) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 ->->-> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 Empty 1.01/1.30 1.01/1.30 1.01/1.30 The problem is decomposed in 3 subproblems. 1.01/1.30 1.01/1.30 Problem 1.1: 1.01/1.30 1.01/1.30 Reduction Pairs Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 PLUS(plus(x2,x3),x4) = PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) = PLUS(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 PLUS(plus(x,0),x2) -> PLUS(x,x2) 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(s(plus(x,y)),x2) 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(x,y) 1.01/1.30 PLUS(x,s(y)) -> PLUS(x,y) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Usable Equations: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> Usable Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(plus(x2,x3),x4) -> PLUS(x2,x3) 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 ->Interpretation type: 1.01/1.30 Linear 1.01/1.30 ->Coefficients: 1.01/1.30 Natural Numbers 1.01/1.30 ->Dimension: 1.01/1.30 1 1.01/1.30 ->Bound: 1.01/1.30 2 1.01/1.30 ->Interpretation: 1.01/1.30 1.01/1.30 [plus](X1,X2) = X1 + X2 + 2 1.01/1.30 [power](X1,X2) = 0 1.01/1.30 [times](X1,X2) = 0 1.01/1.30 [0] = 2 1.01/1.30 [s](X) = X + 1 1.01/1.30 [PLUS](X1,X2) = 2.X1 + 2.X2 1.01/1.30 [POWER](X1,X2) = 0 1.01/1.30 [TIMES](X1,X2) = 0 1.01/1.30 1.01/1.30 Problem 1.1: 1.01/1.30 1.01/1.30 SCC Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 PLUS(plus(x2,x3),x4) = PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) = PLUS(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(s(plus(x,y)),x2) 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(x,y) 1.01/1.30 PLUS(x,s(y)) -> PLUS(x,y) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(plus(x2,x3),x4) -> PLUS(x2,x3) 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 ->Strongly Connected Components: 1.01/1.30 ->->Cycle: 1.01/1.30 ->->-> Pairs: 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(s(plus(x,y)),x2) 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(x,y) 1.01/1.30 PLUS(x,s(y)) -> PLUS(x,y) 1.01/1.30 -> FAxioms: 1.01/1.30 plus(plus(x2,x3),x4) -> plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) -> plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) -> times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) -> times(x3,x2) 1.01/1.30 PLUS(plus(x2,x3),x4) -> PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) -> PLUS(x3,x2) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 ->->-> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(plus(x2,x3),x4) -> PLUS(x2,x3) 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 1.01/1.30 Problem 1.1: 1.01/1.30 1.01/1.30 Reduction Pairs Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 PLUS(plus(x2,x3),x4) = PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) = PLUS(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(s(plus(x,y)),x2) 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(x,y) 1.01/1.30 PLUS(x,s(y)) -> PLUS(x,y) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Usable Equations: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> Usable Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(plus(x2,x3),x4) -> PLUS(x2,x3) 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 ->Interpretation type: 1.01/1.30 Linear 1.01/1.30 ->Coefficients: 1.01/1.30 Natural Numbers 1.01/1.30 ->Dimension: 1.01/1.30 1 1.01/1.30 ->Bound: 1.01/1.30 2 1.01/1.30 ->Interpretation: 1.01/1.30 1.01/1.30 [plus](X1,X2) = X1 + X2 + 1 1.01/1.30 [power](X1,X2) = 0 1.01/1.30 [times](X1,X2) = 0 1.01/1.30 [0] = 0 1.01/1.30 [s](X) = X + 2 1.01/1.30 [PLUS](X1,X2) = 2.X1 + 2.X2 1.01/1.30 [POWER](X1,X2) = 0 1.01/1.30 [TIMES](X1,X2) = 0 1.01/1.30 1.01/1.30 Problem 1.1: 1.01/1.30 1.01/1.30 SCC Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 PLUS(plus(x2,x3),x4) = PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) = PLUS(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(s(plus(x,y)),x2) 1.01/1.30 PLUS(x,s(y)) -> PLUS(x,y) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(plus(x2,x3),x4) -> PLUS(x2,x3) 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 ->Strongly Connected Components: 1.01/1.30 ->->Cycle: 1.01/1.30 ->->-> Pairs: 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(s(plus(x,y)),x2) 1.01/1.30 PLUS(x,s(y)) -> PLUS(x,y) 1.01/1.30 -> FAxioms: 1.01/1.30 plus(plus(x2,x3),x4) -> plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) -> plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) -> times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) -> times(x3,x2) 1.01/1.30 PLUS(plus(x2,x3),x4) -> PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) -> PLUS(x3,x2) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 ->->-> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(plus(x2,x3),x4) -> PLUS(x2,x3) 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 1.01/1.30 Problem 1.1: 1.01/1.30 1.01/1.30 Reduction Pairs Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 PLUS(plus(x2,x3),x4) = PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) = PLUS(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(s(plus(x,y)),x2) 1.01/1.30 PLUS(x,s(y)) -> PLUS(x,y) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Usable Equations: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> Usable Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(plus(x2,x3),x4) -> PLUS(x2,x3) 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 ->Interpretation type: 1.01/1.30 Linear 1.01/1.30 ->Coefficients: 1.01/1.30 Natural Numbers 1.01/1.30 ->Dimension: 1.01/1.30 1 1.01/1.30 ->Bound: 1.01/1.30 2 1.01/1.30 ->Interpretation: 1.01/1.30 1.01/1.30 [plus](X1,X2) = X1 + X2 + 2 1.01/1.30 [power](X1,X2) = 0 1.01/1.30 [times](X1,X2) = 0 1.01/1.30 [0] = 0 1.01/1.30 [s](X) = X + 1 1.01/1.30 [PLUS](X1,X2) = 2.X1 + 2.X2 1.01/1.30 [POWER](X1,X2) = 0 1.01/1.30 [TIMES](X1,X2) = 0 1.01/1.30 1.01/1.30 Problem 1.1: 1.01/1.30 1.01/1.30 SCC Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 PLUS(plus(x2,x3),x4) = PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) = PLUS(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(s(plus(x,y)),x2) 1.01/1.30 PLUS(x,s(y)) -> PLUS(x,y) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 ->Strongly Connected Components: 1.01/1.30 ->->Cycle: 1.01/1.30 ->->-> Pairs: 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(s(plus(x,y)),x2) 1.01/1.30 PLUS(x,s(y)) -> PLUS(x,y) 1.01/1.30 -> FAxioms: 1.01/1.30 plus(plus(x2,x3),x4) -> plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) -> plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) -> times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) -> times(x3,x2) 1.01/1.30 PLUS(plus(x2,x3),x4) -> PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) -> PLUS(x3,x2) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 ->->-> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 1.01/1.30 Problem 1.1: 1.01/1.30 1.01/1.30 Reduction Pairs Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 PLUS(plus(x2,x3),x4) = PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) = PLUS(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(s(plus(x,y)),x2) 1.01/1.30 PLUS(x,s(y)) -> PLUS(x,y) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Usable Equations: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> Usable Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 ->Interpretation type: 1.01/1.30 Linear 1.01/1.30 ->Coefficients: 1.01/1.30 Natural Numbers 1.01/1.30 ->Dimension: 1.01/1.30 1 1.01/1.30 ->Bound: 1.01/1.30 2 1.01/1.30 ->Interpretation: 1.01/1.30 1.01/1.30 [plus](X1,X2) = X1 + X2 + 1 1.01/1.30 [power](X1,X2) = 0 1.01/1.30 [times](X1,X2) = 0 1.01/1.30 [0] = 0 1.01/1.30 [s](X) = X + 2 1.01/1.30 [PLUS](X1,X2) = 2.X1 + 2.X2 1.01/1.30 [POWER](X1,X2) = 0 1.01/1.30 [TIMES](X1,X2) = 0 1.01/1.30 1.01/1.30 Problem 1.1: 1.01/1.30 1.01/1.30 SCC Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 PLUS(plus(x2,x3),x4) = PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) = PLUS(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(s(plus(x,y)),x2) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 ->Strongly Connected Components: 1.01/1.30 ->->Cycle: 1.01/1.30 ->->-> Pairs: 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(s(plus(x,y)),x2) 1.01/1.30 -> FAxioms: 1.01/1.30 plus(plus(x2,x3),x4) -> plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) -> plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) -> times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) -> times(x3,x2) 1.01/1.30 PLUS(plus(x2,x3),x4) -> PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) -> PLUS(x3,x2) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 ->->-> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 1.01/1.30 Problem 1.1: 1.01/1.30 1.01/1.30 Reduction Pairs Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 PLUS(plus(x2,x3),x4) = PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) = PLUS(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 PLUS(plus(x,s(y)),x2) -> PLUS(s(plus(x,y)),x2) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Usable Equations: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> Usable Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 ->Interpretation type: 1.01/1.30 Linear 1.01/1.30 ->Coefficients: 1.01/1.30 Natural Numbers 1.01/1.30 ->Dimension: 1.01/1.30 1 1.01/1.30 ->Bound: 1.01/1.30 2 1.01/1.30 ->Interpretation: 1.01/1.30 1.01/1.30 [plus](X1,X2) = X1 + X2 + 1 1.01/1.30 [power](X1,X2) = 0 1.01/1.30 [times](X1,X2) = 0 1.01/1.30 [0] = 0 1.01/1.30 [s](X) = 2 1.01/1.30 [PLUS](X1,X2) = 2.X1 + 2.X2 1.01/1.30 [POWER](X1,X2) = 0 1.01/1.30 [TIMES](X1,X2) = 0 1.01/1.30 1.01/1.30 Problem 1.1: 1.01/1.30 1.01/1.30 SCC Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 PLUS(plus(x2,x3),x4) = PLUS(x2,plus(x3,x4)) 1.01/1.30 PLUS(x2,x3) = PLUS(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 Empty 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 PLUS(x2,plus(x3,x4)) -> PLUS(x3,x4) 1.01/1.30 ->Strongly Connected Components: 1.01/1.30 There is no strongly connected component 1.01/1.30 1.01/1.30 The problem is finite. 1.01/1.30 1.01/1.30 Problem 1.2: 1.01/1.30 1.01/1.30 Reduction Pairs Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 TIMES(times(x2,x3),x4) = TIMES(x2,times(x3,x4)) 1.01/1.30 TIMES(x2,x3) = TIMES(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 TIMES(times(x,0),x2) -> TIMES(0,x2) 1.01/1.30 TIMES(times(x,s(y)),x2) -> TIMES(plus(x,times(x,y)),x2) 1.01/1.30 TIMES(times(x,s(y)),x2) -> TIMES(x,y) 1.01/1.30 TIMES(x,s(y)) -> TIMES(x,y) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Usable Equations: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> Usable Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,x3) 1.01/1.30 TIMES(x2,times(x3,x4)) -> TIMES(x3,x4) 1.01/1.30 ->Interpretation type: 1.01/1.30 Simple mixed 1.01/1.30 ->Coefficients: 1.01/1.30 Natural Numbers 1.01/1.30 ->Dimension: 1.01/1.30 1 1.01/1.30 ->Bound: 1.01/1.30 1 1.01/1.30 ->Interpretation: 1.01/1.30 1.01/1.30 [plus](X1,X2) = X1 + X2 1.01/1.30 [power](X1,X2) = 0 1.01/1.30 [times](X1,X2) = X1.X2 + X1 + X2 1.01/1.30 [0] = 1 1.01/1.30 [s](X) = X + 1 1.01/1.30 [PLUS](X1,X2) = 0 1.01/1.30 [POWER](X1,X2) = 0 1.01/1.30 [TIMES](X1,X2) = X1.X2 + X1 + X2 1.01/1.30 1.01/1.30 Problem 1.2: 1.01/1.30 1.01/1.30 SCC Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 TIMES(times(x2,x3),x4) = TIMES(x2,times(x3,x4)) 1.01/1.30 TIMES(x2,x3) = TIMES(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 TIMES(times(x,0),x2) -> TIMES(0,x2) 1.01/1.30 TIMES(times(x,s(y)),x2) -> TIMES(x,y) 1.01/1.30 TIMES(x,s(y)) -> TIMES(x,y) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,x3) 1.01/1.30 TIMES(x2,times(x3,x4)) -> TIMES(x3,x4) 1.01/1.30 ->Strongly Connected Components: 1.01/1.30 ->->Cycle: 1.01/1.30 ->->-> Pairs: 1.01/1.30 TIMES(times(x,0),x2) -> TIMES(0,x2) 1.01/1.30 TIMES(times(x,s(y)),x2) -> TIMES(x,y) 1.01/1.30 TIMES(x,s(y)) -> TIMES(x,y) 1.01/1.30 -> FAxioms: 1.01/1.30 plus(plus(x2,x3),x4) -> plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) -> plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) -> times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) -> times(x3,x2) 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,times(x3,x4)) 1.01/1.30 TIMES(x2,x3) -> TIMES(x3,x2) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 ->->-> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,x3) 1.01/1.30 TIMES(x2,times(x3,x4)) -> TIMES(x3,x4) 1.01/1.30 1.01/1.30 Problem 1.2: 1.01/1.30 1.01/1.30 Reduction Pairs Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 TIMES(times(x2,x3),x4) = TIMES(x2,times(x3,x4)) 1.01/1.30 TIMES(x2,x3) = TIMES(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 TIMES(times(x,0),x2) -> TIMES(0,x2) 1.01/1.30 TIMES(times(x,s(y)),x2) -> TIMES(x,y) 1.01/1.30 TIMES(x,s(y)) -> TIMES(x,y) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Usable Equations: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> Usable Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,x3) 1.01/1.30 TIMES(x2,times(x3,x4)) -> TIMES(x3,x4) 1.01/1.30 ->Interpretation type: 1.01/1.30 Simple mixed 1.01/1.30 ->Coefficients: 1.01/1.30 Natural Numbers 1.01/1.30 ->Dimension: 1.01/1.30 1 1.01/1.30 ->Bound: 1.01/1.30 1 1.01/1.30 ->Interpretation: 1.01/1.30 1.01/1.30 [plus](X1,X2) = X1 + X2 + 1 1.01/1.30 [power](X1,X2) = 0 1.01/1.30 [times](X1,X2) = X1.X2 + X1 + X2 1.01/1.30 [0] = 1 1.01/1.30 [s](X) = X + 1 1.01/1.30 [PLUS](X1,X2) = 0 1.01/1.30 [POWER](X1,X2) = 0 1.01/1.30 [TIMES](X1,X2) = X1.X2 + X1 + X2 1.01/1.30 1.01/1.30 Problem 1.2: 1.01/1.30 1.01/1.30 SCC Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 TIMES(times(x2,x3),x4) = TIMES(x2,times(x3,x4)) 1.01/1.30 TIMES(x2,x3) = TIMES(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 TIMES(times(x,0),x2) -> TIMES(0,x2) 1.01/1.30 TIMES(x,s(y)) -> TIMES(x,y) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,x3) 1.01/1.30 TIMES(x2,times(x3,x4)) -> TIMES(x3,x4) 1.01/1.30 ->Strongly Connected Components: 1.01/1.30 ->->Cycle: 1.01/1.30 ->->-> Pairs: 1.01/1.30 TIMES(times(x,0),x2) -> TIMES(0,x2) 1.01/1.30 TIMES(x,s(y)) -> TIMES(x,y) 1.01/1.30 -> FAxioms: 1.01/1.30 plus(plus(x2,x3),x4) -> plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) -> plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) -> times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) -> times(x3,x2) 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,times(x3,x4)) 1.01/1.30 TIMES(x2,x3) -> TIMES(x3,x2) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 ->->-> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,x3) 1.01/1.30 TIMES(x2,times(x3,x4)) -> TIMES(x3,x4) 1.01/1.30 1.01/1.30 Problem 1.2: 1.01/1.30 1.01/1.30 Reduction Pairs Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 TIMES(times(x2,x3),x4) = TIMES(x2,times(x3,x4)) 1.01/1.30 TIMES(x2,x3) = TIMES(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 TIMES(times(x,0),x2) -> TIMES(0,x2) 1.01/1.30 TIMES(x,s(y)) -> TIMES(x,y) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Usable Equations: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> Usable Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,x3) 1.01/1.30 TIMES(x2,times(x3,x4)) -> TIMES(x3,x4) 1.01/1.30 ->Interpretation type: 1.01/1.30 Simple mixed 1.01/1.30 ->Coefficients: 1.01/1.30 Natural Numbers 1.01/1.30 ->Dimension: 1.01/1.30 1 1.01/1.30 ->Bound: 1.01/1.30 1 1.01/1.30 ->Interpretation: 1.01/1.30 1.01/1.30 [plus](X1,X2) = X1 + X2 + 1 1.01/1.30 [power](X1,X2) = 0 1.01/1.30 [times](X1,X2) = X1.X2 + X1 + X2 1.01/1.30 [0] = 1 1.01/1.30 [s](X) = X + 1 1.01/1.30 [PLUS](X1,X2) = 0 1.01/1.30 [POWER](X1,X2) = 0 1.01/1.30 [TIMES](X1,X2) = X1.X2 + X1 + X2 1.01/1.30 1.01/1.30 Problem 1.2: 1.01/1.30 1.01/1.30 SCC Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 TIMES(times(x2,x3),x4) = TIMES(x2,times(x3,x4)) 1.01/1.30 TIMES(x2,x3) = TIMES(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 TIMES(times(x,0),x2) -> TIMES(0,x2) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,x3) 1.01/1.30 TIMES(x2,times(x3,x4)) -> TIMES(x3,x4) 1.01/1.30 ->Strongly Connected Components: 1.01/1.30 ->->Cycle: 1.01/1.30 ->->-> Pairs: 1.01/1.30 TIMES(times(x,0),x2) -> TIMES(0,x2) 1.01/1.30 -> FAxioms: 1.01/1.30 plus(plus(x2,x3),x4) -> plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) -> plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) -> times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) -> times(x3,x2) 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,times(x3,x4)) 1.01/1.30 TIMES(x2,x3) -> TIMES(x3,x2) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 ->->-> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,x3) 1.01/1.30 TIMES(x2,times(x3,x4)) -> TIMES(x3,x4) 1.01/1.30 1.01/1.30 Problem 1.2: 1.01/1.30 1.01/1.30 Reduction Pairs Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 TIMES(times(x2,x3),x4) = TIMES(x2,times(x3,x4)) 1.01/1.30 TIMES(x2,x3) = TIMES(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 TIMES(times(x,0),x2) -> TIMES(0,x2) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Usable Equations: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> Usable Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,x3) 1.01/1.30 TIMES(x2,times(x3,x4)) -> TIMES(x3,x4) 1.01/1.30 ->Interpretation type: 1.01/1.30 Simple mixed 1.01/1.30 ->Coefficients: 1.01/1.30 All rationals 1.01/1.30 ->Dimension: 1.01/1.30 1 1.01/1.30 ->Bound: 1.01/1.30 3 1.01/1.30 ->Interpretation: 1.01/1.30 1.01/1.30 [plus](X1,X2) = X1 + X2 + 2/3 1.01/1.30 [power](X1,X2) = 0 1.01/1.30 [times](X1,X2) = 2.X1.X2 + 3.X1 + 3.X2 + 3 1.01/1.30 [0] = 1/3 1.01/1.30 [s](X) = X + 2 1.01/1.30 [PLUS](X1,X2) = 0 1.01/1.30 [POWER](X1,X2) = 0 1.01/1.30 [TIMES](X1,X2) = 1/3.X1.X2 + 1/2.X1 + 1/2.X2 1.01/1.30 1.01/1.30 Problem 1.2: 1.01/1.30 1.01/1.30 SCC Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 TIMES(times(x2,x3),x4) = TIMES(x2,times(x3,x4)) 1.01/1.30 TIMES(x2,x3) = TIMES(x3,x2) 1.01/1.30 -> Pairs: 1.01/1.30 Empty 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 TIMES(times(x2,x3),x4) -> TIMES(x2,x3) 1.01/1.30 TIMES(x2,times(x3,x4)) -> TIMES(x3,x4) 1.01/1.30 ->Strongly Connected Components: 1.01/1.30 There is no strongly connected component 1.01/1.30 1.01/1.30 The problem is finite. 1.01/1.30 1.01/1.30 Problem 1.3: 1.01/1.30 1.01/1.30 Subterm Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 Empty 1.01/1.30 -> Pairs: 1.01/1.30 POWER(x,s(y)) -> POWER(x,y) 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 Empty 1.01/1.30 ->Projection: 1.01/1.30 pi(POWER) = [2] 1.01/1.30 1.01/1.30 Problem 1.3: 1.01/1.30 1.01/1.30 SCC Processor: 1.01/1.30 -> FAxioms: 1.01/1.30 Empty 1.01/1.30 -> Pairs: 1.01/1.30 Empty 1.01/1.30 -> EAxioms: 1.01/1.30 plus(plus(x2,x3),x4) = plus(x2,plus(x3,x4)) 1.01/1.30 plus(x2,x3) = plus(x3,x2) 1.01/1.30 times(times(x2,x3),x4) = times(x2,times(x3,x4)) 1.01/1.30 times(x2,x3) = times(x3,x2) 1.01/1.30 -> Rules: 1.01/1.30 plus(x,0) -> x 1.01/1.30 plus(x,s(y)) -> s(plus(x,y)) 1.01/1.30 power(x,0) -> s(0) 1.01/1.30 power(x,s(y)) -> times(x,power(x,y)) 1.01/1.30 times(x,0) -> 0 1.01/1.30 times(x,s(y)) -> plus(x,times(x,y)) 1.01/1.30 -> SRules: 1.01/1.30 Empty 1.01/1.30 ->Strongly Connected Components: 1.01/1.30 There is no strongly connected component 1.01/1.30 1.01/1.30 The problem is finite. 1.01/1.30 EOF