5.75/2.45 MAYBE 5.75/2.46 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.75/2.46 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.75/2.46 5.75/2.46 5.75/2.46 Termination of the given ETRS could not be shown: 5.75/2.46 5.75/2.46 (0) ETRS 5.75/2.46 (1) EquationalDependencyPairsProof [EQUIVALENT, 0 ms] 5.75/2.46 (2) EDP 5.75/2.46 (3) EDependencyGraphProof [EQUIVALENT, 0 ms] 5.75/2.46 (4) AND 5.75/2.46 (5) EDP 5.75/2.46 (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 5.75/2.46 (7) EDP 5.75/2.46 (8) EUsableRulesReductionPairsProof [EQUIVALENT, 10 ms] 5.75/2.46 (9) EDP 5.75/2.46 (10) PisEmptyProof [EQUIVALENT, 0 ms] 5.75/2.46 (11) YES 5.75/2.46 (12) EDP 5.75/2.46 (13) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 5.75/2.46 (14) EDP 5.75/2.46 (15) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 5.75/2.46 (16) EDP 5.75/2.46 (17) PisEmptyProof [EQUIVALENT, 0 ms] 5.75/2.46 (18) YES 5.75/2.46 (19) EDP 5.75/2.46 (20) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 5.75/2.46 (21) EDP 5.75/2.46 (22) EUsableRulesProof [EQUIVALENT, 0 ms] 5.75/2.46 (23) EDP 5.75/2.46 (24) EDP 5.75/2.46 (25) EDP 5.75/2.46 (26) EDP 5.75/2.46 5.75/2.46 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (0) 5.75/2.46 Obligation: 5.75/2.46 Equational rewrite system: 5.75/2.46 The TRS R consists of the following rules: 5.75/2.46 5.75/2.46 p(s(N)) -> N 5.75/2.46 +(N, 0) -> N 5.75/2.46 +(s(N), s(M)) -> s(s(+(N, M))) 5.75/2.46 *(N, 0) -> 0 5.75/2.46 *(s(N), s(M)) -> s(+(N, +(M, *(N, M)))) 5.75/2.46 gt(0, M) -> False 5.75/2.46 gt(NzN, 0) -> u_4(is_NzNat(NzN)) 5.75/2.46 u_4(True) -> True 5.75/2.46 is_NzNat(0) -> False 5.75/2.46 is_NzNat(s(N)) -> True 5.75/2.46 gt(s(N), s(M)) -> gt(N, M) 5.75/2.46 lt(N, M) -> gt(M, N) 5.75/2.46 d(0, N) -> N 5.75/2.46 d(s(N), s(M)) -> d(N, M) 5.75/2.46 quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM) 5.75/2.46 u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM) 5.75/2.46 u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM)) 5.75/2.46 quot(NzM, NzM) -> u_01(is_NzNat(NzM)) 5.75/2.46 u_01(True) -> s(0) 5.75/2.46 quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N) 5.75/2.46 u_21(True, NzM, N) -> u_2(gt(NzM, N)) 5.75/2.46 u_2(True) -> 0 5.75/2.46 gcd(0, N) -> 0 5.75/2.46 gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM) 5.75/2.46 u_02(True, NzM) -> NzM 5.75/2.46 gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM) 5.75/2.46 5.75/2.46 The set E consists of the following equations: 5.75/2.46 5.75/2.46 *(x, y) == *(y, x) 5.75/2.46 +(x, y) == +(y, x) 5.75/2.46 d(x, y) == d(y, x) 5.75/2.46 gcd(x, y) == gcd(y, x) 5.75/2.46 5.75/2.46 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (1) EquationalDependencyPairsProof (EQUIVALENT) 5.75/2.46 Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: 5.75/2.46 The TRS P consists of the following rules: 5.75/2.46 5.75/2.46 +^1(s(N), s(M)) -> +^1(N, M) 5.75/2.46 *^1(s(N), s(M)) -> +^1(N, +(M, *(N, M))) 5.75/2.46 *^1(s(N), s(M)) -> +^1(M, *(N, M)) 5.75/2.46 *^1(s(N), s(M)) -> *^1(N, M) 5.75/2.46 GT(NzN, 0) -> U_4(is_NzNat(NzN)) 5.75/2.46 GT(NzN, 0) -> IS_NZNAT(NzN) 5.75/2.46 GT(s(N), s(M)) -> GT(N, M) 5.75/2.46 LT(N, M) -> GT(M, N) 5.75/2.46 D(s(N), s(M)) -> D(N, M) 5.75/2.46 QUOT(N, NzM) -> U_11(is_NzNat(NzM), N, NzM) 5.75/2.46 QUOT(N, NzM) -> IS_NZNAT(NzM) 5.75/2.46 U_11(True, N, NzM) -> U_1(gt(N, NzM), N, NzM) 5.75/2.46 U_11(True, N, NzM) -> GT(N, NzM) 5.75/2.46 U_1(True, N, NzM) -> QUOT(d(N, NzM), NzM) 5.75/2.46 U_1(True, N, NzM) -> D(N, NzM) 5.75/2.46 QUOT(NzM, NzM) -> U_01(is_NzNat(NzM)) 5.75/2.46 QUOT(NzM, NzM) -> IS_NZNAT(NzM) 5.75/2.46 QUOT(N, NzM) -> U_21(is_NzNat(NzM), NzM, N) 5.75/2.46 U_21(True, NzM, N) -> U_2(gt(NzM, N)) 5.75/2.46 U_21(True, NzM, N) -> GT(NzM, N) 5.75/2.46 GCD(NzM, NzM) -> U_02(is_NzNat(NzM), NzM) 5.75/2.46 GCD(NzM, NzM) -> IS_NZNAT(NzM) 5.75/2.46 GCD(NzN, NzM) -> U_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 GCD(NzN, NzM) -> IS_NZNAT(NzN) 5.75/2.46 GCD(NzN, NzM) -> IS_NZNAT(NzM) 5.75/2.46 U_31(True, True, NzN, NzM) -> U_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 U_31(True, True, NzN, NzM) -> GT(NzN, NzM) 5.75/2.46 U_3(True, NzN, NzM) -> GCD(d(NzN, NzM), NzM) 5.75/2.46 U_3(True, NzN, NzM) -> D(NzN, NzM) 5.75/2.46 5.75/2.46 The TRS R consists of the following rules: 5.75/2.46 5.75/2.46 p(s(N)) -> N 5.75/2.46 +(N, 0) -> N 5.75/2.46 +(s(N), s(M)) -> s(s(+(N, M))) 5.75/2.46 *(N, 0) -> 0 5.75/2.46 *(s(N), s(M)) -> s(+(N, +(M, *(N, M)))) 5.75/2.46 gt(0, M) -> False 5.75/2.46 gt(NzN, 0) -> u_4(is_NzNat(NzN)) 5.75/2.46 u_4(True) -> True 5.75/2.46 is_NzNat(0) -> False 5.75/2.46 is_NzNat(s(N)) -> True 5.75/2.46 gt(s(N), s(M)) -> gt(N, M) 5.75/2.46 lt(N, M) -> gt(M, N) 5.75/2.46 d(0, N) -> N 5.75/2.46 d(s(N), s(M)) -> d(N, M) 5.75/2.46 quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM) 5.75/2.46 u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM) 5.75/2.46 u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM)) 5.75/2.46 quot(NzM, NzM) -> u_01(is_NzNat(NzM)) 5.75/2.46 u_01(True) -> s(0) 5.75/2.46 quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N) 5.75/2.46 u_21(True, NzM, N) -> u_2(gt(NzM, N)) 5.75/2.46 u_2(True) -> 0 5.75/2.46 gcd(0, N) -> 0 5.75/2.46 gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM) 5.75/2.46 u_02(True, NzM) -> NzM 5.75/2.46 gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM) 5.75/2.46 5.75/2.46 The set E consists of the following equations: 5.75/2.46 5.75/2.46 *(x, y) == *(y, x) 5.75/2.46 +(x, y) == +(y, x) 5.75/2.46 d(x, y) == d(y, x) 5.75/2.46 gcd(x, y) == gcd(y, x) 5.75/2.46 5.75/2.46 The set E# consists of the following equations: 5.75/2.46 5.75/2.46 *^1(x, y) == *^1(y, x) 5.75/2.46 +^1(x, y) == +^1(y, x) 5.75/2.46 D(x, y) == D(y, x) 5.75/2.46 GCD(x, y) == GCD(y, x) 5.75/2.46 5.75/2.46 We have to consider all minimal (P,E#,R,E)-chains 5.75/2.46 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (2) 5.75/2.46 Obligation: 5.75/2.46 The TRS P consists of the following rules: 5.75/2.46 5.75/2.46 +^1(s(N), s(M)) -> +^1(N, M) 5.75/2.46 *^1(s(N), s(M)) -> +^1(N, +(M, *(N, M))) 5.75/2.46 *^1(s(N), s(M)) -> +^1(M, *(N, M)) 5.75/2.46 *^1(s(N), s(M)) -> *^1(N, M) 5.75/2.46 GT(NzN, 0) -> U_4(is_NzNat(NzN)) 5.75/2.46 GT(NzN, 0) -> IS_NZNAT(NzN) 5.75/2.46 GT(s(N), s(M)) -> GT(N, M) 5.75/2.46 LT(N, M) -> GT(M, N) 5.75/2.46 D(s(N), s(M)) -> D(N, M) 5.75/2.46 QUOT(N, NzM) -> U_11(is_NzNat(NzM), N, NzM) 5.75/2.46 QUOT(N, NzM) -> IS_NZNAT(NzM) 5.75/2.46 U_11(True, N, NzM) -> U_1(gt(N, NzM), N, NzM) 5.75/2.46 U_11(True, N, NzM) -> GT(N, NzM) 5.75/2.46 U_1(True, N, NzM) -> QUOT(d(N, NzM), NzM) 5.75/2.46 U_1(True, N, NzM) -> D(N, NzM) 5.75/2.46 QUOT(NzM, NzM) -> U_01(is_NzNat(NzM)) 5.75/2.46 QUOT(NzM, NzM) -> IS_NZNAT(NzM) 5.75/2.46 QUOT(N, NzM) -> U_21(is_NzNat(NzM), NzM, N) 5.75/2.46 U_21(True, NzM, N) -> U_2(gt(NzM, N)) 5.75/2.46 U_21(True, NzM, N) -> GT(NzM, N) 5.75/2.46 GCD(NzM, NzM) -> U_02(is_NzNat(NzM), NzM) 5.75/2.46 GCD(NzM, NzM) -> IS_NZNAT(NzM) 5.75/2.46 GCD(NzN, NzM) -> U_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 GCD(NzN, NzM) -> IS_NZNAT(NzN) 5.75/2.46 GCD(NzN, NzM) -> IS_NZNAT(NzM) 5.75/2.46 U_31(True, True, NzN, NzM) -> U_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 U_31(True, True, NzN, NzM) -> GT(NzN, NzM) 5.75/2.46 U_3(True, NzN, NzM) -> GCD(d(NzN, NzM), NzM) 5.75/2.46 U_3(True, NzN, NzM) -> D(NzN, NzM) 5.75/2.46 5.75/2.46 The TRS R consists of the following rules: 5.75/2.46 5.75/2.46 p(s(N)) -> N 5.75/2.46 +(N, 0) -> N 5.75/2.46 +(s(N), s(M)) -> s(s(+(N, M))) 5.75/2.46 *(N, 0) -> 0 5.75/2.46 *(s(N), s(M)) -> s(+(N, +(M, *(N, M)))) 5.75/2.46 gt(0, M) -> False 5.75/2.46 gt(NzN, 0) -> u_4(is_NzNat(NzN)) 5.75/2.46 u_4(True) -> True 5.75/2.46 is_NzNat(0) -> False 5.75/2.46 is_NzNat(s(N)) -> True 5.75/2.46 gt(s(N), s(M)) -> gt(N, M) 5.75/2.46 lt(N, M) -> gt(M, N) 5.75/2.46 d(0, N) -> N 5.75/2.46 d(s(N), s(M)) -> d(N, M) 5.75/2.46 quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM) 5.75/2.46 u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM) 5.75/2.46 u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM)) 5.75/2.46 quot(NzM, NzM) -> u_01(is_NzNat(NzM)) 5.75/2.46 u_01(True) -> s(0) 5.75/2.46 quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N) 5.75/2.46 u_21(True, NzM, N) -> u_2(gt(NzM, N)) 5.75/2.46 u_2(True) -> 0 5.75/2.46 gcd(0, N) -> 0 5.75/2.46 gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM) 5.75/2.46 u_02(True, NzM) -> NzM 5.75/2.46 gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM) 5.75/2.46 5.75/2.46 The set E consists of the following equations: 5.75/2.46 5.75/2.46 *(x, y) == *(y, x) 5.75/2.46 +(x, y) == +(y, x) 5.75/2.46 d(x, y) == d(y, x) 5.75/2.46 gcd(x, y) == gcd(y, x) 5.75/2.46 5.75/2.46 The set E# consists of the following equations: 5.75/2.46 5.75/2.46 *^1(x, y) == *^1(y, x) 5.75/2.46 +^1(x, y) == +^1(y, x) 5.75/2.46 D(x, y) == D(y, x) 5.75/2.46 GCD(x, y) == GCD(y, x) 5.75/2.46 5.75/2.46 We have to consider all minimal (P,E#,R,E)-chains 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (3) EDependencyGraphProof (EQUIVALENT) 5.75/2.46 The approximation of the Equational Dependency Graph [DA_STEIN] contains 6 SCCs with 19 less nodes. 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (4) 5.75/2.46 Complex Obligation (AND) 5.75/2.46 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (5) 5.75/2.46 Obligation: 5.75/2.46 The TRS P consists of the following rules: 5.75/2.46 5.75/2.46 D(s(N), s(M)) -> D(N, M) 5.75/2.46 5.75/2.46 The TRS R consists of the following rules: 5.75/2.46 5.75/2.46 p(s(N)) -> N 5.75/2.46 +(N, 0) -> N 5.75/2.46 +(s(N), s(M)) -> s(s(+(N, M))) 5.75/2.46 *(N, 0) -> 0 5.75/2.46 *(s(N), s(M)) -> s(+(N, +(M, *(N, M)))) 5.75/2.46 gt(0, M) -> False 5.75/2.46 gt(NzN, 0) -> u_4(is_NzNat(NzN)) 5.75/2.46 u_4(True) -> True 5.75/2.46 is_NzNat(0) -> False 5.75/2.46 is_NzNat(s(N)) -> True 5.75/2.46 gt(s(N), s(M)) -> gt(N, M) 5.75/2.46 lt(N, M) -> gt(M, N) 5.75/2.46 d(0, N) -> N 5.75/2.46 d(s(N), s(M)) -> d(N, M) 5.75/2.46 quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM) 5.75/2.46 u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM) 5.75/2.46 u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM)) 5.75/2.46 quot(NzM, NzM) -> u_01(is_NzNat(NzM)) 5.75/2.46 u_01(True) -> s(0) 5.75/2.46 quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N) 5.75/2.46 u_21(True, NzM, N) -> u_2(gt(NzM, N)) 5.75/2.46 u_2(True) -> 0 5.75/2.46 gcd(0, N) -> 0 5.75/2.46 gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM) 5.75/2.46 u_02(True, NzM) -> NzM 5.75/2.46 gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM) 5.75/2.46 5.75/2.46 The set E consists of the following equations: 5.75/2.46 5.75/2.46 *(x, y) == *(y, x) 5.75/2.46 +(x, y) == +(y, x) 5.75/2.46 d(x, y) == d(y, x) 5.75/2.46 gcd(x, y) == gcd(y, x) 5.75/2.46 5.75/2.46 The set E# consists of the following equations: 5.75/2.46 5.75/2.46 *^1(x, y) == *^1(y, x) 5.75/2.46 +^1(x, y) == +^1(y, x) 5.75/2.46 D(x, y) == D(y, x) 5.75/2.46 GCD(x, y) == GCD(y, x) 5.75/2.46 5.75/2.46 We have to consider all minimal (P,E#,R,E)-chains 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (6) ESharpUsableEquationsProof (EQUIVALENT) 5.75/2.46 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 5.75/2.46 *^1(x, y) == *^1(y, x) 5.75/2.46 +^1(x, y) == +^1(y, x) 5.75/2.46 GCD(x, y) == GCD(y, x) 5.75/2.46 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (7) 5.75/2.46 Obligation: 5.75/2.46 The TRS P consists of the following rules: 5.75/2.46 5.75/2.46 D(s(N), s(M)) -> D(N, M) 5.75/2.46 5.75/2.46 The TRS R consists of the following rules: 5.75/2.46 5.75/2.46 p(s(N)) -> N 5.75/2.46 +(N, 0) -> N 5.75/2.46 +(s(N), s(M)) -> s(s(+(N, M))) 5.75/2.46 *(N, 0) -> 0 5.75/2.46 *(s(N), s(M)) -> s(+(N, +(M, *(N, M)))) 5.75/2.46 gt(0, M) -> False 5.75/2.46 gt(NzN, 0) -> u_4(is_NzNat(NzN)) 5.75/2.46 u_4(True) -> True 5.75/2.46 is_NzNat(0) -> False 5.75/2.46 is_NzNat(s(N)) -> True 5.75/2.46 gt(s(N), s(M)) -> gt(N, M) 5.75/2.46 lt(N, M) -> gt(M, N) 5.75/2.46 d(0, N) -> N 5.75/2.46 d(s(N), s(M)) -> d(N, M) 5.75/2.46 quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM) 5.75/2.46 u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM) 5.75/2.46 u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM)) 5.75/2.46 quot(NzM, NzM) -> u_01(is_NzNat(NzM)) 5.75/2.46 u_01(True) -> s(0) 5.75/2.46 quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N) 5.75/2.46 u_21(True, NzM, N) -> u_2(gt(NzM, N)) 5.75/2.46 u_2(True) -> 0 5.75/2.46 gcd(0, N) -> 0 5.75/2.46 gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM) 5.75/2.46 u_02(True, NzM) -> NzM 5.75/2.46 gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM) 5.75/2.46 5.75/2.46 The set E consists of the following equations: 5.75/2.46 5.75/2.46 *(x, y) == *(y, x) 5.75/2.46 +(x, y) == +(y, x) 5.75/2.46 d(x, y) == d(y, x) 5.75/2.46 gcd(x, y) == gcd(y, x) 5.75/2.46 5.75/2.46 The set E# consists of the following equations: 5.75/2.46 5.75/2.46 D(x, y) == D(y, x) 5.75/2.46 5.75/2.46 We have to consider all minimal (P,E#,R,E)-chains 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (8) EUsableRulesReductionPairsProof (EQUIVALENT) 5.75/2.46 By using the improved usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding improved usable rules can be oriented non-strictly, the improved usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and improved usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 5.75/2.46 5.75/2.46 The following dependency pairs can be deleted: 5.75/2.46 5.75/2.46 D(s(N), s(M)) -> D(N, M) 5.75/2.46 The following rules are removed from R: 5.75/2.46 5.75/2.46 p(s(N)) -> N 5.75/2.46 +(N, 0) -> N 5.75/2.46 +(s(N), s(M)) -> s(s(+(N, M))) 5.75/2.46 *(N, 0) -> 0 5.75/2.46 *(s(N), s(M)) -> s(+(N, +(M, *(N, M)))) 5.75/2.46 gt(0, M) -> False 5.75/2.46 gt(NzN, 0) -> u_4(is_NzNat(NzN)) 5.75/2.46 u_4(True) -> True 5.75/2.46 is_NzNat(0) -> False 5.75/2.46 is_NzNat(s(N)) -> True 5.75/2.46 gt(s(N), s(M)) -> gt(N, M) 5.75/2.46 lt(N, M) -> gt(M, N) 5.75/2.46 d(0, N) -> N 5.75/2.46 d(s(N), s(M)) -> d(N, M) 5.75/2.46 quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM) 5.75/2.46 u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM) 5.75/2.46 u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM)) 5.75/2.46 quot(NzM, NzM) -> u_01(is_NzNat(NzM)) 5.75/2.46 u_01(True) -> s(0) 5.75/2.46 quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N) 5.75/2.46 u_21(True, NzM, N) -> u_2(gt(NzM, N)) 5.75/2.46 u_2(True) -> 0 5.75/2.46 gcd(0, N) -> 0 5.75/2.46 gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM) 5.75/2.46 u_02(True, NzM) -> NzM 5.75/2.46 gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM) 5.75/2.46 The following equations are removed from E: 5.75/2.46 5.75/2.46 *(x, y) == *(y, x) 5.75/2.46 +(x, y) == +(y, x) 5.75/2.46 d(x, y) == d(y, x) 5.75/2.46 gcd(x, y) == gcd(y, x) 5.75/2.46 Used ordering: POLO with Polynomial interpretation [POLO]: 5.75/2.46 5.75/2.46 POL(D(x_1, x_2)) = 3*x_1 + 3*x_2 5.75/2.46 POL(s(x_1)) = 3*x_1 5.75/2.46 5.75/2.46 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (9) 5.75/2.46 Obligation: 5.75/2.46 P is empty. 5.75/2.46 R is empty. 5.75/2.46 E is empty. 5.75/2.46 The set E# consists of the following equations: 5.75/2.46 5.75/2.46 D(x, y) == D(y, x) 5.75/2.46 5.75/2.46 We have to consider all minimal (P,E#,R,E)-chains 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (10) PisEmptyProof (EQUIVALENT) 5.75/2.46 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (11) 5.75/2.46 YES 5.75/2.46 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (12) 5.75/2.46 Obligation: 5.75/2.46 The TRS P consists of the following rules: 5.75/2.46 5.75/2.46 GT(s(N), s(M)) -> GT(N, M) 5.75/2.46 5.75/2.46 The TRS R consists of the following rules: 5.75/2.46 5.75/2.46 p(s(N)) -> N 5.75/2.46 +(N, 0) -> N 5.75/2.46 +(s(N), s(M)) -> s(s(+(N, M))) 5.75/2.46 *(N, 0) -> 0 5.75/2.46 *(s(N), s(M)) -> s(+(N, +(M, *(N, M)))) 5.75/2.46 gt(0, M) -> False 5.75/2.46 gt(NzN, 0) -> u_4(is_NzNat(NzN)) 5.75/2.46 u_4(True) -> True 5.75/2.46 is_NzNat(0) -> False 5.75/2.46 is_NzNat(s(N)) -> True 5.75/2.46 gt(s(N), s(M)) -> gt(N, M) 5.75/2.46 lt(N, M) -> gt(M, N) 5.75/2.46 d(0, N) -> N 5.75/2.46 d(s(N), s(M)) -> d(N, M) 5.75/2.46 quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM) 5.75/2.46 u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM) 5.75/2.46 u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM)) 5.75/2.46 quot(NzM, NzM) -> u_01(is_NzNat(NzM)) 5.75/2.46 u_01(True) -> s(0) 5.75/2.46 quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N) 5.75/2.46 u_21(True, NzM, N) -> u_2(gt(NzM, N)) 5.75/2.46 u_2(True) -> 0 5.75/2.46 gcd(0, N) -> 0 5.75/2.46 gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM) 5.75/2.46 u_02(True, NzM) -> NzM 5.75/2.46 gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM) 5.75/2.46 5.75/2.46 The set E consists of the following equations: 5.75/2.46 5.75/2.46 *(x, y) == *(y, x) 5.75/2.46 +(x, y) == +(y, x) 5.75/2.46 d(x, y) == d(y, x) 5.75/2.46 gcd(x, y) == gcd(y, x) 5.75/2.46 5.75/2.46 The set E# consists of the following equations: 5.75/2.46 5.75/2.46 *^1(x, y) == *^1(y, x) 5.75/2.46 +^1(x, y) == +^1(y, x) 5.75/2.46 D(x, y) == D(y, x) 5.75/2.46 GCD(x, y) == GCD(y, x) 5.75/2.46 5.75/2.46 We have to consider all minimal (P,E#,R,E)-chains 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (13) ESharpUsableEquationsProof (EQUIVALENT) 5.75/2.46 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 5.75/2.46 *^1(x, y) == *^1(y, x) 5.75/2.46 +^1(x, y) == +^1(y, x) 5.75/2.46 D(x, y) == D(y, x) 5.75/2.46 GCD(x, y) == GCD(y, x) 5.75/2.46 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (14) 5.75/2.46 Obligation: 5.75/2.46 The TRS P consists of the following rules: 5.75/2.46 5.75/2.46 GT(s(N), s(M)) -> GT(N, M) 5.75/2.46 5.75/2.46 The TRS R consists of the following rules: 5.75/2.46 5.75/2.46 p(s(N)) -> N 5.75/2.46 +(N, 0) -> N 5.75/2.46 +(s(N), s(M)) -> s(s(+(N, M))) 5.75/2.46 *(N, 0) -> 0 5.75/2.46 *(s(N), s(M)) -> s(+(N, +(M, *(N, M)))) 5.75/2.46 gt(0, M) -> False 5.75/2.46 gt(NzN, 0) -> u_4(is_NzNat(NzN)) 5.75/2.46 u_4(True) -> True 5.75/2.46 is_NzNat(0) -> False 5.75/2.46 is_NzNat(s(N)) -> True 5.75/2.46 gt(s(N), s(M)) -> gt(N, M) 5.75/2.46 lt(N, M) -> gt(M, N) 5.75/2.46 d(0, N) -> N 5.75/2.46 d(s(N), s(M)) -> d(N, M) 5.75/2.46 quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM) 5.75/2.46 u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM) 5.75/2.46 u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM)) 5.75/2.46 quot(NzM, NzM) -> u_01(is_NzNat(NzM)) 5.75/2.46 u_01(True) -> s(0) 5.75/2.46 quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N) 5.75/2.46 u_21(True, NzM, N) -> u_2(gt(NzM, N)) 5.75/2.46 u_2(True) -> 0 5.75/2.46 gcd(0, N) -> 0 5.75/2.46 gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM) 5.75/2.46 u_02(True, NzM) -> NzM 5.75/2.46 gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM) 5.75/2.46 5.75/2.46 The set E consists of the following equations: 5.75/2.46 5.75/2.46 *(x, y) == *(y, x) 5.75/2.46 +(x, y) == +(y, x) 5.75/2.46 d(x, y) == d(y, x) 5.75/2.46 gcd(x, y) == gcd(y, x) 5.75/2.46 5.75/2.46 E# is empty. 5.75/2.46 We have to consider all minimal (P,E#,R,E)-chains 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (15) EUsableRulesReductionPairsProof (EQUIVALENT) 5.75/2.46 By using the improved usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding improved usable rules can be oriented non-strictly, the improved usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and improved usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 5.75/2.46 5.75/2.46 The following dependency pairs can be deleted: 5.75/2.46 5.75/2.46 GT(s(N), s(M)) -> GT(N, M) 5.75/2.46 The following rules are removed from R: 5.75/2.46 5.75/2.46 p(s(N)) -> N 5.75/2.46 +(N, 0) -> N 5.75/2.46 +(s(N), s(M)) -> s(s(+(N, M))) 5.75/2.46 *(N, 0) -> 0 5.75/2.46 *(s(N), s(M)) -> s(+(N, +(M, *(N, M)))) 5.75/2.46 gt(0, M) -> False 5.75/2.46 gt(NzN, 0) -> u_4(is_NzNat(NzN)) 5.75/2.46 u_4(True) -> True 5.75/2.46 is_NzNat(0) -> False 5.75/2.46 is_NzNat(s(N)) -> True 5.75/2.46 gt(s(N), s(M)) -> gt(N, M) 5.75/2.46 lt(N, M) -> gt(M, N) 5.75/2.46 d(0, N) -> N 5.75/2.46 d(s(N), s(M)) -> d(N, M) 5.75/2.46 quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM) 5.75/2.46 u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM) 5.75/2.46 u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM)) 5.75/2.46 quot(NzM, NzM) -> u_01(is_NzNat(NzM)) 5.75/2.46 u_01(True) -> s(0) 5.75/2.46 quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N) 5.75/2.46 u_21(True, NzM, N) -> u_2(gt(NzM, N)) 5.75/2.46 u_2(True) -> 0 5.75/2.46 gcd(0, N) -> 0 5.75/2.46 gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM) 5.75/2.46 u_02(True, NzM) -> NzM 5.75/2.46 gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM) 5.75/2.46 The following equations are removed from E: 5.75/2.46 5.75/2.46 *(x, y) == *(y, x) 5.75/2.46 +(x, y) == +(y, x) 5.75/2.46 d(x, y) == d(y, x) 5.75/2.46 gcd(x, y) == gcd(y, x) 5.75/2.46 Used ordering: POLO with Polynomial interpretation [POLO]: 5.75/2.46 5.75/2.46 POL(GT(x_1, x_2)) = 3*x_1 + 3*x_2 5.75/2.46 POL(s(x_1)) = x_1 5.75/2.46 5.75/2.46 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (16) 5.75/2.46 Obligation: 5.75/2.46 P is empty. 5.75/2.46 R is empty. 5.75/2.46 E is empty. 5.75/2.46 E# is empty. 5.75/2.46 We have to consider all minimal (P,E#,R,E)-chains 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (17) PisEmptyProof (EQUIVALENT) 5.75/2.46 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (18) 5.75/2.46 YES 5.75/2.46 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (19) 5.75/2.46 Obligation: 5.75/2.46 The TRS P consists of the following rules: 5.75/2.46 5.75/2.46 U_31(True, True, NzN, NzM) -> U_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 U_3(True, NzN, NzM) -> GCD(d(NzN, NzM), NzM) 5.75/2.46 GCD(NzN, NzM) -> U_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 5.75/2.46 The TRS R consists of the following rules: 5.75/2.46 5.75/2.46 p(s(N)) -> N 5.75/2.46 +(N, 0) -> N 5.75/2.46 +(s(N), s(M)) -> s(s(+(N, M))) 5.75/2.46 *(N, 0) -> 0 5.75/2.46 *(s(N), s(M)) -> s(+(N, +(M, *(N, M)))) 5.75/2.46 gt(0, M) -> False 5.75/2.46 gt(NzN, 0) -> u_4(is_NzNat(NzN)) 5.75/2.46 u_4(True) -> True 5.75/2.46 is_NzNat(0) -> False 5.75/2.46 is_NzNat(s(N)) -> True 5.75/2.46 gt(s(N), s(M)) -> gt(N, M) 5.75/2.46 lt(N, M) -> gt(M, N) 5.75/2.46 d(0, N) -> N 5.75/2.46 d(s(N), s(M)) -> d(N, M) 5.75/2.46 quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM) 5.75/2.46 u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM) 5.75/2.46 u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM)) 5.75/2.46 quot(NzM, NzM) -> u_01(is_NzNat(NzM)) 5.75/2.46 u_01(True) -> s(0) 5.75/2.46 quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N) 5.75/2.46 u_21(True, NzM, N) -> u_2(gt(NzM, N)) 5.75/2.46 u_2(True) -> 0 5.75/2.46 gcd(0, N) -> 0 5.75/2.46 gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM) 5.75/2.46 u_02(True, NzM) -> NzM 5.75/2.46 gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM) 5.75/2.46 5.75/2.46 The set E consists of the following equations: 5.75/2.46 5.75/2.46 *(x, y) == *(y, x) 5.75/2.46 +(x, y) == +(y, x) 5.75/2.46 d(x, y) == d(y, x) 5.75/2.46 gcd(x, y) == gcd(y, x) 5.75/2.46 5.75/2.46 The set E# consists of the following equations: 5.75/2.46 5.75/2.46 *^1(x, y) == *^1(y, x) 5.75/2.46 +^1(x, y) == +^1(y, x) 5.75/2.46 D(x, y) == D(y, x) 5.75/2.46 GCD(x, y) == GCD(y, x) 5.75/2.46 5.75/2.46 We have to consider all minimal (P,E#,R,E)-chains 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (20) ESharpUsableEquationsProof (EQUIVALENT) 5.75/2.46 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 5.75/2.46 *^1(x, y) == *^1(y, x) 5.75/2.46 +^1(x, y) == +^1(y, x) 5.75/2.46 D(x, y) == D(y, x) 5.75/2.46 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (21) 5.75/2.46 Obligation: 5.75/2.46 The TRS P consists of the following rules: 5.75/2.46 5.75/2.46 U_31(True, True, NzN, NzM) -> U_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 U_3(True, NzN, NzM) -> GCD(d(NzN, NzM), NzM) 5.75/2.46 GCD(NzN, NzM) -> U_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 5.75/2.46 The TRS R consists of the following rules: 5.75/2.46 5.75/2.46 p(s(N)) -> N 5.75/2.46 +(N, 0) -> N 5.75/2.46 +(s(N), s(M)) -> s(s(+(N, M))) 5.75/2.46 *(N, 0) -> 0 5.75/2.46 *(s(N), s(M)) -> s(+(N, +(M, *(N, M)))) 5.75/2.46 gt(0, M) -> False 5.75/2.46 gt(NzN, 0) -> u_4(is_NzNat(NzN)) 5.75/2.46 u_4(True) -> True 5.75/2.46 is_NzNat(0) -> False 5.75/2.46 is_NzNat(s(N)) -> True 5.75/2.46 gt(s(N), s(M)) -> gt(N, M) 5.75/2.46 lt(N, M) -> gt(M, N) 5.75/2.46 d(0, N) -> N 5.75/2.46 d(s(N), s(M)) -> d(N, M) 5.75/2.46 quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM) 5.75/2.46 u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM) 5.75/2.46 u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM)) 5.75/2.46 quot(NzM, NzM) -> u_01(is_NzNat(NzM)) 5.75/2.46 u_01(True) -> s(0) 5.75/2.46 quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N) 5.75/2.46 u_21(True, NzM, N) -> u_2(gt(NzM, N)) 5.75/2.46 u_2(True) -> 0 5.75/2.46 gcd(0, N) -> 0 5.75/2.46 gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM) 5.75/2.46 u_02(True, NzM) -> NzM 5.75/2.46 gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM) 5.75/2.46 5.75/2.46 The set E consists of the following equations: 5.75/2.46 5.75/2.46 *(x, y) == *(y, x) 5.75/2.46 +(x, y) == +(y, x) 5.75/2.46 d(x, y) == d(y, x) 5.75/2.46 gcd(x, y) == gcd(y, x) 5.75/2.46 5.75/2.46 The set E# consists of the following equations: 5.75/2.46 5.75/2.46 GCD(x, y) == GCD(y, x) 5.75/2.46 5.75/2.46 We have to consider all minimal (P,E#,R,E)-chains 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (22) EUsableRulesProof (EQUIVALENT) 5.75/2.46 We use the improved usable rules and equations processor [DA_STEIN] to delete all non-usable rules from R and all non-usable equations from E, but we lose minimality and add the following 2 Ce-rules: 5.75/2.46 c(x, y) -> x 5.75/2.46 c(x, y) -> y 5.75/2.46 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (23) 5.75/2.46 Obligation: 5.75/2.46 The TRS P consists of the following rules: 5.75/2.46 5.75/2.46 U_31(True, True, NzN, NzM) -> U_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 U_3(True, NzN, NzM) -> GCD(d(NzN, NzM), NzM) 5.75/2.46 GCD(NzN, NzM) -> U_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 5.75/2.46 The TRS R consists of the following rules: 5.75/2.46 5.75/2.46 is_NzNat(0) -> False 5.75/2.46 gt(NzN, 0) -> u_4(is_NzNat(NzN)) 5.75/2.46 is_NzNat(s(N)) -> True 5.75/2.46 gt(0, M) -> False 5.75/2.46 u_4(True) -> True 5.75/2.46 d(s(N), s(M)) -> d(N, M) 5.75/2.46 gt(s(N), s(M)) -> gt(N, M) 5.75/2.46 d(0, N) -> N 5.75/2.46 c(x, y) -> x 5.75/2.46 c(x, y) -> y 5.75/2.46 5.75/2.46 The set E consists of the following equations: 5.75/2.46 5.75/2.46 d(x, y) == d(y, x) 5.75/2.46 5.75/2.46 The set E# consists of the following equations: 5.75/2.46 5.75/2.46 GCD(x, y) == GCD(y, x) 5.75/2.46 5.75/2.46 We have to consider all (P,E#,R,E)-chains 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (24) 5.75/2.46 Obligation: 5.75/2.46 The TRS P consists of the following rules: 5.75/2.46 5.75/2.46 QUOT(N, NzM) -> U_11(is_NzNat(NzM), N, NzM) 5.75/2.46 U_11(True, N, NzM) -> U_1(gt(N, NzM), N, NzM) 5.75/2.46 U_1(True, N, NzM) -> QUOT(d(N, NzM), NzM) 5.75/2.46 5.75/2.46 The TRS R consists of the following rules: 5.75/2.46 5.75/2.46 p(s(N)) -> N 5.75/2.46 +(N, 0) -> N 5.75/2.46 +(s(N), s(M)) -> s(s(+(N, M))) 5.75/2.46 *(N, 0) -> 0 5.75/2.46 *(s(N), s(M)) -> s(+(N, +(M, *(N, M)))) 5.75/2.46 gt(0, M) -> False 5.75/2.46 gt(NzN, 0) -> u_4(is_NzNat(NzN)) 5.75/2.46 u_4(True) -> True 5.75/2.46 is_NzNat(0) -> False 5.75/2.46 is_NzNat(s(N)) -> True 5.75/2.46 gt(s(N), s(M)) -> gt(N, M) 5.75/2.46 lt(N, M) -> gt(M, N) 5.75/2.46 d(0, N) -> N 5.75/2.46 d(s(N), s(M)) -> d(N, M) 5.75/2.46 quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM) 5.75/2.46 u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM) 5.75/2.46 u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM)) 5.75/2.46 quot(NzM, NzM) -> u_01(is_NzNat(NzM)) 5.75/2.46 u_01(True) -> s(0) 5.75/2.46 quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N) 5.75/2.46 u_21(True, NzM, N) -> u_2(gt(NzM, N)) 5.75/2.46 u_2(True) -> 0 5.75/2.46 gcd(0, N) -> 0 5.75/2.46 gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM) 5.75/2.46 u_02(True, NzM) -> NzM 5.75/2.46 gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM) 5.75/2.46 5.75/2.46 The set E consists of the following equations: 5.75/2.46 5.75/2.46 *(x, y) == *(y, x) 5.75/2.46 +(x, y) == +(y, x) 5.75/2.46 d(x, y) == d(y, x) 5.75/2.46 gcd(x, y) == gcd(y, x) 5.75/2.46 5.75/2.46 The set E# consists of the following equations: 5.75/2.46 5.75/2.46 *^1(x, y) == *^1(y, x) 5.75/2.46 +^1(x, y) == +^1(y, x) 5.75/2.46 D(x, y) == D(y, x) 5.75/2.46 GCD(x, y) == GCD(y, x) 5.75/2.46 5.75/2.46 We have to consider all minimal (P,E#,R,E)-chains 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (25) 5.75/2.46 Obligation: 5.75/2.46 The TRS P consists of the following rules: 5.75/2.46 5.75/2.46 +^1(s(N), s(M)) -> +^1(N, M) 5.75/2.46 5.75/2.46 The TRS R consists of the following rules: 5.75/2.46 5.75/2.46 p(s(N)) -> N 5.75/2.46 +(N, 0) -> N 5.75/2.46 +(s(N), s(M)) -> s(s(+(N, M))) 5.75/2.46 *(N, 0) -> 0 5.75/2.46 *(s(N), s(M)) -> s(+(N, +(M, *(N, M)))) 5.75/2.46 gt(0, M) -> False 5.75/2.46 gt(NzN, 0) -> u_4(is_NzNat(NzN)) 5.75/2.46 u_4(True) -> True 5.75/2.46 is_NzNat(0) -> False 5.75/2.46 is_NzNat(s(N)) -> True 5.75/2.46 gt(s(N), s(M)) -> gt(N, M) 5.75/2.46 lt(N, M) -> gt(M, N) 5.75/2.46 d(0, N) -> N 5.75/2.46 d(s(N), s(M)) -> d(N, M) 5.75/2.46 quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM) 5.75/2.46 u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM) 5.75/2.46 u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM)) 5.75/2.46 quot(NzM, NzM) -> u_01(is_NzNat(NzM)) 5.75/2.46 u_01(True) -> s(0) 5.75/2.46 quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N) 5.75/2.46 u_21(True, NzM, N) -> u_2(gt(NzM, N)) 5.75/2.46 u_2(True) -> 0 5.75/2.46 gcd(0, N) -> 0 5.75/2.46 gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM) 5.75/2.46 u_02(True, NzM) -> NzM 5.75/2.46 gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM) 5.75/2.46 5.75/2.46 The set E consists of the following equations: 5.75/2.46 5.75/2.46 *(x, y) == *(y, x) 5.75/2.46 +(x, y) == +(y, x) 5.75/2.46 d(x, y) == d(y, x) 5.75/2.46 gcd(x, y) == gcd(y, x) 5.75/2.46 5.75/2.46 The set E# consists of the following equations: 5.75/2.46 5.75/2.46 *^1(x, y) == *^1(y, x) 5.75/2.46 +^1(x, y) == +^1(y, x) 5.75/2.46 D(x, y) == D(y, x) 5.75/2.46 GCD(x, y) == GCD(y, x) 5.75/2.46 5.75/2.46 We have to consider all minimal (P,E#,R,E)-chains 5.75/2.46 ---------------------------------------- 5.75/2.46 5.75/2.46 (26) 5.75/2.46 Obligation: 5.75/2.46 The TRS P consists of the following rules: 5.75/2.46 5.75/2.46 *^1(s(N), s(M)) -> *^1(N, M) 5.75/2.46 5.75/2.46 The TRS R consists of the following rules: 5.75/2.46 5.75/2.46 p(s(N)) -> N 5.75/2.46 +(N, 0) -> N 5.75/2.46 +(s(N), s(M)) -> s(s(+(N, M))) 5.75/2.46 *(N, 0) -> 0 5.75/2.46 *(s(N), s(M)) -> s(+(N, +(M, *(N, M)))) 5.75/2.46 gt(0, M) -> False 5.75/2.46 gt(NzN, 0) -> u_4(is_NzNat(NzN)) 5.75/2.46 u_4(True) -> True 5.75/2.46 is_NzNat(0) -> False 5.75/2.46 is_NzNat(s(N)) -> True 5.75/2.46 gt(s(N), s(M)) -> gt(N, M) 5.75/2.46 lt(N, M) -> gt(M, N) 5.75/2.46 d(0, N) -> N 5.75/2.46 d(s(N), s(M)) -> d(N, M) 5.75/2.46 quot(N, NzM) -> u_11(is_NzNat(NzM), N, NzM) 5.75/2.46 u_11(True, N, NzM) -> u_1(gt(N, NzM), N, NzM) 5.75/2.46 u_1(True, N, NzM) -> s(quot(d(N, NzM), NzM)) 5.75/2.46 quot(NzM, NzM) -> u_01(is_NzNat(NzM)) 5.75/2.46 u_01(True) -> s(0) 5.75/2.46 quot(N, NzM) -> u_21(is_NzNat(NzM), NzM, N) 5.75/2.46 u_21(True, NzM, N) -> u_2(gt(NzM, N)) 5.75/2.46 u_2(True) -> 0 5.75/2.46 gcd(0, N) -> 0 5.75/2.46 gcd(NzM, NzM) -> u_02(is_NzNat(NzM), NzM) 5.75/2.46 u_02(True, NzM) -> NzM 5.75/2.46 gcd(NzN, NzM) -> u_31(is_NzNat(NzN), is_NzNat(NzM), NzN, NzM) 5.75/2.46 u_31(True, True, NzN, NzM) -> u_3(gt(NzN, NzM), NzN, NzM) 5.75/2.46 u_3(True, NzN, NzM) -> gcd(d(NzN, NzM), NzM) 5.75/2.46 5.75/2.46 The set E consists of the following equations: 5.75/2.46 5.75/2.46 *(x, y) == *(y, x) 5.75/2.46 +(x, y) == +(y, x) 5.75/2.46 d(x, y) == d(y, x) 5.75/2.46 gcd(x, y) == gcd(y, x) 5.75/2.46 5.75/2.46 The set E# consists of the following equations: 5.75/2.46 5.75/2.46 *^1(x, y) == *^1(y, x) 5.75/2.46 +^1(x, y) == +^1(y, x) 5.75/2.46 D(x, y) == D(y, x) 5.75/2.46 GCD(x, y) == GCD(y, x) 5.75/2.46 5.75/2.46 We have to consider all minimal (P,E#,R,E)-chains 5.99/2.49 EOF