17.44/19.07 YES 17.44/19.07 17.44/19.07 Problem 1: 17.44/19.07 17.44/19.07 (VAR t x y z) 17.44/19.07 (THEORY 17.44/19.07 (AC app plus)) 17.44/19.07 (RULES 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 ) 17.44/19.07 17.44/19.07 Problem 1: 17.44/19.07 17.44/19.07 Dependency Pairs Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) = APP(x5,x4) 17.44/19.07 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 17.44/19.07 PLUS(x4,x5) = PLUS(x5,x4) 17.44/19.07 -> Pairs: 17.44/19.07 APP(app(singl(x),singl(y)),x4) -> APP(if(eq(x,y),singl(x),empty),x4) 17.44/19.07 APP(app(singl(x),singl(y)),x4) -> EQ(x,y) 17.44/19.07 APP(app(singl(x),singl(y)),x4) -> IF(eq(x,y),singl(x),empty) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> PLUS(app(x,y),app(x,z)) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> PLUS(app(x,y),app(x,z)) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(singl(x),singl(y)) -> EQ(x,y) 17.44/19.07 APP(singl(x),singl(y)) -> IF(eq(x,y),singl(x),empty) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,app(plus(y,z),t)) -> PLUS(app(x,y),app(x,z)) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> PLUS(app(x,y),app(x,z)) 17.44/19.07 EQ(s(x),s(y)) -> EQ(x,y) 17.44/19.07 PLUS(plus(empty,x),x4) -> PLUS(x,x4) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 17.44/19.07 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 17.44/19.07 17.44/19.07 Problem 1: 17.44/19.07 17.44/19.07 SCC Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) = APP(x5,x4) 17.44/19.07 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 17.44/19.07 PLUS(x4,x5) = PLUS(x5,x4) 17.44/19.07 -> Pairs: 17.44/19.07 APP(app(singl(x),singl(y)),x4) -> APP(if(eq(x,y),singl(x),empty),x4) 17.44/19.07 APP(app(singl(x),singl(y)),x4) -> EQ(x,y) 17.44/19.07 APP(app(singl(x),singl(y)),x4) -> IF(eq(x,y),singl(x),empty) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> PLUS(app(x,y),app(x,z)) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> PLUS(app(x,y),app(x,z)) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(singl(x),singl(y)) -> EQ(x,y) 17.44/19.07 APP(singl(x),singl(y)) -> IF(eq(x,y),singl(x),empty) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,app(plus(y,z),t)) -> PLUS(app(x,y),app(x,z)) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> PLUS(app(x,y),app(x,z)) 17.44/19.07 EQ(s(x),s(y)) -> EQ(x,y) 17.44/19.07 PLUS(plus(empty,x),x4) -> PLUS(x,x4) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 17.44/19.07 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 17.44/19.07 ->Strongly Connected Components: 17.44/19.07 ->->Cycle: 17.44/19.07 ->->-> Pairs: 17.44/19.07 PLUS(plus(empty,x),x4) -> PLUS(x,x4) 17.44/19.07 -> FAxioms: 17.44/19.07 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) -> app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) -> plus(x5,x4) 17.44/19.07 PLUS(plus(x4,x5),x6) -> PLUS(x4,plus(x5,x6)) 17.44/19.07 PLUS(x4,x5) -> PLUS(x5,x4) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 ->->-> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 17.44/19.07 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 17.44/19.07 ->->Cycle: 17.44/19.07 ->->-> Pairs: 17.44/19.07 EQ(s(x),s(y)) -> EQ(x,y) 17.44/19.07 -> FAxioms: 17.44/19.07 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) -> app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) -> plus(x5,x4) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 ->->-> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 Empty 17.44/19.07 ->->Cycle: 17.44/19.07 ->->-> Pairs: 17.44/19.07 APP(app(singl(x),singl(y)),x4) -> APP(if(eq(x,y),singl(x),empty),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> FAxioms: 17.44/19.07 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) -> app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) -> plus(x5,x4) 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) -> APP(x5,x4) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 ->->-> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 17.44/19.07 17.44/19.07 The problem is decomposed in 3 subproblems. 17.44/19.07 17.44/19.07 Problem 1.1: 17.44/19.07 17.44/19.07 Reduction Pairs Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 17.44/19.07 PLUS(x4,x5) = PLUS(x5,x4) 17.44/19.07 -> Pairs: 17.44/19.07 PLUS(plus(empty,x),x4) -> PLUS(x,x4) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Usable Equations: 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> Usable Rules: 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 17.44/19.07 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 17.44/19.07 ->Interpretation type: 17.44/19.07 Linear 17.44/19.07 ->Coefficients: 17.44/19.07 Natural Numbers 17.44/19.07 ->Dimension: 17.44/19.07 1 17.44/19.07 ->Bound: 17.44/19.07 2 17.44/19.07 ->Interpretation: 17.44/19.07 17.44/19.07 [app](X1,X2) = 0 17.44/19.07 [eq](X1,X2) = 0 17.44/19.07 [if](X1,X2,X3) = 0 17.44/19.07 [plus](X1,X2) = X1 + X2 17.44/19.07 [0] = 0 17.44/19.07 [empty] = 2 17.44/19.07 [false] = 0 17.44/19.07 [s](X) = 0 17.44/19.07 [singl](X) = 0 17.44/19.07 [true] = 0 17.44/19.07 [APP](X1,X2) = 0 17.44/19.07 [EQ](X1,X2) = 0 17.44/19.07 [IF](X1,X2,X3) = 0 17.44/19.07 [PLUS](X1,X2) = 2.X1 + 2.X2 17.44/19.07 17.44/19.07 Problem 1.1: 17.44/19.07 17.44/19.07 SCC Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 17.44/19.07 PLUS(x4,x5) = PLUS(x5,x4) 17.44/19.07 -> Pairs: 17.44/19.07 Empty 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 17.44/19.07 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 17.44/19.07 ->Strongly Connected Components: 17.44/19.07 There is no strongly connected component 17.44/19.07 17.44/19.07 The problem is finite. 17.44/19.07 17.44/19.07 Problem 1.2: 17.44/19.07 17.44/19.07 Subterm Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 Empty 17.44/19.07 -> Pairs: 17.44/19.07 EQ(s(x),s(y)) -> EQ(x,y) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 Empty 17.44/19.07 ->Projection: 17.44/19.07 pi(EQ) = [1] 17.44/19.07 17.44/19.07 Problem 1.2: 17.44/19.07 17.44/19.07 SCC Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 Empty 17.44/19.07 -> Pairs: 17.44/19.07 Empty 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 Empty 17.44/19.07 ->Strongly Connected Components: 17.44/19.07 There is no strongly connected component 17.44/19.07 17.44/19.07 The problem is finite. 17.44/19.07 17.44/19.07 Problem 1.3: 17.44/19.07 17.44/19.07 Reduction Pairs Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) = APP(x5,x4) 17.44/19.07 -> Pairs: 17.44/19.07 APP(app(singl(x),singl(y)),x4) -> APP(if(eq(x,y),singl(x),empty),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Usable Equations: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> Usable Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 ->Interpretation type: 17.44/19.07 Simple mixed 17.44/19.07 ->Coefficients: 17.44/19.07 Natural Numbers 17.44/19.07 ->Dimension: 17.44/19.07 1 17.44/19.07 ->Bound: 17.44/19.07 1 17.44/19.07 ->Interpretation: 17.44/19.07 17.44/19.07 [app](X1,X2) = X1.X2 + X1 + X2 17.44/19.07 [eq](X1,X2) = X2 17.44/19.07 [if](X1,X2,X3) = X1.X2 + X1.X3 + X2.X3 + X2 17.44/19.07 [plus](X1,X2) = X1 + X2 + 1 17.44/19.07 [0] = 1 17.44/19.07 [empty] = 1 17.44/19.07 [false] = 1 17.44/19.07 [s](X) = X + 1 17.44/19.07 [singl](X) = X.X + X + 1 17.44/19.07 [true] = 1 17.44/19.07 [APP](X1,X2) = X1.X2 + X1 + X2 17.44/19.07 [EQ](X1,X2) = 0 17.44/19.07 [IF](X1,X2,X3) = 0 17.44/19.07 [PLUS](X1,X2) = 0 17.44/19.07 17.44/19.07 Problem 1.3: 17.44/19.07 17.44/19.07 SCC Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) = APP(x5,x4) 17.44/19.07 -> Pairs: 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 ->Strongly Connected Components: 17.44/19.07 ->->Cycle: 17.44/19.07 ->->-> Pairs: 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> FAxioms: 17.44/19.07 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) -> app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) -> plus(x5,x4) 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) -> APP(x5,x4) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 ->->-> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 17.44/19.07 Problem 1.3: 17.44/19.07 17.44/19.07 Reduction Pairs Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) = APP(x5,x4) 17.44/19.07 -> Pairs: 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Usable Equations: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> Usable Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 ->Interpretation type: 17.44/19.07 Simple mixed 17.44/19.07 ->Coefficients: 17.44/19.07 Natural Numbers 17.44/19.07 ->Dimension: 17.44/19.07 1 17.44/19.07 ->Bound: 17.44/19.07 1 17.44/19.07 ->Interpretation: 17.44/19.07 17.44/19.07 [app](X1,X2) = X1.X2 + X1 + X2 17.44/19.07 [eq](X1,X2) = X1.X2 + X1 + X2 + 1 17.44/19.07 [if](X1,X2,X3) = X1.X3 + X2 + X3 17.44/19.07 [plus](X1,X2) = X1 + X2 + 1 17.44/19.07 [0] = 1 17.44/19.07 [empty] = 1 17.44/19.07 [false] = 1 17.44/19.07 [s](X) = X + 1 17.44/19.07 [singl](X) = X.X + X + 1 17.44/19.07 [true] = 1 17.44/19.07 [APP](X1,X2) = X1.X2 + X1 + X2 17.44/19.07 [EQ](X1,X2) = 0 17.44/19.07 [IF](X1,X2,X3) = 0 17.44/19.07 [PLUS](X1,X2) = 0 17.44/19.07 17.44/19.07 Problem 1.3: 17.44/19.07 17.44/19.07 SCC Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) = APP(x5,x4) 17.44/19.07 -> Pairs: 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 ->Strongly Connected Components: 17.44/19.07 ->->Cycle: 17.44/19.07 ->->-> Pairs: 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> FAxioms: 17.44/19.07 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) -> app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) -> plus(x5,x4) 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) -> APP(x5,x4) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 ->->-> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 17.44/19.07 Problem 1.3: 17.44/19.07 17.44/19.07 Reduction Pairs Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) = APP(x5,x4) 17.44/19.07 -> Pairs: 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Usable Equations: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> Usable Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 ->Interpretation type: 17.44/19.07 Simple mixed 17.44/19.07 ->Coefficients: 17.44/19.07 Natural Numbers 17.44/19.07 ->Dimension: 17.44/19.07 1 17.44/19.07 ->Bound: 17.44/19.07 1 17.44/19.07 ->Interpretation: 17.44/19.07 17.44/19.07 [app](X1,X2) = X1.X2 + X1 + X2 17.44/19.07 [eq](X1,X2) = X1.X2 + X1 + X2 + 1 17.44/19.07 [if](X1,X2,X3) = X1.X3 + X2 + 1 17.44/19.07 [plus](X1,X2) = X1 + X2 + 1 17.44/19.07 [0] = 1 17.44/19.07 [empty] = 1 17.44/19.07 [false] = 1 17.44/19.07 [s](X) = X + 1 17.44/19.07 [singl](X) = X + 1 17.44/19.07 [true] = 1 17.44/19.07 [APP](X1,X2) = X1.X2 + X1 + X2 17.44/19.07 [EQ](X1,X2) = 0 17.44/19.07 [IF](X1,X2,X3) = 0 17.44/19.07 [PLUS](X1,X2) = 0 17.44/19.07 17.44/19.07 Problem 1.3: 17.44/19.07 17.44/19.07 SCC Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) = APP(x5,x4) 17.44/19.07 -> Pairs: 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 ->Strongly Connected Components: 17.44/19.07 ->->Cycle: 17.44/19.07 ->->-> Pairs: 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> FAxioms: 17.44/19.07 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) -> app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) -> plus(x5,x4) 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) -> APP(x5,x4) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 ->->-> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 17.44/19.07 Problem 1.3: 17.44/19.07 17.44/19.07 Reduction Pairs Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) = APP(x5,x4) 17.44/19.07 -> Pairs: 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,y) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Usable Equations: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> Usable Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 ->Interpretation type: 17.44/19.07 Simple mixed 17.44/19.07 ->Coefficients: 17.44/19.07 Natural Numbers 17.44/19.07 ->Dimension: 17.44/19.07 1 17.44/19.07 ->Bound: 17.44/19.07 1 17.44/19.07 ->Interpretation: 17.44/19.07 17.44/19.07 [app](X1,X2) = X1.X2 + X1 + X2 17.44/19.07 [eq](X1,X2) = 1 17.44/19.07 [if](X1,X2,X3) = X1.X2.X3 + X2 + X3 17.44/19.07 [plus](X1,X2) = X1 + X2 + 1 17.44/19.07 [0] = 0 17.44/19.07 [empty] = 1 17.44/19.07 [false] = 1 17.44/19.07 [s](X) = 1 17.44/19.07 [singl](X) = X.X + X + 1 17.44/19.07 [true] = 1 17.44/19.07 [APP](X1,X2) = X1.X2 + X1 + X2 17.44/19.07 [EQ](X1,X2) = 0 17.44/19.07 [IF](X1,X2,X3) = 0 17.44/19.07 [PLUS](X1,X2) = 0 17.44/19.07 17.44/19.07 Problem 1.3: 17.44/19.07 17.44/19.07 SCC Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) = APP(x5,x4) 17.44/19.07 -> Pairs: 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 ->Strongly Connected Components: 17.44/19.07 ->->Cycle: 17.44/19.07 ->->-> Pairs: 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> FAxioms: 17.44/19.07 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) -> app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) -> plus(x5,x4) 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) -> APP(x5,x4) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 ->->-> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 17.44/19.07 Problem 1.3: 17.44/19.07 17.44/19.07 Reduction Pairs Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) = APP(x5,x4) 17.44/19.07 -> Pairs: 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(x,z) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Usable Equations: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> Usable Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 ->Interpretation type: 17.44/19.07 Simple mixed 17.44/19.07 ->Coefficients: 17.44/19.07 Natural Numbers 17.44/19.07 ->Dimension: 17.44/19.07 1 17.44/19.07 ->Bound: 17.44/19.07 1 17.44/19.07 ->Interpretation: 17.44/19.07 17.44/19.07 [app](X1,X2) = X1.X2 + X1 + X2 17.44/19.07 [eq](X1,X2) = X1 + X2 + 1 17.44/19.07 [if](X1,X2,X3) = X1.X3 + X2.X3 + X1 + X2 + X3 + 1 17.44/19.07 [plus](X1,X2) = X1 + X2 + 1 17.44/19.07 [0] = 0 17.44/19.07 [empty] = 0 17.44/19.07 [false] = 1 17.44/19.07 [s](X) = X + 1 17.44/19.07 [singl](X) = X.X + X + 1 17.44/19.07 [true] = 1 17.44/19.07 [APP](X1,X2) = X1.X2 + X1 + X2 17.44/19.07 [EQ](X1,X2) = 0 17.44/19.07 [IF](X1,X2,X3) = 0 17.44/19.07 [PLUS](X1,X2) = 0 17.44/19.07 17.44/19.07 Problem 1.3: 17.44/19.07 17.44/19.07 SCC Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) = APP(x5,x4) 17.44/19.07 -> Pairs: 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 ->Strongly Connected Components: 17.44/19.07 ->->Cycle: 17.44/19.07 ->->-> Pairs: 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> FAxioms: 17.44/19.07 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) -> app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) -> plus(x5,x4) 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) -> APP(x5,x4) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 ->->-> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.07 app(x,app(empty,z)) -> app(empty,z) 17.44/19.07 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.07 app(x,empty) -> empty 17.44/19.07 eq(0,0) -> true 17.44/19.07 eq(0,s(x)) -> false 17.44/19.07 eq(s(x),s(y)) -> eq(x,y) 17.44/19.07 if(false,x,y) -> y 17.44/19.07 if(true,x,y) -> x 17.44/19.07 plus(empty,x) -> x 17.44/19.07 -> SRules: 17.44/19.07 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.07 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.07 17.44/19.07 Problem 1.3: 17.44/19.07 17.44/19.07 Reduction Pairs Processor: 17.44/19.07 -> FAxioms: 17.44/19.07 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.07 APP(x4,x5) = APP(x5,x4) 17.44/19.07 -> Pairs: 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.07 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.07 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.07 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,y) 17.44/19.07 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.07 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.07 -> EAxioms: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Usable Equations: 17.44/19.07 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.07 app(x4,x5) = app(x5,x4) 17.44/19.07 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.07 plus(x4,x5) = plus(x5,x4) 17.44/19.07 -> Rules: 17.44/19.07 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.07 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> Usable Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Interpretation type: 17.44/19.08 Simple mixed 17.44/19.08 ->Coefficients: 17.44/19.08 Natural Numbers 17.44/19.08 ->Dimension: 17.44/19.08 1 17.44/19.08 ->Bound: 17.44/19.08 1 17.44/19.08 ->Interpretation: 17.44/19.08 17.44/19.08 [app](X1,X2) = X1.X2 + X1 + X2 17.44/19.08 [eq](X1,X2) = X1.X2 + X1 + X2 17.44/19.08 [if](X1,X2,X3) = X1.X3 + X2 + X3 + 1 17.44/19.08 [plus](X1,X2) = X1 + X2 + 1 17.44/19.08 [0] = 1 17.44/19.08 [empty] = 1 17.44/19.08 [false] = 1 17.44/19.08 [s](X) = X + 1 17.44/19.08 [singl](X) = X + 1 17.44/19.08 [true] = 1 17.44/19.08 [APP](X1,X2) = X1.X2 + X1 + X2 17.44/19.08 [EQ](X1,X2) = 0 17.44/19.08 [IF](X1,X2,X3) = 0 17.44/19.08 [PLUS](X1,X2) = 0 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 SCC Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.08 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.08 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Strongly Connected Components: 17.44/19.08 ->->Cycle: 17.44/19.08 ->->-> Pairs: 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.08 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.08 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.08 -> FAxioms: 17.44/19.08 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) -> app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) -> plus(x5,x4) 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) -> APP(x5,x4) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 ->->-> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 Reduction Pairs Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(x,z) 17.44/19.08 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.08 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Usable Equations: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> Usable Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Interpretation type: 17.44/19.08 Simple mixed 17.44/19.08 ->Coefficients: 17.44/19.08 Natural Numbers 17.44/19.08 ->Dimension: 17.44/19.08 1 17.44/19.08 ->Bound: 17.44/19.08 1 17.44/19.08 ->Interpretation: 17.44/19.08 17.44/19.08 [app](X1,X2) = X1.X2 + X1 + X2 17.44/19.08 [eq](X1,X2) = X1 + X2 17.44/19.08 [if](X1,X2,X3) = X1.X3 + X2 + X3 + 1 17.44/19.08 [plus](X1,X2) = X1 + X2 + 1 17.44/19.08 [0] = 1 17.44/19.08 [empty] = 1 17.44/19.08 [false] = 1 17.44/19.08 [s](X) = X + 1 17.44/19.08 [singl](X) = X + 1 17.44/19.08 [true] = 1 17.44/19.08 [APP](X1,X2) = X1.X2 + X1 + X2 17.44/19.08 [EQ](X1,X2) = 0 17.44/19.08 [IF](X1,X2,X3) = 0 17.44/19.08 [PLUS](X1,X2) = 0 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 SCC Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.08 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Strongly Connected Components: 17.44/19.08 ->->Cycle: 17.44/19.08 ->->-> Pairs: 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.08 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.08 -> FAxioms: 17.44/19.08 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) -> app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) -> plus(x5,x4) 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) -> APP(x5,x4) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 ->->-> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 Reduction Pairs Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(x,plus(y,z)) -> APP(x,y) 17.44/19.08 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Usable Equations: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> Usable Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Interpretation type: 17.44/19.08 Simple mixed 17.44/19.08 ->Coefficients: 17.44/19.08 Natural Numbers 17.44/19.08 ->Dimension: 17.44/19.08 1 17.44/19.08 ->Bound: 17.44/19.08 1 17.44/19.08 ->Interpretation: 17.44/19.08 17.44/19.08 [app](X1,X2) = X1.X2 + X1 + X2 17.44/19.08 [eq](X1,X2) = X2 + 1 17.44/19.08 [if](X1,X2,X3) = X1.X2 + X1.X3 + X2.X3 + X1 + X2 + X3 17.44/19.08 [plus](X1,X2) = X1 + X2 + 1 17.44/19.08 [0] = 1 17.44/19.08 [empty] = 0 17.44/19.08 [false] = 1 17.44/19.08 [s](X) = X + 1 17.44/19.08 [singl](X) = X + 1 17.44/19.08 [true] = 0 17.44/19.08 [APP](X1,X2) = X1.X2 + X1 + X2 17.44/19.08 [EQ](X1,X2) = 0 17.44/19.08 [IF](X1,X2,X3) = 0 17.44/19.08 [PLUS](X1,X2) = 0 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 SCC Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Strongly Connected Components: 17.44/19.08 ->->Cycle: 17.44/19.08 ->->-> Pairs: 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.08 -> FAxioms: 17.44/19.08 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) -> app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) -> plus(x5,x4) 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) -> APP(x5,x4) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 ->->-> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 Reduction Pairs Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(x,plus(y,z)) -> APP(x,z) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Usable Equations: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> Usable Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Interpretation type: 17.44/19.08 Simple mixed 17.44/19.08 ->Coefficients: 17.44/19.08 Natural Numbers 17.44/19.08 ->Dimension: 17.44/19.08 1 17.44/19.08 ->Bound: 17.44/19.08 1 17.44/19.08 ->Interpretation: 17.44/19.08 17.44/19.08 [app](X1,X2) = X1.X2 + X1 + X2 17.44/19.08 [eq](X1,X2) = X1 + X2 + 1 17.44/19.08 [if](X1,X2,X3) = X1.X2.X3 + X1.X3 + X2.X3 + X1 + X2 + X3 + 1 17.44/19.08 [plus](X1,X2) = X1 + X2 + 1 17.44/19.08 [0] = 1 17.44/19.08 [empty] = 0 17.44/19.08 [false] = 1 17.44/19.08 [s](X) = X + 1 17.44/19.08 [singl](X) = X + 1 17.44/19.08 [true] = 1 17.44/19.08 [APP](X1,X2) = X1.X2 + X1 + X2 17.44/19.08 [EQ](X1,X2) = 0 17.44/19.08 [IF](X1,X2,X3) = 0 17.44/19.08 [PLUS](X1,X2) = 0 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 SCC Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Strongly Connected Components: 17.44/19.08 ->->Cycle: 17.44/19.08 ->->-> Pairs: 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> FAxioms: 17.44/19.08 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) -> app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) -> plus(x5,x4) 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) -> APP(x5,x4) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 ->->-> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 Reduction Pairs Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(app(plus(app(x,y),app(x,z)),t),x4) 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Usable Equations: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> Usable Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Interpretation type: 17.44/19.08 Simple mixed 17.44/19.08 ->Coefficients: 17.44/19.08 All rationals 17.44/19.08 ->Dimension: 17.44/19.08 1 17.44/19.08 ->Bound: 17.44/19.08 3 17.44/19.08 ->Interpretation: 17.44/19.08 17.44/19.08 [app](X1,X2) = 3.X1.X2 + 3.X1 + 3.X2 + 2 17.44/19.08 [eq](X1,X2) = 2 17.44/19.08 [if](X1,X2,X3) = 2/3.X1.X2 + 3.X2.X3 + 2/3.X1 + 2/3.X2 + X3 17.44/19.08 [plus](X1,X2) = X1 + X2 + 3 17.44/19.08 [0] = 1/3 17.44/19.08 [empty] = 0 17.44/19.08 [false] = 2 17.44/19.08 [s](X) = 2/3.X + 1/2 17.44/19.08 [singl](X) = 2/3.X + 2 17.44/19.08 [true] = 1/2 17.44/19.08 [APP](X1,X2) = 1/3.X1.X2 + 1/3.X1 + 1/3.X2 17.44/19.08 [EQ](X1,X2) = 0 17.44/19.08 [IF](X1,X2,X3) = 0 17.44/19.08 [PLUS](X1,X2) = 0 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 SCC Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Strongly Connected Components: 17.44/19.08 ->->Cycle: 17.44/19.08 ->->-> Pairs: 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> FAxioms: 17.44/19.08 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) -> app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) -> plus(x5,x4) 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) -> APP(x5,x4) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 ->->-> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 Reduction Pairs Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(app(x,app(plus(y,z),t)),x4) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Usable Equations: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> Usable Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Interpretation type: 17.44/19.08 Simple mixed 17.44/19.08 ->Coefficients: 17.44/19.08 All rationals 17.44/19.08 ->Dimension: 17.44/19.08 1 17.44/19.08 ->Bound: 17.44/19.08 3 17.44/19.08 ->Interpretation: 17.44/19.08 17.44/19.08 [app](X1,X2) = 3.X1.X2 + 3.X1 + 3.X2 + 2 17.44/19.08 [eq](X1,X2) = 2 17.44/19.08 [if](X1,X2,X3) = 3.X1.X2.X3 + 3/2.X1.X3 + 1/3.X2.X3 + 3.X2 + 2/3.X3 + 1/2 17.44/19.08 [plus](X1,X2) = X1 + X2 + 3 17.44/19.08 [0] = 1 17.44/19.08 [empty] = 0 17.44/19.08 [false] = 1/3 17.44/19.08 [s](X) = 0 17.44/19.08 [singl](X) = 3/2.X.X + 1/3.X + 2 17.44/19.08 [true] = 1 17.44/19.08 [APP](X1,X2) = 1/3.X1.X2 + 1/3.X1 + 1/3.X2 17.44/19.08 [EQ](X1,X2) = 0 17.44/19.08 [IF](X1,X2,X3) = 0 17.44/19.08 [PLUS](X1,X2) = 0 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 SCC Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Strongly Connected Components: 17.44/19.08 ->->Cycle: 17.44/19.08 ->->-> Pairs: 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> FAxioms: 17.44/19.08 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) -> app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) -> plus(x5,x4) 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) -> APP(x5,x4) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 ->->-> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 Reduction Pairs Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(app(x,app(empty,z)),x4) -> APP(app(empty,z),x4) 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Usable Equations: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> Usable Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Interpretation type: 17.44/19.08 Simple mixed 17.44/19.08 ->Coefficients: 17.44/19.08 All rationals 17.44/19.08 ->Dimension: 17.44/19.08 1 17.44/19.08 ->Bound: 17.44/19.08 3 17.44/19.08 ->Interpretation: 17.44/19.08 17.44/19.08 [app](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1 17.44/19.08 [eq](X1,X2) = 2.X1.X2 + X2 + 1/2 17.44/19.08 [if](X1,X2,X3) = 2/3.X1 + 3/2.X2 + 2.X3 + 3 17.44/19.08 [plus](X1,X2) = X1 + X2 + 2 17.44/19.08 [0] = 3 17.44/19.08 [empty] = 0 17.44/19.08 [false] = 0 17.44/19.08 [s](X) = 3.X 17.44/19.08 [singl](X) = X + 3 17.44/19.08 [true] = 1/2 17.44/19.08 [APP](X1,X2) = 1/2.X1.X2 + 1/2.X1 + 1/2.X2 17.44/19.08 [EQ](X1,X2) = 0 17.44/19.08 [IF](X1,X2,X3) = 0 17.44/19.08 [PLUS](X1,X2) = 0 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 SCC Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Strongly Connected Components: 17.44/19.08 ->->Cycle: 17.44/19.08 ->->-> Pairs: 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> FAxioms: 17.44/19.08 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) -> app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) -> plus(x5,x4) 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) -> APP(x5,x4) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 ->->-> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 Reduction Pairs Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(app(x,plus(y,z)),x4) -> APP(plus(app(x,y),app(x,z)),x4) 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Usable Equations: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> Usable Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Interpretation type: 17.44/19.08 Simple mixed 17.44/19.08 ->Coefficients: 17.44/19.08 All rationals 17.44/19.08 ->Dimension: 17.44/19.08 1 17.44/19.08 ->Bound: 17.44/19.08 3 17.44/19.08 ->Interpretation: 17.44/19.08 17.44/19.08 [app](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 1 17.44/19.08 [eq](X1,X2) = 2 17.44/19.08 [if](X1,X2,X3) = 3.X1.X2 + 2/3.X1.X3 + X2.X3 + 1/2.X2 + 3/2.X3 + 2/3 17.44/19.08 [plus](X1,X2) = X1 + X2 + 3 17.44/19.08 [0] = 1 17.44/19.08 [empty] = 0 17.44/19.08 [false] = 0 17.44/19.08 [s](X) = 1/3.X + 3/2 17.44/19.08 [singl](X) = 2.X + 3 17.44/19.08 [true] = 2 17.44/19.08 [APP](X1,X2) = 1/2.X1.X2 + 1/2.X1 + 1/2.X2 17.44/19.08 [EQ](X1,X2) = 0 17.44/19.08 [IF](X1,X2,X3) = 0 17.44/19.08 [PLUS](X1,X2) = 0 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 SCC Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Strongly Connected Components: 17.44/19.08 ->->Cycle: 17.44/19.08 ->->-> Pairs: 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> FAxioms: 17.44/19.08 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) -> app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) -> plus(x5,x4) 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) -> APP(x5,x4) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 ->->-> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 Reduction Pairs Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(app(x,empty),x4) -> APP(empty,x4) 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Usable Equations: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> Usable Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Interpretation type: 17.44/19.08 Simple mixed 17.44/19.08 ->Coefficients: 17.44/19.08 All rationals 17.44/19.08 ->Dimension: 17.44/19.08 1 17.44/19.08 ->Bound: 17.44/19.08 3 17.44/19.08 ->Interpretation: 17.44/19.08 17.44/19.08 [app](X1,X2) = 3/2.X1.X2 + 3/2.X1 + 3/2.X2 + 1/2 17.44/19.08 [eq](X1,X2) = 2 17.44/19.08 [if](X1,X2,X3) = 2.X1.X2 + 2.X1.X3 + 1/3.X2.X3 + 2/3.X1 + 1/2.X2 + 3.X3 17.44/19.08 [plus](X1,X2) = X1 + X2 + 3/2 17.44/19.08 [0] = 2 17.44/19.08 [empty] = 1/2 17.44/19.08 [false] = 2/3 17.44/19.08 [s](X) = 1/2.X 17.44/19.08 [singl](X) = 3.X + 3 17.44/19.08 [true] = 1/2 17.44/19.08 [APP](X1,X2) = 1/3.X1.X2 + 1/3.X1 + 1/3.X2 17.44/19.08 [EQ](X1,X2) = 0 17.44/19.08 [IF](X1,X2,X3) = 0 17.44/19.08 [PLUS](X1,X2) = 0 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 SCC Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Strongly Connected Components: 17.44/19.08 ->->Cycle: 17.44/19.08 ->->-> Pairs: 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> FAxioms: 17.44/19.08 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) -> app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) -> plus(x5,x4) 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) -> APP(x5,x4) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 ->->-> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 Reduction Pairs Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Usable Equations: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> Usable Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,x5) 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Interpretation type: 17.44/19.08 Simple mixed 17.44/19.08 ->Coefficients: 17.44/19.08 All rationals 17.44/19.08 ->Dimension: 17.44/19.08 1 17.44/19.08 ->Bound: 17.44/19.08 3 17.44/19.08 ->Interpretation: 17.44/19.08 17.44/19.08 [app](X1,X2) = 2/3.X1.X2 + 2.X1 + 2.X2 + 3 17.44/19.08 [eq](X1,X2) = 3 17.44/19.08 [if](X1,X2,X3) = 3.X1.X2.X3 + 1/3.X1.X3 + 3/2.X2.X3 + 2/3.X1 + 3/2.X2 + 3.X3 17.44/19.08 [plus](X1,X2) = X1 + X2 + 3 17.44/19.08 [0] = 3 17.44/19.08 [empty] = 0 17.44/19.08 [false] = 3/2 17.44/19.08 [s](X) = 2/3 17.44/19.08 [singl](X) = 1/3.X + 3 17.44/19.08 [true] = 3 17.44/19.08 [APP](X1,X2) = 1/3.X1.X2 + X1 + X2 17.44/19.08 [EQ](X1,X2) = 0 17.44/19.08 [IF](X1,X2,X3) = 0 17.44/19.08 [PLUS](X1,X2) = 0 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 SCC Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Strongly Connected Components: 17.44/19.08 ->->Cycle: 17.44/19.08 ->->-> Pairs: 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> FAxioms: 17.44/19.08 app(app(x4,x5),x6) -> app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) -> app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) -> plus(x5,x4) 17.44/19.08 APP(app(x4,x5),x6) -> APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) -> APP(x5,x4) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 ->->-> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 Reduction Pairs Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 APP(x,app(plus(y,z),t)) -> APP(plus(app(x,y),app(x,z)),t) 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Usable Equations: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> Usable Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Interpretation type: 17.44/19.08 Simple mixed 17.44/19.08 ->Coefficients: 17.44/19.08 All rationals 17.44/19.08 ->Dimension: 17.44/19.08 1 17.44/19.08 ->Bound: 17.44/19.08 3 17.44/19.08 ->Interpretation: 17.44/19.08 17.44/19.08 [app](X1,X2) = 3.X1.X2 + 2.X1 + 2.X2 + 2/3 17.44/19.08 [eq](X1,X2) = X2 + 1/3 17.44/19.08 [if](X1,X2,X3) = 1/3.X1.X2 + 3.X2.X3 + 1/3.X2 + X3 17.44/19.08 [plus](X1,X2) = X1 + X2 + 3 17.44/19.08 [0] = 2 17.44/19.08 [empty] = 1/2 17.44/19.08 [false] = 0 17.44/19.08 [s](X) = 3.X 17.44/19.08 [singl](X) = 2.X.X + 3.X 17.44/19.08 [true] = 2 17.44/19.08 [APP](X1,X2) = X1.X2 + 2/3.X1 + 2/3.X2 17.44/19.08 [EQ](X1,X2) = 0 17.44/19.08 [IF](X1,X2,X3) = 0 17.44/19.08 [PLUS](X1,X2) = 0 17.44/19.08 17.44/19.08 Problem 1.3: 17.44/19.08 17.44/19.08 SCC Processor: 17.44/19.08 -> FAxioms: 17.44/19.08 APP(app(x4,x5),x6) = APP(x4,app(x5,x6)) 17.44/19.08 APP(x4,x5) = APP(x5,x4) 17.44/19.08 -> Pairs: 17.44/19.08 Empty 17.44/19.08 -> EAxioms: 17.44/19.08 app(app(x4,x5),x6) = app(x4,app(x5,x6)) 17.44/19.08 app(x4,x5) = app(x5,x4) 17.44/19.08 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 17.44/19.08 plus(x4,x5) = plus(x5,x4) 17.44/19.08 -> Rules: 17.44/19.08 app(singl(x),singl(y)) -> if(eq(x,y),singl(x),empty) 17.44/19.08 app(x,app(plus(y,z),t)) -> app(plus(app(x,y),app(x,z)),t) 17.44/19.08 app(x,app(empty,z)) -> app(empty,z) 17.44/19.08 app(x,plus(y,z)) -> plus(app(x,y),app(x,z)) 17.44/19.08 app(x,empty) -> empty 17.44/19.08 eq(0,0) -> true 17.44/19.08 eq(0,s(x)) -> false 17.44/19.08 eq(s(x),s(y)) -> eq(x,y) 17.44/19.08 if(false,x,y) -> y 17.44/19.08 if(true,x,y) -> x 17.44/19.08 plus(empty,x) -> x 17.44/19.08 -> SRules: 17.44/19.08 APP(x4,app(x5,x6)) -> APP(x5,x6) 17.44/19.08 ->Strongly Connected Components: 17.44/19.08 There is no strongly connected component 17.44/19.08 17.44/19.08 The problem is finite. 17.44/19.08 EOF