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