0.00/0.41 YES 0.00/0.41 0.00/0.41 Problem 1: 0.00/0.41 0.00/0.41 (VAR x y) 0.00/0.41 (THEORY 0.00/0.41 (C gcd)) 0.00/0.41 (RULES 0.00/0.41 gcd(0,y) -> y 0.00/0.41 gcd(s(x),0) -> s(x) 0.00/0.41 gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y)) 0.00/0.41 if_gcd(false,s(x),s(y)) -> gcd(minus(y,x),s(x)) 0.00/0.41 if_gcd(true,s(x),s(y)) -> gcd(minus(x,y),s(y)) 0.00/0.41 if_minus(false,s(x),y) -> s(minus(x,y)) 0.00/0.41 if_minus(true,s(x),y) -> 0 0.00/0.41 le(0,y) -> true 0.00/0.41 le(s(x),0) -> false 0.00/0.41 le(s(x),s(y)) -> le(x,y) 0.00/0.41 minus(0,y) -> 0 0.00/0.41 minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) 0.00/0.41 ) 0.00/0.41 0.00/0.41 Problem 1: 0.00/0.41 0.00/0.41 Dependency Pairs Processor: 0.00/0.41 -> FAxioms: 0.00/0.41 GCD(x2,x3) = GCD(x3,x2) 0.00/0.41 -> Pairs: 0.00/0.41 GCD(s(x),s(y)) -> IF_GCD(le(y,x),s(x),s(y)) 0.00/0.41 GCD(s(x),s(y)) -> LE(y,x) 0.00/0.41 IF_GCD(false,s(x),s(y)) -> GCD(minus(y,x),s(x)) 0.00/0.41 IF_GCD(false,s(x),s(y)) -> MINUS(y,x) 0.00/0.41 IF_GCD(true,s(x),s(y)) -> GCD(minus(x,y),s(y)) 0.00/0.41 IF_GCD(true,s(x),s(y)) -> MINUS(x,y) 0.00/0.41 IF_MINUS(false,s(x),y) -> MINUS(x,y) 0.00/0.41 LE(s(x),s(y)) -> LE(x,y) 0.00/0.41 MINUS(s(x),y) -> IF_MINUS(le(s(x),y),s(x),y) 0.00/0.41 MINUS(s(x),y) -> LE(s(x),y) 0.00/0.41 -> EAxioms: 0.00/0.41 gcd(x2,x3) = gcd(x3,x2) 0.00/0.41 -> Rules: 0.00/0.41 gcd(0,y) -> y 0.00/0.41 gcd(s(x),0) -> s(x) 0.00/0.41 gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y)) 0.00/0.41 if_gcd(false,s(x),s(y)) -> gcd(minus(y,x),s(x)) 0.00/0.41 if_gcd(true,s(x),s(y)) -> gcd(minus(x,y),s(y)) 0.00/0.41 if_minus(false,s(x),y) -> s(minus(x,y)) 0.00/0.41 if_minus(true,s(x),y) -> 0 0.00/0.41 le(0,y) -> true 0.00/0.41 le(s(x),0) -> false 0.00/0.41 le(s(x),s(y)) -> le(x,y) 0.00/0.41 minus(0,y) -> 0 0.00/0.41 minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) 0.00/0.41 -> SRules: 0.00/0.41 Empty 0.00/0.41 0.00/0.41 Problem 1: 0.00/0.41 0.00/0.41 SCC Processor: 0.00/0.41 -> FAxioms: 0.00/0.41 GCD(x2,x3) = GCD(x3,x2) 0.00/0.41 -> Pairs: 0.00/0.41 GCD(s(x),s(y)) -> IF_GCD(le(y,x),s(x),s(y)) 0.00/0.41 GCD(s(x),s(y)) -> LE(y,x) 0.00/0.41 IF_GCD(false,s(x),s(y)) -> GCD(minus(y,x),s(x)) 0.00/0.41 IF_GCD(false,s(x),s(y)) -> MINUS(y,x) 0.00/0.41 IF_GCD(true,s(x),s(y)) -> GCD(minus(x,y),s(y)) 0.00/0.41 IF_GCD(true,s(x),s(y)) -> MINUS(x,y) 0.00/0.41 IF_MINUS(false,s(x),y) -> MINUS(x,y) 0.00/0.41 LE(s(x),s(y)) -> LE(x,y) 0.00/0.41 MINUS(s(x),y) -> IF_MINUS(le(s(x),y),s(x),y) 0.00/0.41 MINUS(s(x),y) -> LE(s(x),y) 0.00/0.41 -> EAxioms: 0.00/0.41 gcd(x2,x3) = gcd(x3,x2) 0.00/0.41 -> Rules: 0.00/0.41 gcd(0,y) -> y 0.00/0.41 gcd(s(x),0) -> s(x) 0.00/0.41 gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y)) 0.00/0.41 if_gcd(false,s(x),s(y)) -> gcd(minus(y,x),s(x)) 0.00/0.41 if_gcd(true,s(x),s(y)) -> gcd(minus(x,y),s(y)) 0.00/0.41 if_minus(false,s(x),y) -> s(minus(x,y)) 0.00/0.41 if_minus(true,s(x),y) -> 0 0.00/0.41 le(0,y) -> true 0.00/0.41 le(s(x),0) -> false 0.00/0.41 le(s(x),s(y)) -> le(x,y) 0.00/0.41 minus(0,y) -> 0 0.00/0.41 minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) 0.00/0.41 -> SRules: 0.00/0.41 Empty 0.00/0.41 ->Strongly Connected Components: 0.00/0.41 ->->Cycle: 0.00/0.41 ->->-> Pairs: 0.00/0.41 LE(s(x),s(y)) -> LE(x,y) 0.00/0.41 -> FAxioms: 0.00/0.41 gcd(x2,x3) -> gcd(x3,x2) 0.00/0.41 -> EAxioms: 0.00/0.41 gcd(x2,x3) = gcd(x3,x2) 0.00/0.41 ->->-> Rules: 0.00/0.41 gcd(0,y) -> y 0.00/0.41 gcd(s(x),0) -> s(x) 0.00/0.41 gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y)) 0.00/0.41 if_gcd(false,s(x),s(y)) -> gcd(minus(y,x),s(x)) 0.00/0.41 if_gcd(true,s(x),s(y)) -> gcd(minus(x,y),s(y)) 0.00/0.41 if_minus(false,s(x),y) -> s(minus(x,y)) 0.00/0.41 if_minus(true,s(x),y) -> 0 0.00/0.41 le(0,y) -> true 0.00/0.41 le(s(x),0) -> false 0.00/0.41 le(s(x),s(y)) -> le(x,y) 0.00/0.41 minus(0,y) -> 0 0.00/0.41 minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) 0.00/0.41 -> SRules: 0.00/0.41 Empty 0.00/0.41 ->->Cycle: 0.00/0.41 ->->-> Pairs: 0.00/0.41 IF_MINUS(false,s(x),y) -> MINUS(x,y) 0.00/0.41 MINUS(s(x),y) -> IF_MINUS(le(s(x),y),s(x),y) 0.00/0.41 -> FAxioms: 0.00/0.41 gcd(x2,x3) -> gcd(x3,x2) 0.00/0.41 -> EAxioms: 0.00/0.41 gcd(x2,x3) = gcd(x3,x2) 0.00/0.41 ->->-> Rules: 0.00/0.41 gcd(0,y) -> y 0.00/0.41 gcd(s(x),0) -> s(x) 0.00/0.41 gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y)) 0.00/0.41 if_gcd(false,s(x),s(y)) -> gcd(minus(y,x),s(x)) 0.00/0.41 if_gcd(true,s(x),s(y)) -> gcd(minus(x,y),s(y)) 0.00/0.41 if_minus(false,s(x),y) -> s(minus(x,y)) 0.00/0.41 if_minus(true,s(x),y) -> 0 0.00/0.41 le(0,y) -> true 0.00/0.41 le(s(x),0) -> false 0.00/0.41 le(s(x),s(y)) -> le(x,y) 0.00/0.41 minus(0,y) -> 0 0.00/0.41 minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) 0.00/0.41 -> SRules: 0.00/0.41 Empty 0.00/0.41 ->->Cycle: 0.00/0.41 ->->-> Pairs: 0.00/0.41 GCD(s(x),s(y)) -> IF_GCD(le(y,x),s(x),s(y)) 0.00/0.41 IF_GCD(false,s(x),s(y)) -> GCD(minus(y,x),s(x)) 0.00/0.41 IF_GCD(true,s(x),s(y)) -> GCD(minus(x,y),s(y)) 0.00/0.41 -> FAxioms: 0.00/0.41 gcd(x2,x3) -> gcd(x3,x2) 0.00/0.41 GCD(x2,x3) -> GCD(x3,x2) 0.00/0.41 -> EAxioms: 0.00/0.41 gcd(x2,x3) = gcd(x3,x2) 0.00/0.41 ->->-> Rules: 0.00/0.41 gcd(0,y) -> y 0.00/0.41 gcd(s(x),0) -> s(x) 0.00/0.41 gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y)) 0.00/0.41 if_gcd(false,s(x),s(y)) -> gcd(minus(y,x),s(x)) 0.00/0.41 if_gcd(true,s(x),s(y)) -> gcd(minus(x,y),s(y)) 0.00/0.41 if_minus(false,s(x),y) -> s(minus(x,y)) 0.00/0.41 if_minus(true,s(x),y) -> 0 0.00/0.41 le(0,y) -> true 0.00/0.41 le(s(x),0) -> false 0.00/0.41 le(s(x),s(y)) -> le(x,y) 0.00/0.41 minus(0,y) -> 0 0.00/0.41 minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) 0.00/0.41 -> SRules: 0.00/0.41 Empty 0.00/0.41 0.00/0.41 0.00/0.41 The problem is decomposed in 3 subproblems. 0.00/0.41 0.00/0.41 Problem 1.1: 0.00/0.41 0.00/0.41 Subterm Processor: 0.00/0.41 -> FAxioms: 0.00/0.41 Empty 0.00/0.41 -> Pairs: 0.00/0.41 LE(s(x),s(y)) -> LE(x,y) 0.00/0.41 -> EAxioms: 0.00/0.41 gcd(x2,x3) = gcd(x3,x2) 0.00/0.41 -> Rules: 0.00/0.41 gcd(0,y) -> y 0.00/0.41 gcd(s(x),0) -> s(x) 0.00/0.41 gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y)) 0.00/0.41 if_gcd(false,s(x),s(y)) -> gcd(minus(y,x),s(x)) 0.00/0.41 if_gcd(true,s(x),s(y)) -> gcd(minus(x,y),s(y)) 0.00/0.41 if_minus(false,s(x),y) -> s(minus(x,y)) 0.00/0.41 if_minus(true,s(x),y) -> 0 0.00/0.41 le(0,y) -> true 0.00/0.41 le(s(x),0) -> false 0.00/0.41 le(s(x),s(y)) -> le(x,y) 0.00/0.41 minus(0,y) -> 0 0.00/0.41 minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) 0.00/0.41 -> SRules: 0.00/0.41 Empty 0.00/0.41 ->Projection: 0.00/0.41 pi(LE) = [1] 0.00/0.41 0.00/0.41 Problem 1.1: 0.00/0.41 0.00/0.41 SCC Processor: 0.00/0.41 -> FAxioms: 0.00/0.41 Empty 0.00/0.41 -> Pairs: 0.00/0.41 Empty 0.00/0.41 -> EAxioms: 0.00/0.41 gcd(x2,x3) = gcd(x3,x2) 0.00/0.41 -> Rules: 0.00/0.41 gcd(0,y) -> y 0.00/0.41 gcd(s(x),0) -> s(x) 0.00/0.41 gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y)) 0.00/0.41 if_gcd(false,s(x),s(y)) -> gcd(minus(y,x),s(x)) 0.00/0.41 if_gcd(true,s(x),s(y)) -> gcd(minus(x,y),s(y)) 0.00/0.41 if_minus(false,s(x),y) -> s(minus(x,y)) 0.00/0.41 if_minus(true,s(x),y) -> 0 0.00/0.41 le(0,y) -> true 0.00/0.41 le(s(x),0) -> false 0.00/0.41 le(s(x),s(y)) -> le(x,y) 0.00/0.41 minus(0,y) -> 0 0.00/0.41 minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) 0.00/0.41 -> SRules: 0.00/0.41 Empty 0.00/0.41 ->Strongly Connected Components: 0.00/0.41 There is no strongly connected component 0.00/0.41 0.00/0.41 The problem is finite. 0.00/0.41 0.00/0.41 Problem 1.2: 0.00/0.41 0.00/0.41 Subterm Processor: 0.00/0.41 -> FAxioms: 0.00/0.41 Empty 0.00/0.41 -> Pairs: 0.00/0.41 IF_MINUS(false,s(x),y) -> MINUS(x,y) 0.00/0.41 MINUS(s(x),y) -> IF_MINUS(le(s(x),y),s(x),y) 0.00/0.41 -> EAxioms: 0.00/0.41 gcd(x2,x3) = gcd(x3,x2) 0.00/0.41 -> Rules: 0.00/0.41 gcd(0,y) -> y 0.00/0.41 gcd(s(x),0) -> s(x) 0.00/0.41 gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y)) 0.00/0.41 if_gcd(false,s(x),s(y)) -> gcd(minus(y,x),s(x)) 0.00/0.41 if_gcd(true,s(x),s(y)) -> gcd(minus(x,y),s(y)) 0.00/0.41 if_minus(false,s(x),y) -> s(minus(x,y)) 0.00/0.41 if_minus(true,s(x),y) -> 0 0.00/0.41 le(0,y) -> true 0.00/0.41 le(s(x),0) -> false 0.00/0.41 le(s(x),s(y)) -> le(x,y) 0.00/0.41 minus(0,y) -> 0 0.00/0.41 minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) 0.00/0.41 -> SRules: 0.00/0.41 Empty 0.00/0.41 ->Projection: 0.00/0.41 pi(IF_MINUS) = [2] 0.00/0.41 pi(MINUS) = [1] 0.00/0.41 0.00/0.41 Problem 1.2: 0.00/0.41 0.00/0.41 SCC Processor: 0.00/0.41 -> FAxioms: 0.00/0.41 Empty 0.00/0.41 -> Pairs: 0.00/0.41 MINUS(s(x),y) -> IF_MINUS(le(s(x),y),s(x),y) 0.00/0.41 -> EAxioms: 0.00/0.41 gcd(x2,x3) = gcd(x3,x2) 0.00/0.41 -> Rules: 0.00/0.41 gcd(0,y) -> y 0.00/0.41 gcd(s(x),0) -> s(x) 0.00/0.41 gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y)) 0.00/0.41 if_gcd(false,s(x),s(y)) -> gcd(minus(y,x),s(x)) 0.00/0.41 if_gcd(true,s(x),s(y)) -> gcd(minus(x,y),s(y)) 0.00/0.41 if_minus(false,s(x),y) -> s(minus(x,y)) 0.00/0.41 if_minus(true,s(x),y) -> 0 0.00/0.41 le(0,y) -> true 0.00/0.41 le(s(x),0) -> false 0.00/0.41 le(s(x),s(y)) -> le(x,y) 0.00/0.41 minus(0,y) -> 0 0.00/0.41 minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) 0.00/0.41 -> SRules: 0.00/0.41 Empty 0.00/0.41 ->Strongly Connected Components: 0.00/0.41 There is no strongly connected component 0.00/0.41 0.00/0.41 The problem is finite. 0.00/0.41 0.00/0.41 Problem 1.3: 0.00/0.41 0.00/0.41 Reduction Pairs Processor: 0.00/0.41 -> FAxioms: 0.00/0.41 GCD(x2,x3) = GCD(x3,x2) 0.00/0.41 -> Pairs: 0.00/0.41 GCD(s(x),s(y)) -> IF_GCD(le(y,x),s(x),s(y)) 0.00/0.41 IF_GCD(false,s(x),s(y)) -> GCD(minus(y,x),s(x)) 0.00/0.41 IF_GCD(true,s(x),s(y)) -> GCD(minus(x,y),s(y)) 0.00/0.41 -> EAxioms: 0.00/0.41 gcd(x2,x3) = gcd(x3,x2) 0.00/0.41 -> Usable Equations: 0.00/0.41 Empty 0.00/0.41 -> Rules: 0.00/0.41 gcd(0,y) -> y 0.00/0.41 gcd(s(x),0) -> s(x) 0.00/0.41 gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y)) 0.00/0.41 if_gcd(false,s(x),s(y)) -> gcd(minus(y,x),s(x)) 0.00/0.41 if_gcd(true,s(x),s(y)) -> gcd(minus(x,y),s(y)) 0.00/0.41 if_minus(false,s(x),y) -> s(minus(x,y)) 0.00/0.41 if_minus(true,s(x),y) -> 0 0.00/0.41 le(0,y) -> true 0.00/0.41 le(s(x),0) -> false 0.00/0.41 le(s(x),s(y)) -> le(x,y) 0.00/0.41 minus(0,y) -> 0 0.00/0.41 minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) 0.00/0.41 -> Usable Rules: 0.00/0.41 if_minus(false,s(x),y) -> s(minus(x,y)) 0.00/0.41 if_minus(true,s(x),y) -> 0 0.00/0.41 le(0,y) -> true 0.00/0.41 le(s(x),0) -> false 0.00/0.41 le(s(x),s(y)) -> le(x,y) 0.00/0.41 minus(0,y) -> 0 0.00/0.41 minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) 0.00/0.41 -> SRules: 0.00/0.41 Empty 0.00/0.41 ->Interpretation type: 0.00/0.41 Linear 0.00/0.41 ->Coefficients: 0.00/0.41 Natural Numbers 0.00/0.41 ->Dimension: 0.00/0.41 1 0.00/0.41 ->Bound: 0.00/0.41 2 0.00/0.41 ->Interpretation: 0.00/0.41 0.00/0.41 [gcd](X1,X2) = 0 0.00/0.41 [if_gcd](X1,X2,X3) = 0 0.00/0.41 [if_minus](X1,X2,X3) = 2.X2 0.00/0.41 [le](X1,X2) = 2 0.00/0.41 [minus](X1,X2) = 2.X1 0.00/0.41 [0] = 0 0.00/0.41 [false] = 2 0.00/0.41 [s](X) = 2.X + 1 0.00/0.41 [true] = 2 0.00/0.41 [GCD](X1,X2) = X1 + X2 + 2 0.00/0.41 [IF_GCD](X1,X2,X3) = X2 + X3 + 1 0.00/0.41 [IF_MINUS](X1,X2,X3) = 0 0.00/0.41 [LE](X1,X2) = 0 0.00/0.41 [MINUS](X1,X2) = 0 0.00/0.41 0.00/0.41 Problem 1.3: 0.00/0.41 0.00/0.41 SCC Processor: 0.00/0.41 -> FAxioms: 0.00/0.41 GCD(x2,x3) = GCD(x3,x2) 0.00/0.41 -> Pairs: 0.00/0.41 IF_GCD(false,s(x),s(y)) -> GCD(minus(y,x),s(x)) 0.00/0.41 IF_GCD(true,s(x),s(y)) -> GCD(minus(x,y),s(y)) 0.00/0.41 -> EAxioms: 0.00/0.41 gcd(x2,x3) = gcd(x3,x2) 0.00/0.41 -> Rules: 0.00/0.41 gcd(0,y) -> y 0.00/0.41 gcd(s(x),0) -> s(x) 0.00/0.41 gcd(s(x),s(y)) -> if_gcd(le(y,x),s(x),s(y)) 0.00/0.41 if_gcd(false,s(x),s(y)) -> gcd(minus(y,x),s(x)) 0.00/0.41 if_gcd(true,s(x),s(y)) -> gcd(minus(x,y),s(y)) 0.00/0.41 if_minus(false,s(x),y) -> s(minus(x,y)) 0.00/0.41 if_minus(true,s(x),y) -> 0 0.00/0.41 le(0,y) -> true 0.00/0.41 le(s(x),0) -> false 0.00/0.41 le(s(x),s(y)) -> le(x,y) 0.00/0.41 minus(0,y) -> 0 0.00/0.41 minus(s(x),y) -> if_minus(le(s(x),y),s(x),y) 0.00/0.41 -> SRules: 0.00/0.41 Empty 0.00/0.41 ->Strongly Connected Components: 0.00/0.41 There is no strongly connected component 0.00/0.41 0.00/0.41 The problem is finite. 0.00/0.44 EOF