18.38/8.41 MAYBE 18.38/8.42 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 18.38/8.42 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 18.38/8.42 18.38/8.42 18.38/8.42 Termination of the given ETRS could not be shown: 18.38/8.42 18.38/8.42 (0) ETRS 18.38/8.42 (1) EquationalDependencyPairsProof [EQUIVALENT, 0 ms] 18.38/8.42 (2) EDP 18.38/8.42 (3) EDependencyGraphProof [EQUIVALENT, 0 ms] 18.38/8.42 (4) AND 18.38/8.42 (5) EDP 18.38/8.42 (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 18.38/8.42 (7) EDP 18.38/8.42 (8) EUsableRulesReductionPairsProof [EQUIVALENT, 155 ms] 18.38/8.42 (9) EDP 18.38/8.42 (10) EDependencyGraphProof [EQUIVALENT, 0 ms] 18.38/8.42 (11) TRUE 18.38/8.42 (12) EDP 18.38/8.42 (13) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 18.38/8.42 (14) EDP 18.38/8.42 (15) EUsableRulesReductionPairsProof [EQUIVALENT, 80 ms] 18.38/8.42 (16) EDP 18.38/8.42 (17) EDependencyGraphProof [EQUIVALENT, 0 ms] 18.38/8.42 (18) TRUE 18.38/8.42 (19) EDP 18.38/8.42 (20) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 18.38/8.42 (21) EDP 18.38/8.42 (22) EUsableRulesReductionPairsProof [EQUIVALENT, 83 ms] 18.38/8.42 (23) EDP 18.38/8.42 (24) EDependencyGraphProof [EQUIVALENT, 0 ms] 18.38/8.42 (25) TRUE 18.38/8.42 (26) EDP 18.38/8.42 (27) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 18.38/8.42 (28) EDP 18.38/8.42 (29) EUsableRulesReductionPairsProof [EQUIVALENT, 45 ms] 18.38/8.42 (30) EDP 18.38/8.42 (31) EDependencyGraphProof [EQUIVALENT, 0 ms] 18.38/8.42 (32) TRUE 18.38/8.42 (33) EDP 18.38/8.42 (34) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 18.38/8.42 (35) EDP 18.38/8.42 (36) EUsableRulesReductionPairsProof [EQUIVALENT, 44 ms] 18.38/8.42 (37) EDP 18.38/8.42 (38) EDependencyGraphProof [EQUIVALENT, 0 ms] 18.38/8.42 (39) TRUE 18.38/8.42 (40) EDP 18.38/8.42 (41) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 18.38/8.42 (42) EDP 18.38/8.42 (43) EUsableRulesProof [EQUIVALENT, 4 ms] 18.38/8.42 (44) EDP 18.38/8.42 (45) EDP 18.38/8.42 18.38/8.42 18.38/8.42 ---------------------------------------- 18.38/8.42 18.38/8.42 (0) 18.38/8.42 Obligation: 18.38/8.42 Equational rewrite system: 18.38/8.42 The TRS R consists of the following rules: 18.38/8.42 18.38/8.42 1 -> s_(0) 18.38/8.42 2 -> s_(s_(0)) 18.38/8.42 3 -> s_(s_(s_(0))) 18.38/8.42 4 -> s_(s_(s_(s_(0)))) 18.38/8.42 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.42 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.42 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.42 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.42 U102(tt, M, N) -> d(N, M) 18.38/8.42 U11(tt) -> 0 18.38/8.42 U111(tt) -> 0 18.38/8.42 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.42 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.42 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.42 U131(tt, N') -> N' 18.38/8.42 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.42 U142(tt) -> tt 18.38/8.42 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.42 U152(tt) -> tt 18.38/8.42 U161(tt) -> tt 18.38/8.42 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.42 U172(tt) -> tt 18.38/8.42 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.42 U182(tt) -> tt 18.38/8.42 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.42 U192(tt) -> tt 18.38/8.42 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.42 U202(tt) -> tt 18.38/8.42 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.42 U211(tt) -> tt 18.38/8.42 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.42 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.42 U222(tt) -> tt 18.38/8.42 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.42 U232(tt) -> tt 18.38/8.42 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.42 U242(tt) -> tt 18.38/8.42 U251(tt) -> tt 18.38/8.42 U261(tt, N) -> N 18.38/8.42 U271(tt) -> s_(0) 18.38/8.42 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.42 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.42 U283(tt) -> 0 18.38/8.42 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.42 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.42 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.42 U31(tt, N) -> N 18.38/8.42 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.42 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.42 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.42 U52(tt, M, N) -> _>_(M, N) 18.38/8.42 U61(tt) -> false 18.38/8.42 U71(tt) -> true 18.38/8.42 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.42 U82(tt, M, N) -> _>_(N, M) 18.38/8.42 U91(tt, N) -> N 18.38/8.42 _*_(N, 0) -> U11(isNat(N)) 18.38/8.42 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.42 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.42 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.42 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.42 _>_(0, M) -> U61(isNat(M)) 18.38/8.42 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.42 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.42 d(0, N) -> U91(isNat(N), N) 18.38/8.42 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.42 equal(X, X) -> tt 18.38/8.42 gcd(0, N) -> U111(isNat(N)) 18.38/8.42 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.42 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.42 isBoolean(false) -> tt 18.38/8.42 isBoolean(true) -> tt 18.38/8.42 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.42 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.42 isNat(0) -> tt 18.38/8.42 isNat(V) -> U161(isNzNat(V)) 18.38/8.42 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.42 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.42 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.42 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.42 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.42 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.42 isNzNat(1) -> tt 18.38/8.42 isNzNat(2) -> tt 18.38/8.42 isNzNat(3) -> tt 18.38/8.42 isNzNat(4) -> tt 18.38/8.42 isNzNat(5) -> tt 18.38/8.42 isNzNat(6) -> tt 18.38/8.42 isNzNat(7) -> tt 18.38/8.42 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.42 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.42 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.42 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.42 quot(M', M') -> U271(isNzNat(M')) 18.38/8.42 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.42 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.42 18.38/8.42 The set E consists of the following equations: 18.38/8.42 18.38/8.42 _*_(x, y) == _*_(y, x) 18.38/8.42 _+_(x, y) == _+_(y, x) 18.38/8.42 d(x, y) == d(y, x) 18.38/8.42 gcd(x, y) == gcd(y, x) 18.38/8.42 18.38/8.42 18.38/8.42 ---------------------------------------- 18.38/8.42 18.38/8.42 (1) EquationalDependencyPairsProof (EQUIVALENT) 18.38/8.42 Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: 18.38/8.42 The TRS P consists of the following rules: 18.38/8.42 18.38/8.42 U101^1(tt, M, N) -> U102^1(isNat(N), M, N) 18.38/8.42 U101^1(tt, M, N) -> ISNAT(N) 18.38/8.42 U102^1(tt, M, N) -> D(N, M) 18.38/8.42 U121^1(tt, M', N') -> U122^1(isNzNat(N'), M', N') 18.38/8.42 U121^1(tt, M', N') -> ISNZNAT(N') 18.38/8.42 U122^1(tt, M', N') -> U123^1(equal(_>_(N', M'), true), M', N') 18.38/8.42 U122^1(tt, M', N') -> EQUAL(_>_(N', M'), true) 18.38/8.42 U122^1(tt, M', N') -> _>_^1(N', M') 18.38/8.42 U123^1(tt, M', N') -> GCD(d(N', M'), M') 18.38/8.42 U123^1(tt, M', N') -> D(N', M') 18.38/8.42 U141^1(tt, V2) -> U142^1(isNat(V2)) 18.38/8.42 U141^1(tt, V2) -> ISNAT(V2) 18.38/8.42 U151^1(tt, V2) -> U152^1(isNat(V2)) 18.38/8.42 U151^1(tt, V2) -> ISNAT(V2) 18.38/8.42 U171^1(tt, V2) -> U172^1(isNat(V2)) 18.38/8.42 U171^1(tt, V2) -> ISNAT(V2) 18.38/8.42 U181^1(tt, V2) -> U182^1(isNat(V2)) 18.38/8.42 U181^1(tt, V2) -> ISNAT(V2) 18.38/8.42 U191^1(tt, V2) -> U192^1(isNat(V2)) 18.38/8.42 U191^1(tt, V2) -> ISNAT(V2) 18.38/8.42 U201^1(tt, V2) -> U202^1(isNat(V2)) 18.38/8.42 U201^1(tt, V2) -> ISNAT(V2) 18.38/8.42 U21^1(tt, M, N) -> U22^1(isNat(N), M, N) 18.38/8.42 U21^1(tt, M, N) -> ISNAT(N) 18.38/8.42 U22^1(tt, M, N) -> _+_^1(N, _+_(M, _*_(N, M))) 18.38/8.42 U22^1(tt, M, N) -> _+_^1(M, _*_(N, M)) 18.38/8.42 U22^1(tt, M, N) -> _*_^1(N, M) 18.38/8.42 U221^1(tt, V2) -> U222^1(isNzNat(V2)) 18.38/8.42 U221^1(tt, V2) -> ISNZNAT(V2) 18.38/8.42 U231^1(tt, V2) -> U232^1(isNzNat(V2)) 18.38/8.42 U231^1(tt, V2) -> ISNZNAT(V2) 18.38/8.42 U241^1(tt, V2) -> U242^1(isNzNat(V2)) 18.38/8.42 U241^1(tt, V2) -> ISNZNAT(V2) 18.38/8.42 U281^1(tt, M', N) -> U282^1(isNat(N), M', N) 18.38/8.42 U281^1(tt, M', N) -> ISNAT(N) 18.38/8.42 U282^1(tt, M', N) -> U283^1(equal(_>_(M', N), true)) 18.38/8.42 U282^1(tt, M', N) -> EQUAL(_>_(M', N), true) 18.38/8.42 U282^1(tt, M', N) -> _>_^1(M', N) 18.38/8.42 U291^1(tt, M', N) -> U292^1(isNat(N), M', N) 18.38/8.42 U291^1(tt, M', N) -> ISNAT(N) 18.38/8.42 U292^1(tt, M', N) -> U293^1(equal(_>_(N, M'), true), M', N) 18.38/8.42 U292^1(tt, M', N) -> EQUAL(_>_(N, M'), true) 18.38/8.42 U292^1(tt, M', N) -> _>_^1(N, M') 18.38/8.42 U293^1(tt, M', N) -> QUOT(d(N, M'), M') 18.38/8.42 U293^1(tt, M', N) -> D(N, M') 18.38/8.42 U41^1(tt, M, N) -> U42^1(isNat(N), M, N) 18.38/8.42 U41^1(tt, M, N) -> ISNAT(N) 18.38/8.42 U42^1(tt, M, N) -> _+_^1(N, M) 18.38/8.42 U51^1(tt, M, N) -> U52^1(isNat(N), M, N) 18.38/8.42 U51^1(tt, M, N) -> ISNAT(N) 18.38/8.42 U52^1(tt, M, N) -> _>_^1(M, N) 18.38/8.42 U81^1(tt, M, N) -> U82^1(isNat(N), M, N) 18.38/8.42 U81^1(tt, M, N) -> ISNAT(N) 18.38/8.42 U82^1(tt, M, N) -> _>_^1(N, M) 18.38/8.42 _*_^1(N, 0) -> U11^1(isNat(N)) 18.38/8.42 _*_^1(N, 0) -> ISNAT(N) 18.38/8.42 _*_^1(s_(N), s_(M)) -> U21^1(isNat(M), M, N) 18.38/8.42 _*_^1(s_(N), s_(M)) -> ISNAT(M) 18.38/8.42 _+_^1(N, 0) -> U31^1(isNat(N), N) 18.38/8.42 _+_^1(N, 0) -> ISNAT(N) 18.38/8.42 _+_^1(s_(N), s_(M)) -> U41^1(isNat(M), M, N) 18.38/8.42 _+_^1(s_(N), s_(M)) -> ISNAT(M) 18.38/8.42 _<_^1(N, M) -> U51^1(isNat(M), M, N) 18.38/8.42 _<_^1(N, M) -> ISNAT(M) 18.38/8.42 _>_^1(0, M) -> U61^1(isNat(M)) 18.38/8.42 _>_^1(0, M) -> ISNAT(M) 18.38/8.42 _>_^1(N', 0) -> U71^1(isNzNat(N')) 18.38/8.42 _>_^1(N', 0) -> ISNZNAT(N') 18.38/8.42 _>_^1(s_(N), s_(M)) -> U81^1(isNat(M), M, N) 18.38/8.42 _>_^1(s_(N), s_(M)) -> ISNAT(M) 18.38/8.42 D(0, N) -> U91^1(isNat(N), N) 18.38/8.42 D(0, N) -> ISNAT(N) 18.38/8.42 D(s_(N), s_(M)) -> U101^1(isNat(M), M, N) 18.38/8.42 D(s_(N), s_(M)) -> ISNAT(M) 18.38/8.42 GCD(0, N) -> U111^1(isNat(N)) 18.38/8.42 GCD(0, N) -> ISNAT(N) 18.38/8.42 GCD(N', M') -> U121^1(isNzNat(M'), M', N') 18.38/8.42 GCD(N', M') -> ISNZNAT(M') 18.38/8.42 GCD(N', N') -> U131^1(isNzNat(N'), N') 18.38/8.42 GCD(N', N') -> ISNZNAT(N') 18.38/8.42 ISBOOLEAN(_<_(V1, V2)) -> U141^1(isNat(V1), V2) 18.38/8.42 ISBOOLEAN(_<_(V1, V2)) -> ISNAT(V1) 18.38/8.42 ISBOOLEAN(_>_(V1, V2)) -> U151^1(isNat(V1), V2) 18.38/8.42 ISBOOLEAN(_>_(V1, V2)) -> ISNAT(V1) 18.38/8.42 ISNAT(V) -> U161^1(isNzNat(V)) 18.38/8.42 ISNAT(V) -> ISNZNAT(V) 18.38/8.42 ISNAT(_*_(V1, V2)) -> U171^1(isNat(V1), V2) 18.38/8.42 ISNAT(_*_(V1, V2)) -> ISNAT(V1) 18.38/8.42 ISNAT(_+_(V1, V2)) -> U181^1(isNat(V1), V2) 18.38/8.42 ISNAT(_+_(V1, V2)) -> ISNAT(V1) 18.38/8.42 ISNAT(d(V1, V2)) -> U191^1(isNat(V1), V2) 18.38/8.42 ISNAT(d(V1, V2)) -> ISNAT(V1) 18.38/8.42 ISNAT(gcd(V1, V2)) -> U201^1(isNat(V1), V2) 18.38/8.42 ISNAT(gcd(V1, V2)) -> ISNAT(V1) 18.38/8.42 ISNAT(p_(V1)) -> U211^1(isNzNat(V1)) 18.38/8.42 ISNAT(p_(V1)) -> ISNZNAT(V1) 18.38/8.42 ISNAT(quot(V1, V2)) -> U221^1(isNat(V1), V2) 18.38/8.42 ISNAT(quot(V1, V2)) -> ISNAT(V1) 18.38/8.42 ISNZNAT(_*_(V1, V2)) -> U231^1(isNzNat(V1), V2) 18.38/8.42 ISNZNAT(_*_(V1, V2)) -> ISNZNAT(V1) 18.38/8.42 ISNZNAT(gcd(V1, V2)) -> U241^1(isNzNat(V1), V2) 18.38/8.42 ISNZNAT(gcd(V1, V2)) -> ISNZNAT(V1) 18.38/8.42 ISNZNAT(s_(V1)) -> U251^1(isNat(V1)) 18.38/8.42 ISNZNAT(s_(V1)) -> ISNAT(V1) 18.38/8.42 P_(s_(N)) -> U261^1(isNat(N), N) 18.38/8.42 P_(s_(N)) -> ISNAT(N) 18.38/8.42 QUOT(M', M') -> U271^1(isNzNat(M')) 18.38/8.42 QUOT(M', M') -> ISNZNAT(M') 18.38/8.42 QUOT(N, M') -> U281^1(isNzNat(M'), M', N) 18.38/8.42 QUOT(N, M') -> ISNZNAT(M') 18.38/8.42 QUOT(N, M') -> U291^1(isNzNat(M'), M', N) 18.38/8.42 18.38/8.42 The TRS R consists of the following rules: 18.38/8.42 18.38/8.42 1 -> s_(0) 18.38/8.42 2 -> s_(s_(0)) 18.38/8.42 3 -> s_(s_(s_(0))) 18.38/8.42 4 -> s_(s_(s_(s_(0)))) 18.38/8.42 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.42 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.42 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.42 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.42 U102(tt, M, N) -> d(N, M) 18.38/8.42 U11(tt) -> 0 18.38/8.42 U111(tt) -> 0 18.38/8.42 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.42 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.42 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.42 U131(tt, N') -> N' 18.38/8.42 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.42 U142(tt) -> tt 18.38/8.42 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.42 U152(tt) -> tt 18.38/8.42 U161(tt) -> tt 18.38/8.42 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.42 U172(tt) -> tt 18.38/8.42 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.42 U182(tt) -> tt 18.38/8.42 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.42 U192(tt) -> tt 18.38/8.42 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.42 U202(tt) -> tt 18.38/8.42 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.42 U211(tt) -> tt 18.38/8.42 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.42 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.42 U222(tt) -> tt 18.38/8.42 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.42 U232(tt) -> tt 18.38/8.42 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.42 U242(tt) -> tt 18.38/8.42 U251(tt) -> tt 18.38/8.42 U261(tt, N) -> N 18.38/8.42 U271(tt) -> s_(0) 18.38/8.42 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.42 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.42 U283(tt) -> 0 18.38/8.42 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.42 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.42 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.42 U31(tt, N) -> N 18.38/8.42 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.42 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.42 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.42 U52(tt, M, N) -> _>_(M, N) 18.38/8.42 U61(tt) -> false 18.38/8.42 U71(tt) -> true 18.38/8.42 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.42 U82(tt, M, N) -> _>_(N, M) 18.38/8.42 U91(tt, N) -> N 18.38/8.42 _*_(N, 0) -> U11(isNat(N)) 18.38/8.42 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.42 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.42 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.42 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.42 _>_(0, M) -> U61(isNat(M)) 18.38/8.42 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.42 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.42 d(0, N) -> U91(isNat(N), N) 18.38/8.42 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.42 equal(X, X) -> tt 18.38/8.42 gcd(0, N) -> U111(isNat(N)) 18.38/8.42 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.42 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.42 isBoolean(false) -> tt 18.38/8.42 isBoolean(true) -> tt 18.38/8.42 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.42 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.42 isNat(0) -> tt 18.38/8.42 isNat(V) -> U161(isNzNat(V)) 18.38/8.42 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.42 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.42 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.42 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.42 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.42 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.42 isNzNat(1) -> tt 18.38/8.42 isNzNat(2) -> tt 18.38/8.42 isNzNat(3) -> tt 18.38/8.42 isNzNat(4) -> tt 18.38/8.42 isNzNat(5) -> tt 18.38/8.42 isNzNat(6) -> tt 18.38/8.42 isNzNat(7) -> tt 18.38/8.42 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.42 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.42 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.42 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.42 quot(M', M') -> U271(isNzNat(M')) 18.38/8.42 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.42 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.42 18.38/8.42 The set E consists of the following equations: 18.38/8.42 18.38/8.42 _*_(x, y) == _*_(y, x) 18.38/8.42 _+_(x, y) == _+_(y, x) 18.38/8.42 d(x, y) == d(y, x) 18.38/8.42 gcd(x, y) == gcd(y, x) 18.38/8.42 18.38/8.42 The set E# consists of the following equations: 18.38/8.42 18.38/8.42 _*_^1(x, y) == _*_^1(y, x) 18.38/8.42 _+_^1(x, y) == _+_^1(y, x) 18.38/8.42 D(x, y) == D(y, x) 18.38/8.42 GCD(x, y) == GCD(y, x) 18.38/8.42 18.38/8.42 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.42 18.38/8.42 ---------------------------------------- 18.38/8.42 18.38/8.42 (2) 18.38/8.42 Obligation: 18.38/8.42 The TRS P consists of the following rules: 18.38/8.42 18.38/8.42 U101^1(tt, M, N) -> U102^1(isNat(N), M, N) 18.38/8.42 U101^1(tt, M, N) -> ISNAT(N) 18.38/8.42 U102^1(tt, M, N) -> D(N, M) 18.38/8.42 U121^1(tt, M', N') -> U122^1(isNzNat(N'), M', N') 18.38/8.42 U121^1(tt, M', N') -> ISNZNAT(N') 18.38/8.42 U122^1(tt, M', N') -> U123^1(equal(_>_(N', M'), true), M', N') 18.38/8.42 U122^1(tt, M', N') -> EQUAL(_>_(N', M'), true) 18.38/8.42 U122^1(tt, M', N') -> _>_^1(N', M') 18.38/8.42 U123^1(tt, M', N') -> GCD(d(N', M'), M') 18.38/8.42 U123^1(tt, M', N') -> D(N', M') 18.38/8.42 U141^1(tt, V2) -> U142^1(isNat(V2)) 18.38/8.42 U141^1(tt, V2) -> ISNAT(V2) 18.38/8.42 U151^1(tt, V2) -> U152^1(isNat(V2)) 18.38/8.42 U151^1(tt, V2) -> ISNAT(V2) 18.38/8.42 U171^1(tt, V2) -> U172^1(isNat(V2)) 18.38/8.42 U171^1(tt, V2) -> ISNAT(V2) 18.38/8.42 U181^1(tt, V2) -> U182^1(isNat(V2)) 18.38/8.42 U181^1(tt, V2) -> ISNAT(V2) 18.38/8.42 U191^1(tt, V2) -> U192^1(isNat(V2)) 18.38/8.42 U191^1(tt, V2) -> ISNAT(V2) 18.38/8.42 U201^1(tt, V2) -> U202^1(isNat(V2)) 18.38/8.42 U201^1(tt, V2) -> ISNAT(V2) 18.38/8.42 U21^1(tt, M, N) -> U22^1(isNat(N), M, N) 18.38/8.42 U21^1(tt, M, N) -> ISNAT(N) 18.38/8.42 U22^1(tt, M, N) -> _+_^1(N, _+_(M, _*_(N, M))) 18.38/8.42 U22^1(tt, M, N) -> _+_^1(M, _*_(N, M)) 18.38/8.42 U22^1(tt, M, N) -> _*_^1(N, M) 18.38/8.42 U221^1(tt, V2) -> U222^1(isNzNat(V2)) 18.38/8.42 U221^1(tt, V2) -> ISNZNAT(V2) 18.38/8.42 U231^1(tt, V2) -> U232^1(isNzNat(V2)) 18.38/8.42 U231^1(tt, V2) -> ISNZNAT(V2) 18.38/8.42 U241^1(tt, V2) -> U242^1(isNzNat(V2)) 18.38/8.42 U241^1(tt, V2) -> ISNZNAT(V2) 18.38/8.42 U281^1(tt, M', N) -> U282^1(isNat(N), M', N) 18.38/8.42 U281^1(tt, M', N) -> ISNAT(N) 18.38/8.42 U282^1(tt, M', N) -> U283^1(equal(_>_(M', N), true)) 18.38/8.42 U282^1(tt, M', N) -> EQUAL(_>_(M', N), true) 18.38/8.42 U282^1(tt, M', N) -> _>_^1(M', N) 18.38/8.42 U291^1(tt, M', N) -> U292^1(isNat(N), M', N) 18.38/8.42 U291^1(tt, M', N) -> ISNAT(N) 18.38/8.42 U292^1(tt, M', N) -> U293^1(equal(_>_(N, M'), true), M', N) 18.38/8.42 U292^1(tt, M', N) -> EQUAL(_>_(N, M'), true) 18.38/8.42 U292^1(tt, M', N) -> _>_^1(N, M') 18.38/8.42 U293^1(tt, M', N) -> QUOT(d(N, M'), M') 18.38/8.42 U293^1(tt, M', N) -> D(N, M') 18.38/8.42 U41^1(tt, M, N) -> U42^1(isNat(N), M, N) 18.38/8.42 U41^1(tt, M, N) -> ISNAT(N) 18.38/8.42 U42^1(tt, M, N) -> _+_^1(N, M) 18.38/8.42 U51^1(tt, M, N) -> U52^1(isNat(N), M, N) 18.38/8.42 U51^1(tt, M, N) -> ISNAT(N) 18.38/8.42 U52^1(tt, M, N) -> _>_^1(M, N) 18.38/8.42 U81^1(tt, M, N) -> U82^1(isNat(N), M, N) 18.38/8.42 U81^1(tt, M, N) -> ISNAT(N) 18.38/8.42 U82^1(tt, M, N) -> _>_^1(N, M) 18.38/8.42 _*_^1(N, 0) -> U11^1(isNat(N)) 18.38/8.42 _*_^1(N, 0) -> ISNAT(N) 18.38/8.42 _*_^1(s_(N), s_(M)) -> U21^1(isNat(M), M, N) 18.38/8.42 _*_^1(s_(N), s_(M)) -> ISNAT(M) 18.38/8.42 _+_^1(N, 0) -> U31^1(isNat(N), N) 18.38/8.42 _+_^1(N, 0) -> ISNAT(N) 18.38/8.42 _+_^1(s_(N), s_(M)) -> U41^1(isNat(M), M, N) 18.38/8.42 _+_^1(s_(N), s_(M)) -> ISNAT(M) 18.38/8.42 _<_^1(N, M) -> U51^1(isNat(M), M, N) 18.38/8.42 _<_^1(N, M) -> ISNAT(M) 18.38/8.42 _>_^1(0, M) -> U61^1(isNat(M)) 18.38/8.42 _>_^1(0, M) -> ISNAT(M) 18.38/8.42 _>_^1(N', 0) -> U71^1(isNzNat(N')) 18.38/8.42 _>_^1(N', 0) -> ISNZNAT(N') 18.38/8.42 _>_^1(s_(N), s_(M)) -> U81^1(isNat(M), M, N) 18.38/8.42 _>_^1(s_(N), s_(M)) -> ISNAT(M) 18.38/8.42 D(0, N) -> U91^1(isNat(N), N) 18.38/8.42 D(0, N) -> ISNAT(N) 18.38/8.42 D(s_(N), s_(M)) -> U101^1(isNat(M), M, N) 18.38/8.42 D(s_(N), s_(M)) -> ISNAT(M) 18.38/8.42 GCD(0, N) -> U111^1(isNat(N)) 18.38/8.42 GCD(0, N) -> ISNAT(N) 18.38/8.42 GCD(N', M') -> U121^1(isNzNat(M'), M', N') 18.38/8.42 GCD(N', M') -> ISNZNAT(M') 18.38/8.42 GCD(N', N') -> U131^1(isNzNat(N'), N') 18.38/8.42 GCD(N', N') -> ISNZNAT(N') 18.38/8.42 ISBOOLEAN(_<_(V1, V2)) -> U141^1(isNat(V1), V2) 18.38/8.42 ISBOOLEAN(_<_(V1, V2)) -> ISNAT(V1) 18.38/8.42 ISBOOLEAN(_>_(V1, V2)) -> U151^1(isNat(V1), V2) 18.38/8.42 ISBOOLEAN(_>_(V1, V2)) -> ISNAT(V1) 18.38/8.42 ISNAT(V) -> U161^1(isNzNat(V)) 18.38/8.42 ISNAT(V) -> ISNZNAT(V) 18.38/8.42 ISNAT(_*_(V1, V2)) -> U171^1(isNat(V1), V2) 18.38/8.42 ISNAT(_*_(V1, V2)) -> ISNAT(V1) 18.38/8.42 ISNAT(_+_(V1, V2)) -> U181^1(isNat(V1), V2) 18.38/8.42 ISNAT(_+_(V1, V2)) -> ISNAT(V1) 18.38/8.42 ISNAT(d(V1, V2)) -> U191^1(isNat(V1), V2) 18.38/8.42 ISNAT(d(V1, V2)) -> ISNAT(V1) 18.38/8.42 ISNAT(gcd(V1, V2)) -> U201^1(isNat(V1), V2) 18.38/8.42 ISNAT(gcd(V1, V2)) -> ISNAT(V1) 18.38/8.42 ISNAT(p_(V1)) -> U211^1(isNzNat(V1)) 18.38/8.42 ISNAT(p_(V1)) -> ISNZNAT(V1) 18.38/8.42 ISNAT(quot(V1, V2)) -> U221^1(isNat(V1), V2) 18.38/8.42 ISNAT(quot(V1, V2)) -> ISNAT(V1) 18.38/8.42 ISNZNAT(_*_(V1, V2)) -> U231^1(isNzNat(V1), V2) 18.38/8.42 ISNZNAT(_*_(V1, V2)) -> ISNZNAT(V1) 18.38/8.42 ISNZNAT(gcd(V1, V2)) -> U241^1(isNzNat(V1), V2) 18.38/8.42 ISNZNAT(gcd(V1, V2)) -> ISNZNAT(V1) 18.38/8.42 ISNZNAT(s_(V1)) -> U251^1(isNat(V1)) 18.38/8.42 ISNZNAT(s_(V1)) -> ISNAT(V1) 18.38/8.42 P_(s_(N)) -> U261^1(isNat(N), N) 18.38/8.42 P_(s_(N)) -> ISNAT(N) 18.38/8.42 QUOT(M', M') -> U271^1(isNzNat(M')) 18.38/8.42 QUOT(M', M') -> ISNZNAT(M') 18.38/8.42 QUOT(N, M') -> U281^1(isNzNat(M'), M', N) 18.38/8.42 QUOT(N, M') -> ISNZNAT(M') 18.38/8.42 QUOT(N, M') -> U291^1(isNzNat(M'), M', N) 18.38/8.43 18.38/8.43 The TRS R consists of the following rules: 18.38/8.43 18.38/8.43 1 -> s_(0) 18.38/8.43 2 -> s_(s_(0)) 18.38/8.43 3 -> s_(s_(s_(0))) 18.38/8.43 4 -> s_(s_(s_(s_(0)))) 18.38/8.43 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.43 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.43 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.43 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.43 U102(tt, M, N) -> d(N, M) 18.38/8.43 U11(tt) -> 0 18.38/8.43 U111(tt) -> 0 18.38/8.43 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.43 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.43 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.43 U131(tt, N') -> N' 18.38/8.43 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.43 U142(tt) -> tt 18.38/8.43 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.43 U152(tt) -> tt 18.38/8.43 U161(tt) -> tt 18.38/8.43 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.43 U172(tt) -> tt 18.38/8.43 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.43 U182(tt) -> tt 18.38/8.43 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.43 U192(tt) -> tt 18.38/8.43 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.43 U202(tt) -> tt 18.38/8.43 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.43 U211(tt) -> tt 18.38/8.43 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.43 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.43 U222(tt) -> tt 18.38/8.43 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.43 U232(tt) -> tt 18.38/8.43 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.43 U242(tt) -> tt 18.38/8.43 U251(tt) -> tt 18.38/8.43 U261(tt, N) -> N 18.38/8.43 U271(tt) -> s_(0) 18.38/8.43 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.43 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.43 U283(tt) -> 0 18.38/8.43 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.43 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.43 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.43 U31(tt, N) -> N 18.38/8.43 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.43 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.43 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.43 U52(tt, M, N) -> _>_(M, N) 18.38/8.43 U61(tt) -> false 18.38/8.43 U71(tt) -> true 18.38/8.43 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.43 U82(tt, M, N) -> _>_(N, M) 18.38/8.43 U91(tt, N) -> N 18.38/8.43 _*_(N, 0) -> U11(isNat(N)) 18.38/8.43 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.43 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.43 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.43 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.43 _>_(0, M) -> U61(isNat(M)) 18.38/8.43 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.43 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.43 d(0, N) -> U91(isNat(N), N) 18.38/8.43 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.43 equal(X, X) -> tt 18.38/8.43 gcd(0, N) -> U111(isNat(N)) 18.38/8.43 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.43 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.43 isBoolean(false) -> tt 18.38/8.43 isBoolean(true) -> tt 18.38/8.43 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.43 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.43 isNat(0) -> tt 18.38/8.43 isNat(V) -> U161(isNzNat(V)) 18.38/8.43 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.43 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.43 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.43 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.43 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.43 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.43 isNzNat(1) -> tt 18.38/8.43 isNzNat(2) -> tt 18.38/8.43 isNzNat(3) -> tt 18.38/8.43 isNzNat(4) -> tt 18.38/8.43 isNzNat(5) -> tt 18.38/8.43 isNzNat(6) -> tt 18.38/8.43 isNzNat(7) -> tt 18.38/8.43 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.43 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.43 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.43 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.43 quot(M', M') -> U271(isNzNat(M')) 18.38/8.43 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.43 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.43 18.38/8.43 The set E consists of the following equations: 18.38/8.43 18.38/8.43 _*_(x, y) == _*_(y, x) 18.38/8.43 _+_(x, y) == _+_(y, x) 18.38/8.43 d(x, y) == d(y, x) 18.38/8.43 gcd(x, y) == gcd(y, x) 18.38/8.43 18.38/8.43 The set E# consists of the following equations: 18.38/8.43 18.38/8.43 _*_^1(x, y) == _*_^1(y, x) 18.38/8.43 _+_^1(x, y) == _+_^1(y, x) 18.38/8.43 D(x, y) == D(y, x) 18.38/8.43 GCD(x, y) == GCD(y, x) 18.38/8.43 18.38/8.43 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (3) EDependencyGraphProof (EQUIVALENT) 18.38/8.43 The approximation of the Equational Dependency Graph [DA_STEIN] contains 7 SCCs with 67 less nodes. 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (4) 18.38/8.43 Complex Obligation (AND) 18.38/8.43 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (5) 18.38/8.43 Obligation: 18.38/8.43 The TRS P consists of the following rules: 18.38/8.43 18.38/8.43 ISNAT(_*_(V1, V2)) -> U171^1(isNat(V1), V2) 18.38/8.43 U241^1(tt, V2) -> ISNZNAT(V2) 18.38/8.43 U181^1(tt, V2) -> ISNAT(V2) 18.38/8.43 ISNAT(d(V1, V2)) -> ISNAT(V1) 18.38/8.43 ISNAT(V) -> ISNZNAT(V) 18.38/8.43 ISNAT(p_(V1)) -> ISNZNAT(V1) 18.38/8.43 ISNAT(gcd(V1, V2)) -> U201^1(isNat(V1), V2) 18.38/8.43 U201^1(tt, V2) -> ISNAT(V2) 18.38/8.43 U171^1(tt, V2) -> ISNAT(V2) 18.38/8.43 ISNZNAT(s_(V1)) -> ISNAT(V1) 18.38/8.43 U231^1(tt, V2) -> ISNZNAT(V2) 18.38/8.43 ISNZNAT(_*_(V1, V2)) -> ISNZNAT(V1) 18.38/8.43 ISNZNAT(gcd(V1, V2)) -> U241^1(isNzNat(V1), V2) 18.38/8.43 ISNZNAT(gcd(V1, V2)) -> ISNZNAT(V1) 18.38/8.43 ISNAT(_+_(V1, V2)) -> U181^1(isNat(V1), V2) 18.38/8.43 ISNAT(_+_(V1, V2)) -> ISNAT(V1) 18.38/8.43 ISNAT(d(V1, V2)) -> U191^1(isNat(V1), V2) 18.38/8.43 ISNZNAT(_*_(V1, V2)) -> U231^1(isNzNat(V1), V2) 18.38/8.43 ISNAT(_*_(V1, V2)) -> ISNAT(V1) 18.38/8.43 ISNAT(gcd(V1, V2)) -> ISNAT(V1) 18.38/8.43 U221^1(tt, V2) -> ISNZNAT(V2) 18.38/8.43 ISNAT(quot(V1, V2)) -> U221^1(isNat(V1), V2) 18.38/8.43 ISNAT(quot(V1, V2)) -> ISNAT(V1) 18.38/8.43 U191^1(tt, V2) -> ISNAT(V2) 18.38/8.43 18.38/8.43 The TRS R consists of the following rules: 18.38/8.43 18.38/8.43 1 -> s_(0) 18.38/8.43 2 -> s_(s_(0)) 18.38/8.43 3 -> s_(s_(s_(0))) 18.38/8.43 4 -> s_(s_(s_(s_(0)))) 18.38/8.43 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.43 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.43 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.43 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.43 U102(tt, M, N) -> d(N, M) 18.38/8.43 U11(tt) -> 0 18.38/8.43 U111(tt) -> 0 18.38/8.43 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.43 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.43 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.43 U131(tt, N') -> N' 18.38/8.43 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.43 U142(tt) -> tt 18.38/8.43 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.43 U152(tt) -> tt 18.38/8.43 U161(tt) -> tt 18.38/8.43 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.43 U172(tt) -> tt 18.38/8.43 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.43 U182(tt) -> tt 18.38/8.43 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.43 U192(tt) -> tt 18.38/8.43 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.43 U202(tt) -> tt 18.38/8.43 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.43 U211(tt) -> tt 18.38/8.43 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.43 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.43 U222(tt) -> tt 18.38/8.43 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.43 U232(tt) -> tt 18.38/8.43 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.43 U242(tt) -> tt 18.38/8.43 U251(tt) -> tt 18.38/8.43 U261(tt, N) -> N 18.38/8.43 U271(tt) -> s_(0) 18.38/8.43 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.43 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.43 U283(tt) -> 0 18.38/8.43 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.43 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.43 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.43 U31(tt, N) -> N 18.38/8.43 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.43 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.43 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.43 U52(tt, M, N) -> _>_(M, N) 18.38/8.43 U61(tt) -> false 18.38/8.43 U71(tt) -> true 18.38/8.43 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.43 U82(tt, M, N) -> _>_(N, M) 18.38/8.43 U91(tt, N) -> N 18.38/8.43 _*_(N, 0) -> U11(isNat(N)) 18.38/8.43 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.43 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.43 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.43 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.43 _>_(0, M) -> U61(isNat(M)) 18.38/8.43 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.43 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.43 d(0, N) -> U91(isNat(N), N) 18.38/8.43 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.43 equal(X, X) -> tt 18.38/8.43 gcd(0, N) -> U111(isNat(N)) 18.38/8.43 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.43 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.43 isBoolean(false) -> tt 18.38/8.43 isBoolean(true) -> tt 18.38/8.43 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.43 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.43 isNat(0) -> tt 18.38/8.43 isNat(V) -> U161(isNzNat(V)) 18.38/8.43 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.43 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.43 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.43 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.43 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.43 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.43 isNzNat(1) -> tt 18.38/8.43 isNzNat(2) -> tt 18.38/8.43 isNzNat(3) -> tt 18.38/8.43 isNzNat(4) -> tt 18.38/8.43 isNzNat(5) -> tt 18.38/8.43 isNzNat(6) -> tt 18.38/8.43 isNzNat(7) -> tt 18.38/8.43 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.43 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.43 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.43 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.43 quot(M', M') -> U271(isNzNat(M')) 18.38/8.43 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.43 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.43 18.38/8.43 The set E consists of the following equations: 18.38/8.43 18.38/8.43 _*_(x, y) == _*_(y, x) 18.38/8.43 _+_(x, y) == _+_(y, x) 18.38/8.43 d(x, y) == d(y, x) 18.38/8.43 gcd(x, y) == gcd(y, x) 18.38/8.43 18.38/8.43 The set E# consists of the following equations: 18.38/8.43 18.38/8.43 _*_^1(x, y) == _*_^1(y, x) 18.38/8.43 _+_^1(x, y) == _+_^1(y, x) 18.38/8.43 D(x, y) == D(y, x) 18.38/8.43 GCD(x, y) == GCD(y, x) 18.38/8.43 18.38/8.43 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (6) ESharpUsableEquationsProof (EQUIVALENT) 18.38/8.43 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 18.38/8.43 _*_^1(x, y) == _*_^1(y, x) 18.38/8.43 _+_^1(x, y) == _+_^1(y, x) 18.38/8.43 D(x, y) == D(y, x) 18.38/8.43 GCD(x, y) == GCD(y, x) 18.38/8.43 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (7) 18.38/8.43 Obligation: 18.38/8.43 The TRS P consists of the following rules: 18.38/8.43 18.38/8.43 ISNAT(_*_(V1, V2)) -> U171^1(isNat(V1), V2) 18.38/8.43 U241^1(tt, V2) -> ISNZNAT(V2) 18.38/8.43 U181^1(tt, V2) -> ISNAT(V2) 18.38/8.43 ISNAT(d(V1, V2)) -> ISNAT(V1) 18.38/8.43 ISNAT(V) -> ISNZNAT(V) 18.38/8.43 ISNAT(p_(V1)) -> ISNZNAT(V1) 18.38/8.43 ISNAT(gcd(V1, V2)) -> U201^1(isNat(V1), V2) 18.38/8.43 U201^1(tt, V2) -> ISNAT(V2) 18.38/8.43 U171^1(tt, V2) -> ISNAT(V2) 18.38/8.43 ISNZNAT(s_(V1)) -> ISNAT(V1) 18.38/8.43 U231^1(tt, V2) -> ISNZNAT(V2) 18.38/8.43 ISNZNAT(_*_(V1, V2)) -> ISNZNAT(V1) 18.38/8.43 ISNZNAT(gcd(V1, V2)) -> U241^1(isNzNat(V1), V2) 18.38/8.43 ISNZNAT(gcd(V1, V2)) -> ISNZNAT(V1) 18.38/8.43 ISNAT(_+_(V1, V2)) -> U181^1(isNat(V1), V2) 18.38/8.43 ISNAT(_+_(V1, V2)) -> ISNAT(V1) 18.38/8.43 ISNAT(d(V1, V2)) -> U191^1(isNat(V1), V2) 18.38/8.43 ISNZNAT(_*_(V1, V2)) -> U231^1(isNzNat(V1), V2) 18.38/8.43 ISNAT(_*_(V1, V2)) -> ISNAT(V1) 18.38/8.43 ISNAT(gcd(V1, V2)) -> ISNAT(V1) 18.38/8.43 U221^1(tt, V2) -> ISNZNAT(V2) 18.38/8.43 ISNAT(quot(V1, V2)) -> U221^1(isNat(V1), V2) 18.38/8.43 ISNAT(quot(V1, V2)) -> ISNAT(V1) 18.38/8.43 U191^1(tt, V2) -> ISNAT(V2) 18.38/8.43 18.38/8.43 The TRS R consists of the following rules: 18.38/8.43 18.38/8.43 1 -> s_(0) 18.38/8.43 2 -> s_(s_(0)) 18.38/8.43 3 -> s_(s_(s_(0))) 18.38/8.43 4 -> s_(s_(s_(s_(0)))) 18.38/8.43 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.43 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.43 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.43 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.43 U102(tt, M, N) -> d(N, M) 18.38/8.43 U11(tt) -> 0 18.38/8.43 U111(tt) -> 0 18.38/8.43 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.43 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.43 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.43 U131(tt, N') -> N' 18.38/8.43 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.43 U142(tt) -> tt 18.38/8.43 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.43 U152(tt) -> tt 18.38/8.43 U161(tt) -> tt 18.38/8.43 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.43 U172(tt) -> tt 18.38/8.43 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.43 U182(tt) -> tt 18.38/8.43 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.43 U192(tt) -> tt 18.38/8.43 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.43 U202(tt) -> tt 18.38/8.43 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.43 U211(tt) -> tt 18.38/8.43 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.43 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.43 U222(tt) -> tt 18.38/8.43 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.43 U232(tt) -> tt 18.38/8.43 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.43 U242(tt) -> tt 18.38/8.43 U251(tt) -> tt 18.38/8.43 U261(tt, N) -> N 18.38/8.43 U271(tt) -> s_(0) 18.38/8.43 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.43 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.43 U283(tt) -> 0 18.38/8.43 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.43 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.43 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.43 U31(tt, N) -> N 18.38/8.43 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.43 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.43 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.43 U52(tt, M, N) -> _>_(M, N) 18.38/8.43 U61(tt) -> false 18.38/8.43 U71(tt) -> true 18.38/8.43 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.43 U82(tt, M, N) -> _>_(N, M) 18.38/8.43 U91(tt, N) -> N 18.38/8.43 _*_(N, 0) -> U11(isNat(N)) 18.38/8.43 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.43 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.43 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.43 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.43 _>_(0, M) -> U61(isNat(M)) 18.38/8.43 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.43 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.43 d(0, N) -> U91(isNat(N), N) 18.38/8.43 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.43 equal(X, X) -> tt 18.38/8.43 gcd(0, N) -> U111(isNat(N)) 18.38/8.43 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.43 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.43 isBoolean(false) -> tt 18.38/8.43 isBoolean(true) -> tt 18.38/8.43 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.43 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.43 isNat(0) -> tt 18.38/8.43 isNat(V) -> U161(isNzNat(V)) 18.38/8.43 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.43 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.43 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.43 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.43 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.43 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.43 isNzNat(1) -> tt 18.38/8.43 isNzNat(2) -> tt 18.38/8.43 isNzNat(3) -> tt 18.38/8.43 isNzNat(4) -> tt 18.38/8.43 isNzNat(5) -> tt 18.38/8.43 isNzNat(6) -> tt 18.38/8.43 isNzNat(7) -> tt 18.38/8.43 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.43 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.43 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.43 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.43 quot(M', M') -> U271(isNzNat(M')) 18.38/8.43 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.43 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.43 18.38/8.43 The set E consists of the following equations: 18.38/8.43 18.38/8.43 _*_(x, y) == _*_(y, x) 18.38/8.43 _+_(x, y) == _+_(y, x) 18.38/8.43 d(x, y) == d(y, x) 18.38/8.43 gcd(x, y) == gcd(y, x) 18.38/8.43 18.38/8.43 E# is empty. 18.38/8.43 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (8) EUsableRulesReductionPairsProof (EQUIVALENT) 18.38/8.43 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. 18.38/8.43 18.38/8.43 The following dependency pairs can be deleted: 18.38/8.43 18.38/8.43 ISNAT(_*_(V1, V2)) -> U171^1(isNat(V1), V2) 18.38/8.43 ISNAT(d(V1, V2)) -> ISNAT(V1) 18.38/8.43 ISNAT(p_(V1)) -> ISNZNAT(V1) 18.38/8.43 ISNAT(gcd(V1, V2)) -> U201^1(isNat(V1), V2) 18.38/8.43 ISNZNAT(s_(V1)) -> ISNAT(V1) 18.38/8.43 ISNZNAT(_*_(V1, V2)) -> ISNZNAT(V1) 18.38/8.43 ISNZNAT(gcd(V1, V2)) -> U241^1(isNzNat(V1), V2) 18.38/8.43 ISNZNAT(gcd(V1, V2)) -> ISNZNAT(V1) 18.38/8.43 ISNAT(_+_(V1, V2)) -> U181^1(isNat(V1), V2) 18.38/8.43 ISNAT(_+_(V1, V2)) -> ISNAT(V1) 18.38/8.43 ISNAT(d(V1, V2)) -> U191^1(isNat(V1), V2) 18.38/8.43 ISNZNAT(_*_(V1, V2)) -> U231^1(isNzNat(V1), V2) 18.38/8.43 ISNAT(_*_(V1, V2)) -> ISNAT(V1) 18.38/8.43 ISNAT(gcd(V1, V2)) -> ISNAT(V1) 18.38/8.43 ISNAT(quot(V1, V2)) -> U221^1(isNat(V1), V2) 18.38/8.43 ISNAT(quot(V1, V2)) -> ISNAT(V1) 18.38/8.43 The following rules are removed from R: 18.38/8.43 18.38/8.43 1 -> s_(0) 18.38/8.43 2 -> s_(s_(0)) 18.38/8.43 3 -> s_(s_(s_(0))) 18.38/8.43 4 -> s_(s_(s_(s_(0)))) 18.38/8.43 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.43 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.43 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.43 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.43 U102(tt, M, N) -> d(N, M) 18.38/8.43 U11(tt) -> 0 18.38/8.43 U111(tt) -> 0 18.38/8.43 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.43 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.43 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.43 U131(tt, N') -> N' 18.38/8.43 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.43 U142(tt) -> tt 18.38/8.43 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.43 U152(tt) -> tt 18.38/8.43 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.43 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.43 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.43 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.43 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.43 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.43 U261(tt, N) -> N 18.38/8.43 U271(tt) -> s_(0) 18.38/8.43 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.43 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.43 U283(tt) -> 0 18.38/8.43 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.43 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.43 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.43 U31(tt, N) -> N 18.38/8.43 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.43 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.43 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.43 U52(tt, M, N) -> _>_(M, N) 18.38/8.43 U61(tt) -> false 18.38/8.43 U71(tt) -> true 18.38/8.43 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.43 U82(tt, M, N) -> _>_(N, M) 18.38/8.43 U91(tt, N) -> N 18.38/8.43 _*_(N, 0) -> U11(isNat(N)) 18.38/8.43 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.43 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.43 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.43 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.43 _>_(0, M) -> U61(isNat(M)) 18.38/8.43 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.43 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.43 d(0, N) -> U91(isNat(N), N) 18.38/8.43 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.43 equal(X, X) -> tt 18.38/8.43 gcd(0, N) -> U111(isNat(N)) 18.38/8.43 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.43 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.43 isBoolean(false) -> tt 18.38/8.43 isBoolean(true) -> tt 18.38/8.43 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.43 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.43 isNat(0) -> tt 18.38/8.43 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.43 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.43 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.43 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.43 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.43 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.43 isNzNat(1) -> tt 18.38/8.43 isNzNat(2) -> tt 18.38/8.43 isNzNat(3) -> tt 18.38/8.43 isNzNat(4) -> tt 18.38/8.43 isNzNat(5) -> tt 18.38/8.43 isNzNat(6) -> tt 18.38/8.43 isNzNat(7) -> tt 18.38/8.43 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.43 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.43 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.43 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.43 quot(M', M') -> U271(isNzNat(M')) 18.38/8.43 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.43 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.43 The following equations are removed from E: 18.38/8.43 18.38/8.43 _*_(x, y) == _*_(y, x) 18.38/8.43 _+_(x, y) == _+_(y, x) 18.38/8.43 d(x, y) == d(y, x) 18.38/8.43 gcd(x, y) == gcd(y, x) 18.38/8.43 Used ordering: POLO with Polynomial interpretation [POLO]: 18.38/8.43 18.38/8.43 POL(0) = 0 18.38/8.43 POL(1) = 0 18.38/8.43 POL(2) = 0 18.38/8.43 POL(3) = 0 18.38/8.43 POL(4) = 0 18.38/8.43 POL(5) = 0 18.38/8.43 POL(6) = 0 18.38/8.43 POL(7) = 0 18.38/8.43 POL(ISNAT(x_1)) = x_1 18.38/8.43 POL(ISNZNAT(x_1)) = x_1 18.38/8.43 POL(U161(x_1)) = 2*x_1 18.38/8.43 POL(U171(x_1, x_2)) = 2 + x_1 + 2*x_2 18.38/8.43 POL(U171^1(x_1, x_2)) = x_1 + x_2 18.38/8.43 POL(U172(x_1)) = x_1 18.38/8.43 POL(U181(x_1, x_2)) = 2 + 2*x_1 + 3*x_2 18.38/8.43 POL(U181^1(x_1, x_2)) = x_1 + 2*x_2 18.38/8.43 POL(U182(x_1)) = x_1 18.38/8.43 POL(U191(x_1, x_2)) = 2 + 2*x_1 + 3*x_2 18.38/8.43 POL(U191^1(x_1, x_2)) = x_1 + 2*x_2 18.38/8.43 POL(U192(x_1)) = x_1 18.38/8.43 POL(U201(x_1, x_2)) = x_1 + 2*x_2 18.38/8.43 POL(U201^1(x_1, x_2)) = x_1 + x_2 18.38/8.43 POL(U202(x_1)) = x_1 18.38/8.43 POL(U211(x_1)) = x_1 18.38/8.43 POL(U221(x_1, x_2)) = 2 + x_1 + 2*x_2 18.38/8.43 POL(U221^1(x_1, x_2)) = x_1 + x_2 18.38/8.43 POL(U222(x_1)) = 2*x_1 18.38/8.43 POL(U231(x_1, x_2)) = x_1 + x_2 18.38/8.43 POL(U231^1(x_1, x_2)) = x_1 + x_2 18.38/8.43 POL(U232(x_1)) = x_1 18.38/8.43 POL(U241(x_1, x_2)) = x_1 + x_2 18.38/8.43 POL(U241^1(x_1, x_2)) = x_1 + x_2 18.38/8.43 POL(U242(x_1)) = x_1 18.38/8.43 POL(U251(x_1)) = x_1 18.38/8.43 POL(_*_(x_1, x_2)) = 2 + 2*x_1 + x_2 18.38/8.43 POL(_+_(x_1, x_2)) = 2 + 3*x_1 + 3*x_2 18.38/8.43 POL(d(x_1, x_2)) = 2 + 3*x_1 + 3*x_2 18.38/8.43 POL(gcd(x_1, x_2)) = 2*x_1 + x_2 18.38/8.43 POL(isNat(x_1)) = 2*x_1 18.38/8.43 POL(isNzNat(x_1)) = x_1 18.38/8.43 POL(p_(x_1)) = x_1 18.38/8.43 POL(quot(x_1, x_2)) = 2 + 2*x_1 + x_2 18.38/8.43 POL(s_(x_1)) = 2*x_1 18.38/8.43 POL(tt) = 0 18.38/8.43 18.38/8.43 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (9) 18.38/8.43 Obligation: 18.38/8.43 The TRS P consists of the following rules: 18.38/8.43 18.38/8.43 U241^1(tt, V2) -> ISNZNAT(V2) 18.38/8.43 U181^1(tt, V2) -> ISNAT(V2) 18.38/8.43 ISNAT(V) -> ISNZNAT(V) 18.38/8.43 U201^1(tt, V2) -> ISNAT(V2) 18.38/8.43 U171^1(tt, V2) -> ISNAT(V2) 18.38/8.43 U231^1(tt, V2) -> ISNZNAT(V2) 18.38/8.43 U221^1(tt, V2) -> ISNZNAT(V2) 18.38/8.43 U191^1(tt, V2) -> ISNAT(V2) 18.38/8.43 18.38/8.43 The TRS R consists of the following rules: 18.38/8.43 18.38/8.43 U242(tt) -> tt 18.38/8.43 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.43 U202(tt) -> tt 18.38/8.43 U251(tt) -> tt 18.38/8.43 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.43 U222(tt) -> tt 18.38/8.43 U161(tt) -> tt 18.38/8.43 isNat(V) -> U161(isNzNat(V)) 18.38/8.43 U172(tt) -> tt 18.38/8.43 U232(tt) -> tt 18.38/8.43 U192(tt) -> tt 18.38/8.43 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.43 U182(tt) -> tt 18.38/8.43 U211(tt) -> tt 18.38/8.43 18.38/8.43 E is empty. 18.38/8.43 E# is empty. 18.38/8.43 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (10) EDependencyGraphProof (EQUIVALENT) 18.38/8.43 The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 8 less nodes. 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (11) 18.38/8.43 TRUE 18.38/8.43 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (12) 18.38/8.43 Obligation: 18.38/8.43 The TRS P consists of the following rules: 18.38/8.43 18.38/8.43 U81^1(tt, M, N) -> U82^1(isNat(N), M, N) 18.38/8.43 _>_^1(s_(N), s_(M)) -> U81^1(isNat(M), M, N) 18.38/8.43 U82^1(tt, M, N) -> _>_^1(N, M) 18.38/8.43 18.38/8.43 The TRS R consists of the following rules: 18.38/8.43 18.38/8.43 1 -> s_(0) 18.38/8.43 2 -> s_(s_(0)) 18.38/8.43 3 -> s_(s_(s_(0))) 18.38/8.43 4 -> s_(s_(s_(s_(0)))) 18.38/8.43 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.43 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.43 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.43 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.43 U102(tt, M, N) -> d(N, M) 18.38/8.43 U11(tt) -> 0 18.38/8.43 U111(tt) -> 0 18.38/8.43 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.43 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.43 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.43 U131(tt, N') -> N' 18.38/8.43 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.43 U142(tt) -> tt 18.38/8.43 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.43 U152(tt) -> tt 18.38/8.43 U161(tt) -> tt 18.38/8.43 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.43 U172(tt) -> tt 18.38/8.43 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.43 U182(tt) -> tt 18.38/8.43 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.43 U192(tt) -> tt 18.38/8.43 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.43 U202(tt) -> tt 18.38/8.43 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.43 U211(tt) -> tt 18.38/8.43 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.43 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.43 U222(tt) -> tt 18.38/8.43 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.43 U232(tt) -> tt 18.38/8.43 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.43 U242(tt) -> tt 18.38/8.43 U251(tt) -> tt 18.38/8.43 U261(tt, N) -> N 18.38/8.43 U271(tt) -> s_(0) 18.38/8.43 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.43 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.43 U283(tt) -> 0 18.38/8.43 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.43 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.43 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.43 U31(tt, N) -> N 18.38/8.43 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.43 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.43 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.43 U52(tt, M, N) -> _>_(M, N) 18.38/8.43 U61(tt) -> false 18.38/8.43 U71(tt) -> true 18.38/8.43 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.43 U82(tt, M, N) -> _>_(N, M) 18.38/8.43 U91(tt, N) -> N 18.38/8.43 _*_(N, 0) -> U11(isNat(N)) 18.38/8.43 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.43 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.43 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.43 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.43 _>_(0, M) -> U61(isNat(M)) 18.38/8.43 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.43 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.43 d(0, N) -> U91(isNat(N), N) 18.38/8.43 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.43 equal(X, X) -> tt 18.38/8.43 gcd(0, N) -> U111(isNat(N)) 18.38/8.43 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.43 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.43 isBoolean(false) -> tt 18.38/8.43 isBoolean(true) -> tt 18.38/8.43 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.43 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.43 isNat(0) -> tt 18.38/8.43 isNat(V) -> U161(isNzNat(V)) 18.38/8.43 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.43 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.43 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.43 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.43 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.43 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.43 isNzNat(1) -> tt 18.38/8.43 isNzNat(2) -> tt 18.38/8.43 isNzNat(3) -> tt 18.38/8.43 isNzNat(4) -> tt 18.38/8.43 isNzNat(5) -> tt 18.38/8.43 isNzNat(6) -> tt 18.38/8.43 isNzNat(7) -> tt 18.38/8.43 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.43 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.43 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.43 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.43 quot(M', M') -> U271(isNzNat(M')) 18.38/8.43 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.43 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.43 18.38/8.43 The set E consists of the following equations: 18.38/8.43 18.38/8.43 _*_(x, y) == _*_(y, x) 18.38/8.43 _+_(x, y) == _+_(y, x) 18.38/8.43 d(x, y) == d(y, x) 18.38/8.43 gcd(x, y) == gcd(y, x) 18.38/8.43 18.38/8.43 The set E# consists of the following equations: 18.38/8.43 18.38/8.43 _*_^1(x, y) == _*_^1(y, x) 18.38/8.43 _+_^1(x, y) == _+_^1(y, x) 18.38/8.43 D(x, y) == D(y, x) 18.38/8.43 GCD(x, y) == GCD(y, x) 18.38/8.43 18.38/8.43 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (13) ESharpUsableEquationsProof (EQUIVALENT) 18.38/8.43 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 18.38/8.43 _*_^1(x, y) == _*_^1(y, x) 18.38/8.43 _+_^1(x, y) == _+_^1(y, x) 18.38/8.43 D(x, y) == D(y, x) 18.38/8.43 GCD(x, y) == GCD(y, x) 18.38/8.43 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (14) 18.38/8.43 Obligation: 18.38/8.43 The TRS P consists of the following rules: 18.38/8.43 18.38/8.43 U81^1(tt, M, N) -> U82^1(isNat(N), M, N) 18.38/8.43 _>_^1(s_(N), s_(M)) -> U81^1(isNat(M), M, N) 18.38/8.43 U82^1(tt, M, N) -> _>_^1(N, M) 18.38/8.43 18.38/8.43 The TRS R consists of the following rules: 18.38/8.43 18.38/8.43 1 -> s_(0) 18.38/8.43 2 -> s_(s_(0)) 18.38/8.43 3 -> s_(s_(s_(0))) 18.38/8.43 4 -> s_(s_(s_(s_(0)))) 18.38/8.43 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.43 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.43 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.43 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.43 U102(tt, M, N) -> d(N, M) 18.38/8.43 U11(tt) -> 0 18.38/8.43 U111(tt) -> 0 18.38/8.43 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.43 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.43 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.43 U131(tt, N') -> N' 18.38/8.43 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.43 U142(tt) -> tt 18.38/8.43 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.43 U152(tt) -> tt 18.38/8.43 U161(tt) -> tt 18.38/8.43 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.43 U172(tt) -> tt 18.38/8.43 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.43 U182(tt) -> tt 18.38/8.43 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.43 U192(tt) -> tt 18.38/8.43 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.43 U202(tt) -> tt 18.38/8.43 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.43 U211(tt) -> tt 18.38/8.43 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.43 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.43 U222(tt) -> tt 18.38/8.43 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.43 U232(tt) -> tt 18.38/8.43 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.43 U242(tt) -> tt 18.38/8.43 U251(tt) -> tt 18.38/8.43 U261(tt, N) -> N 18.38/8.43 U271(tt) -> s_(0) 18.38/8.43 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.43 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.43 U283(tt) -> 0 18.38/8.43 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.43 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.43 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.43 U31(tt, N) -> N 18.38/8.43 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.43 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.43 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.43 U52(tt, M, N) -> _>_(M, N) 18.38/8.43 U61(tt) -> false 18.38/8.43 U71(tt) -> true 18.38/8.43 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.43 U82(tt, M, N) -> _>_(N, M) 18.38/8.43 U91(tt, N) -> N 18.38/8.43 _*_(N, 0) -> U11(isNat(N)) 18.38/8.43 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.43 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.43 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.43 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.43 _>_(0, M) -> U61(isNat(M)) 18.38/8.43 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.43 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.43 d(0, N) -> U91(isNat(N), N) 18.38/8.43 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.43 equal(X, X) -> tt 18.38/8.43 gcd(0, N) -> U111(isNat(N)) 18.38/8.43 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.43 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.43 isBoolean(false) -> tt 18.38/8.43 isBoolean(true) -> tt 18.38/8.43 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.43 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.43 isNat(0) -> tt 18.38/8.43 isNat(V) -> U161(isNzNat(V)) 18.38/8.43 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.43 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.43 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.43 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.43 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.43 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.43 isNzNat(1) -> tt 18.38/8.43 isNzNat(2) -> tt 18.38/8.43 isNzNat(3) -> tt 18.38/8.43 isNzNat(4) -> tt 18.38/8.43 isNzNat(5) -> tt 18.38/8.43 isNzNat(6) -> tt 18.38/8.43 isNzNat(7) -> tt 18.38/8.43 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.43 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.43 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.43 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.43 quot(M', M') -> U271(isNzNat(M')) 18.38/8.43 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.43 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.43 18.38/8.43 The set E consists of the following equations: 18.38/8.43 18.38/8.43 _*_(x, y) == _*_(y, x) 18.38/8.43 _+_(x, y) == _+_(y, x) 18.38/8.43 d(x, y) == d(y, x) 18.38/8.43 gcd(x, y) == gcd(y, x) 18.38/8.43 18.38/8.43 E# is empty. 18.38/8.43 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (15) EUsableRulesReductionPairsProof (EQUIVALENT) 18.38/8.43 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. 18.38/8.43 18.38/8.43 The following dependency pairs can be deleted: 18.38/8.43 18.38/8.43 _>_^1(s_(N), s_(M)) -> U81^1(isNat(M), M, N) 18.38/8.43 The following rules are removed from R: 18.38/8.43 18.38/8.43 1 -> s_(0) 18.38/8.43 2 -> s_(s_(0)) 18.38/8.43 3 -> s_(s_(s_(0))) 18.38/8.43 4 -> s_(s_(s_(s_(0)))) 18.38/8.43 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.43 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.43 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.43 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.43 U102(tt, M, N) -> d(N, M) 18.38/8.43 U11(tt) -> 0 18.38/8.43 U111(tt) -> 0 18.38/8.43 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.43 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.43 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.43 U131(tt, N') -> N' 18.38/8.43 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.43 U142(tt) -> tt 18.38/8.43 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.43 U152(tt) -> tt 18.38/8.43 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.43 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.43 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.43 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.43 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.43 U261(tt, N) -> N 18.38/8.43 U271(tt) -> s_(0) 18.38/8.43 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.43 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.43 U283(tt) -> 0 18.38/8.43 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.43 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.43 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.43 U31(tt, N) -> N 18.38/8.43 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.43 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.43 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.43 U52(tt, M, N) -> _>_(M, N) 18.38/8.43 U61(tt) -> false 18.38/8.43 U71(tt) -> true 18.38/8.43 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.43 U82(tt, M, N) -> _>_(N, M) 18.38/8.43 U91(tt, N) -> N 18.38/8.43 _*_(N, 0) -> U11(isNat(N)) 18.38/8.43 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.43 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.43 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.43 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.43 _>_(0, M) -> U61(isNat(M)) 18.38/8.43 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.43 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.43 d(0, N) -> U91(isNat(N), N) 18.38/8.43 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.43 equal(X, X) -> tt 18.38/8.43 gcd(0, N) -> U111(isNat(N)) 18.38/8.43 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.43 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.43 isBoolean(false) -> tt 18.38/8.43 isBoolean(true) -> tt 18.38/8.43 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.43 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.43 isNat(0) -> tt 18.38/8.43 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.43 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.43 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.43 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.43 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.43 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.43 isNzNat(1) -> tt 18.38/8.43 isNzNat(2) -> tt 18.38/8.43 isNzNat(3) -> tt 18.38/8.43 isNzNat(4) -> tt 18.38/8.43 isNzNat(5) -> tt 18.38/8.43 isNzNat(6) -> tt 18.38/8.43 isNzNat(7) -> tt 18.38/8.43 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.43 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.43 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.43 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.43 quot(M', M') -> U271(isNzNat(M')) 18.38/8.43 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.43 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.43 The following equations are removed from E: 18.38/8.43 18.38/8.43 _*_(x, y) == _*_(y, x) 18.38/8.43 _+_(x, y) == _+_(y, x) 18.38/8.43 d(x, y) == d(y, x) 18.38/8.43 gcd(x, y) == gcd(y, x) 18.38/8.43 Used ordering: POLO with Polynomial interpretation [POLO]: 18.38/8.43 18.38/8.43 POL(0) = 0 18.38/8.43 POL(1) = 0 18.38/8.43 POL(2) = 0 18.38/8.43 POL(3) = 0 18.38/8.43 POL(4) = 0 18.38/8.43 POL(5) = 0 18.38/8.43 POL(6) = 0 18.38/8.43 POL(7) = 0 18.38/8.43 POL(U161(x_1)) = 2*x_1 18.38/8.43 POL(U171(x_1, x_2)) = 2*x_1 + 2*x_2 18.38/8.43 POL(U172(x_1)) = x_1 18.38/8.43 POL(U181(x_1, x_2)) = 2*x_1 + 3*x_2 18.38/8.43 POL(U182(x_1)) = x_1 18.38/8.43 POL(U191(x_1, x_2)) = 2*x_1 + 3*x_2 18.38/8.43 POL(U192(x_1)) = x_1 18.38/8.43 POL(U201(x_1, x_2)) = 2*x_1 + 2*x_2 18.38/8.43 POL(U202(x_1)) = x_1 18.38/8.43 POL(U211(x_1)) = 2*x_1 18.38/8.43 POL(U221(x_1, x_2)) = 2 + x_1 + 3*x_2 18.38/8.43 POL(U222(x_1)) = 2*x_1 18.38/8.43 POL(U231(x_1, x_2)) = 2 + x_1 + x_2 18.38/8.43 POL(U232(x_1)) = x_1 18.38/8.43 POL(U241(x_1, x_2)) = 2 + x_1 + x_2 18.38/8.43 POL(U242(x_1)) = x_1 18.38/8.43 POL(U251(x_1)) = x_1 18.38/8.43 POL(U81^1(x_1, x_2, x_3)) = x_1 + 2*x_2 + 3*x_3 18.38/8.43 POL(U82^1(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 18.38/8.43 POL(_*_(x_1, x_2)) = 2 + 3*x_1 + x_2 18.38/8.43 POL(_+_(x_1, x_2)) = 3 + 3*x_1 + 3*x_2 18.38/8.43 POL(_>_^1(x_1, x_2)) = x_1 + 2*x_2 18.38/8.43 POL(d(x_1, x_2)) = 3 + 3*x_1 + 3*x_2 18.38/8.43 POL(gcd(x_1, x_2)) = 3 + 2*x_1 + x_2 18.38/8.43 POL(isNat(x_1)) = 2*x_1 18.38/8.43 POL(isNzNat(x_1)) = x_1 18.38/8.43 POL(p_(x_1)) = 3 + 2*x_1 18.38/8.43 POL(quot(x_1, x_2)) = 1 + 2*x_1 + 3*x_2 18.38/8.43 POL(s_(x_1)) = 3*x_1 18.38/8.43 POL(tt) = 0 18.38/8.43 18.38/8.43 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (16) 18.38/8.43 Obligation: 18.38/8.43 The TRS P consists of the following rules: 18.38/8.43 18.38/8.43 U81^1(tt, M, N) -> U82^1(isNat(N), M, N) 18.38/8.43 U82^1(tt, M, N) -> _>_^1(N, M) 18.38/8.43 18.38/8.43 The TRS R consists of the following rules: 18.38/8.43 18.38/8.43 U242(tt) -> tt 18.38/8.43 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.43 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.43 U202(tt) -> tt 18.38/8.43 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.43 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.43 U251(tt) -> tt 18.38/8.43 U222(tt) -> tt 18.38/8.43 U161(tt) -> tt 18.38/8.43 isNat(V) -> U161(isNzNat(V)) 18.38/8.43 U172(tt) -> tt 18.38/8.43 U232(tt) -> tt 18.38/8.43 U192(tt) -> tt 18.38/8.43 U182(tt) -> tt 18.38/8.43 U211(tt) -> tt 18.38/8.43 18.38/8.43 E is empty. 18.38/8.43 E# is empty. 18.38/8.43 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (17) EDependencyGraphProof (EQUIVALENT) 18.38/8.43 The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 2 less nodes. 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (18) 18.38/8.43 TRUE 18.38/8.43 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (19) 18.38/8.43 Obligation: 18.38/8.43 The TRS P consists of the following rules: 18.38/8.43 18.38/8.43 U41^1(tt, M, N) -> U42^1(isNat(N), M, N) 18.38/8.43 U42^1(tt, M, N) -> _+_^1(N, M) 18.38/8.43 _+_^1(s_(N), s_(M)) -> U41^1(isNat(M), M, N) 18.38/8.43 18.38/8.43 The TRS R consists of the following rules: 18.38/8.43 18.38/8.43 1 -> s_(0) 18.38/8.43 2 -> s_(s_(0)) 18.38/8.43 3 -> s_(s_(s_(0))) 18.38/8.43 4 -> s_(s_(s_(s_(0)))) 18.38/8.43 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.43 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.43 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.43 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.43 U102(tt, M, N) -> d(N, M) 18.38/8.43 U11(tt) -> 0 18.38/8.43 U111(tt) -> 0 18.38/8.43 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.43 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.43 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.43 U131(tt, N') -> N' 18.38/8.43 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.43 U142(tt) -> tt 18.38/8.43 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.43 U152(tt) -> tt 18.38/8.43 U161(tt) -> tt 18.38/8.43 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.43 U172(tt) -> tt 18.38/8.43 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.43 U182(tt) -> tt 18.38/8.43 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.43 U192(tt) -> tt 18.38/8.43 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.43 U202(tt) -> tt 18.38/8.43 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.43 U211(tt) -> tt 18.38/8.43 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.43 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.43 U222(tt) -> tt 18.38/8.43 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.43 U232(tt) -> tt 18.38/8.43 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.43 U242(tt) -> tt 18.38/8.43 U251(tt) -> tt 18.38/8.43 U261(tt, N) -> N 18.38/8.43 U271(tt) -> s_(0) 18.38/8.43 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.43 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.43 U283(tt) -> 0 18.38/8.43 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.43 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.43 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.43 U31(tt, N) -> N 18.38/8.43 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.43 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.43 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.43 U52(tt, M, N) -> _>_(M, N) 18.38/8.43 U61(tt) -> false 18.38/8.43 U71(tt) -> true 18.38/8.43 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.43 U82(tt, M, N) -> _>_(N, M) 18.38/8.43 U91(tt, N) -> N 18.38/8.43 _*_(N, 0) -> U11(isNat(N)) 18.38/8.43 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.43 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.43 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.43 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.43 _>_(0, M) -> U61(isNat(M)) 18.38/8.43 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.43 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.43 d(0, N) -> U91(isNat(N), N) 18.38/8.43 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.43 equal(X, X) -> tt 18.38/8.43 gcd(0, N) -> U111(isNat(N)) 18.38/8.43 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.43 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.43 isBoolean(false) -> tt 18.38/8.43 isBoolean(true) -> tt 18.38/8.43 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.43 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.43 isNat(0) -> tt 18.38/8.43 isNat(V) -> U161(isNzNat(V)) 18.38/8.43 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.43 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.43 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.43 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.43 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.43 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.43 isNzNat(1) -> tt 18.38/8.43 isNzNat(2) -> tt 18.38/8.43 isNzNat(3) -> tt 18.38/8.43 isNzNat(4) -> tt 18.38/8.43 isNzNat(5) -> tt 18.38/8.43 isNzNat(6) -> tt 18.38/8.43 isNzNat(7) -> tt 18.38/8.43 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.43 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.43 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.43 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.43 quot(M', M') -> U271(isNzNat(M')) 18.38/8.43 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.43 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.43 18.38/8.43 The set E consists of the following equations: 18.38/8.43 18.38/8.43 _*_(x, y) == _*_(y, x) 18.38/8.43 _+_(x, y) == _+_(y, x) 18.38/8.43 d(x, y) == d(y, x) 18.38/8.43 gcd(x, y) == gcd(y, x) 18.38/8.43 18.38/8.43 The set E# consists of the following equations: 18.38/8.43 18.38/8.43 _*_^1(x, y) == _*_^1(y, x) 18.38/8.43 _+_^1(x, y) == _+_^1(y, x) 18.38/8.43 D(x, y) == D(y, x) 18.38/8.43 GCD(x, y) == GCD(y, x) 18.38/8.43 18.38/8.43 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (20) ESharpUsableEquationsProof (EQUIVALENT) 18.38/8.43 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 18.38/8.43 _*_^1(x, y) == _*_^1(y, x) 18.38/8.43 D(x, y) == D(y, x) 18.38/8.43 GCD(x, y) == GCD(y, x) 18.38/8.43 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (21) 18.38/8.43 Obligation: 18.38/8.43 The TRS P consists of the following rules: 18.38/8.43 18.38/8.43 U41^1(tt, M, N) -> U42^1(isNat(N), M, N) 18.38/8.43 U42^1(tt, M, N) -> _+_^1(N, M) 18.38/8.43 _+_^1(s_(N), s_(M)) -> U41^1(isNat(M), M, N) 18.38/8.43 18.38/8.43 The TRS R consists of the following rules: 18.38/8.43 18.38/8.43 1 -> s_(0) 18.38/8.43 2 -> s_(s_(0)) 18.38/8.43 3 -> s_(s_(s_(0))) 18.38/8.43 4 -> s_(s_(s_(s_(0)))) 18.38/8.43 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.43 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.43 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.43 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.43 U102(tt, M, N) -> d(N, M) 18.38/8.43 U11(tt) -> 0 18.38/8.43 U111(tt) -> 0 18.38/8.43 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.43 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.43 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.43 U131(tt, N') -> N' 18.38/8.43 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.43 U142(tt) -> tt 18.38/8.43 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.43 U152(tt) -> tt 18.38/8.43 U161(tt) -> tt 18.38/8.43 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.43 U172(tt) -> tt 18.38/8.43 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.43 U182(tt) -> tt 18.38/8.43 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.43 U192(tt) -> tt 18.38/8.43 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.43 U202(tt) -> tt 18.38/8.43 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.43 U211(tt) -> tt 18.38/8.43 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.43 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.43 U222(tt) -> tt 18.38/8.43 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.43 U232(tt) -> tt 18.38/8.43 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.43 U242(tt) -> tt 18.38/8.43 U251(tt) -> tt 18.38/8.43 U261(tt, N) -> N 18.38/8.43 U271(tt) -> s_(0) 18.38/8.43 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.43 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.43 U283(tt) -> 0 18.38/8.43 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.43 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.43 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.43 U31(tt, N) -> N 18.38/8.43 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.43 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.43 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.43 U52(tt, M, N) -> _>_(M, N) 18.38/8.43 U61(tt) -> false 18.38/8.43 U71(tt) -> true 18.38/8.43 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.43 U82(tt, M, N) -> _>_(N, M) 18.38/8.43 U91(tt, N) -> N 18.38/8.43 _*_(N, 0) -> U11(isNat(N)) 18.38/8.43 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.43 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.43 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.43 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.43 _>_(0, M) -> U61(isNat(M)) 18.38/8.43 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.43 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.43 d(0, N) -> U91(isNat(N), N) 18.38/8.43 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.43 equal(X, X) -> tt 18.38/8.43 gcd(0, N) -> U111(isNat(N)) 18.38/8.43 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.43 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.43 isBoolean(false) -> tt 18.38/8.43 isBoolean(true) -> tt 18.38/8.43 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.43 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.43 isNat(0) -> tt 18.38/8.43 isNat(V) -> U161(isNzNat(V)) 18.38/8.43 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.43 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.43 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.43 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.43 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.43 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.43 isNzNat(1) -> tt 18.38/8.43 isNzNat(2) -> tt 18.38/8.43 isNzNat(3) -> tt 18.38/8.43 isNzNat(4) -> tt 18.38/8.43 isNzNat(5) -> tt 18.38/8.43 isNzNat(6) -> tt 18.38/8.43 isNzNat(7) -> tt 18.38/8.43 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.43 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.43 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.43 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.43 quot(M', M') -> U271(isNzNat(M')) 18.38/8.43 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.43 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.43 18.38/8.43 The set E consists of the following equations: 18.38/8.43 18.38/8.43 _*_(x, y) == _*_(y, x) 18.38/8.43 _+_(x, y) == _+_(y, x) 18.38/8.43 d(x, y) == d(y, x) 18.38/8.43 gcd(x, y) == gcd(y, x) 18.38/8.43 18.38/8.43 The set E# consists of the following equations: 18.38/8.43 18.38/8.43 _+_^1(x, y) == _+_^1(y, x) 18.38/8.43 18.38/8.43 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (22) EUsableRulesReductionPairsProof (EQUIVALENT) 18.38/8.43 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. 18.38/8.43 18.38/8.43 The following dependency pairs can be deleted: 18.38/8.43 18.38/8.43 U41^1(tt, M, N) -> U42^1(isNat(N), M, N) 18.38/8.43 _+_^1(s_(N), s_(M)) -> U41^1(isNat(M), M, N) 18.38/8.43 The following rules are removed from R: 18.38/8.43 18.38/8.43 1 -> s_(0) 18.38/8.43 2 -> s_(s_(0)) 18.38/8.43 3 -> s_(s_(s_(0))) 18.38/8.43 4 -> s_(s_(s_(s_(0)))) 18.38/8.43 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.43 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.43 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.43 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.43 U102(tt, M, N) -> d(N, M) 18.38/8.43 U11(tt) -> 0 18.38/8.43 U111(tt) -> 0 18.38/8.43 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.43 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.43 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.43 U131(tt, N') -> N' 18.38/8.43 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.43 U142(tt) -> tt 18.38/8.43 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.43 U152(tt) -> tt 18.38/8.43 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.43 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.43 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.43 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.43 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.43 U232(tt) -> tt 18.38/8.43 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.43 U261(tt, N) -> N 18.38/8.43 U271(tt) -> s_(0) 18.38/8.43 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.43 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.43 U283(tt) -> 0 18.38/8.43 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.43 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.43 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.43 U31(tt, N) -> N 18.38/8.43 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.43 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.43 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.43 U52(tt, M, N) -> _>_(M, N) 18.38/8.43 U61(tt) -> false 18.38/8.43 U71(tt) -> true 18.38/8.43 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.43 U82(tt, M, N) -> _>_(N, M) 18.38/8.43 U91(tt, N) -> N 18.38/8.43 _*_(N, 0) -> U11(isNat(N)) 18.38/8.43 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.43 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.43 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.43 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.43 _>_(0, M) -> U61(isNat(M)) 18.38/8.43 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.43 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.43 d(0, N) -> U91(isNat(N), N) 18.38/8.43 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.43 equal(X, X) -> tt 18.38/8.43 gcd(0, N) -> U111(isNat(N)) 18.38/8.43 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.43 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.43 isBoolean(false) -> tt 18.38/8.43 isBoolean(true) -> tt 18.38/8.43 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.43 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.43 isNat(0) -> tt 18.38/8.43 isNat(V) -> U161(isNzNat(V)) 18.38/8.43 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.43 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.43 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.43 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.43 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.43 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.43 isNzNat(1) -> tt 18.38/8.43 isNzNat(2) -> tt 18.38/8.43 isNzNat(3) -> tt 18.38/8.43 isNzNat(4) -> tt 18.38/8.43 isNzNat(5) -> tt 18.38/8.43 isNzNat(6) -> tt 18.38/8.43 isNzNat(7) -> tt 18.38/8.43 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.43 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.43 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.43 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.43 quot(M', M') -> U271(isNzNat(M')) 18.38/8.43 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.43 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.43 The following equations are removed from E: 18.38/8.43 18.38/8.43 _*_(x, y) == _*_(y, x) 18.38/8.43 _+_(x, y) == _+_(y, x) 18.38/8.43 d(x, y) == d(y, x) 18.38/8.43 gcd(x, y) == gcd(y, x) 18.38/8.43 Used ordering: POLO with Polynomial interpretation [POLO]: 18.38/8.43 18.38/8.43 POL(0) = 0 18.38/8.43 POL(1) = 2 18.38/8.43 POL(2) = 2 18.38/8.43 POL(3) = 2 18.38/8.43 POL(4) = 2 18.38/8.43 POL(5) = 2 18.38/8.43 POL(6) = 2 18.38/8.43 POL(7) = 2 18.38/8.43 POL(U161(x_1)) = x_1 18.38/8.43 POL(U171(x_1, x_2)) = x_1 + 2*x_2 18.38/8.43 POL(U172(x_1)) = x_1 18.38/8.43 POL(U181(x_1, x_2)) = x_1 + 3*x_2 18.38/8.43 POL(U182(x_1)) = x_1 18.38/8.43 POL(U191(x_1, x_2)) = x_1 + 2*x_2 18.38/8.43 POL(U192(x_1)) = x_1 18.38/8.43 POL(U201(x_1, x_2)) = 1 + x_1 + x_2 18.38/8.43 POL(U202(x_1)) = x_1 18.38/8.43 POL(U211(x_1)) = x_1 18.38/8.43 POL(U221(x_1, x_2)) = x_1 + 3*x_2 18.38/8.43 POL(U222(x_1)) = x_1 18.38/8.43 POL(U231(x_1, x_2)) = 2 + x_1 + 2*x_2 18.38/8.43 POL(U232(x_1)) = 2*x_1 18.38/8.43 POL(U241(x_1, x_2)) = 2*x_1 + x_2 18.38/8.43 POL(U242(x_1)) = x_1 18.38/8.43 POL(U251(x_1)) = x_1 18.38/8.43 POL(U41^1(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 3*x_3 18.38/8.43 POL(U42^1(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 18.38/8.43 POL(_*_(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 18.38/8.43 POL(_+_(x_1, x_2)) = 2*x_1 + 3*x_2 18.38/8.43 POL(_+_^1(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 18.38/8.43 POL(d(x_1, x_2)) = 2*x_1 + 3*x_2 18.38/8.43 POL(gcd(x_1, x_2)) = 2 + 3*x_1 + x_2 18.38/8.43 POL(isNat(x_1)) = 2 + x_1 18.38/8.43 POL(isNzNat(x_1)) = x_1 18.38/8.43 POL(p_(x_1)) = 2*x_1 18.38/8.43 POL(quot(x_1, x_2)) = 2 + 2*x_1 + 3*x_2 18.38/8.43 POL(s_(x_1)) = 2 + 2*x_1 18.38/8.43 POL(tt) = 2 18.38/8.43 18.38/8.43 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (23) 18.38/8.43 Obligation: 18.38/8.43 The TRS P consists of the following rules: 18.38/8.43 18.38/8.43 U42^1(tt, M, N) -> _+_^1(N, M) 18.38/8.43 18.38/8.43 The TRS R consists of the following rules: 18.38/8.43 18.38/8.43 U242(tt) -> tt 18.38/8.43 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.43 U202(tt) -> tt 18.38/8.43 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.43 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.43 U251(tt) -> tt 18.38/8.43 U222(tt) -> tt 18.38/8.43 U161(tt) -> tt 18.38/8.43 U172(tt) -> tt 18.38/8.43 U192(tt) -> tt 18.38/8.43 U182(tt) -> tt 18.38/8.43 U211(tt) -> tt 18.38/8.43 18.38/8.43 E is empty. 18.38/8.43 The set E# consists of the following equations: 18.38/8.43 18.38/8.43 _+_^1(x, y) == _+_^1(y, x) 18.38/8.43 18.38/8.43 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (24) EDependencyGraphProof (EQUIVALENT) 18.38/8.43 The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 1 less node. 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (25) 18.38/8.43 TRUE 18.38/8.43 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (26) 18.38/8.43 Obligation: 18.38/8.43 The TRS P consists of the following rules: 18.38/8.43 18.38/8.43 U21^1(tt, M, N) -> U22^1(isNat(N), M, N) 18.38/8.43 U22^1(tt, M, N) -> _*_^1(N, M) 18.38/8.43 _*_^1(s_(N), s_(M)) -> U21^1(isNat(M), M, N) 18.38/8.43 18.38/8.43 The TRS R consists of the following rules: 18.38/8.43 18.38/8.43 1 -> s_(0) 18.38/8.43 2 -> s_(s_(0)) 18.38/8.43 3 -> s_(s_(s_(0))) 18.38/8.43 4 -> s_(s_(s_(s_(0)))) 18.38/8.43 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.43 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.43 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.43 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.43 U102(tt, M, N) -> d(N, M) 18.38/8.43 U11(tt) -> 0 18.38/8.43 U111(tt) -> 0 18.38/8.43 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.43 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.43 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.43 U131(tt, N') -> N' 18.38/8.43 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.43 U142(tt) -> tt 18.38/8.43 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.43 U152(tt) -> tt 18.38/8.43 U161(tt) -> tt 18.38/8.43 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.43 U172(tt) -> tt 18.38/8.43 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.43 U182(tt) -> tt 18.38/8.43 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.43 U192(tt) -> tt 18.38/8.43 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.43 U202(tt) -> tt 18.38/8.43 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.43 U211(tt) -> tt 18.38/8.43 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.43 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.43 U222(tt) -> tt 18.38/8.43 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.43 U232(tt) -> tt 18.38/8.43 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.43 U242(tt) -> tt 18.38/8.43 U251(tt) -> tt 18.38/8.43 U261(tt, N) -> N 18.38/8.43 U271(tt) -> s_(0) 18.38/8.43 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.43 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.43 U283(tt) -> 0 18.38/8.43 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.43 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.43 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.43 U31(tt, N) -> N 18.38/8.43 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.43 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.43 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.43 U52(tt, M, N) -> _>_(M, N) 18.38/8.43 U61(tt) -> false 18.38/8.43 U71(tt) -> true 18.38/8.43 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.43 U82(tt, M, N) -> _>_(N, M) 18.38/8.43 U91(tt, N) -> N 18.38/8.43 _*_(N, 0) -> U11(isNat(N)) 18.38/8.43 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.43 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.43 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.43 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.43 _>_(0, M) -> U61(isNat(M)) 18.38/8.43 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.43 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.43 d(0, N) -> U91(isNat(N), N) 18.38/8.43 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.43 equal(X, X) -> tt 18.38/8.43 gcd(0, N) -> U111(isNat(N)) 18.38/8.43 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.43 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.43 isBoolean(false) -> tt 18.38/8.43 isBoolean(true) -> tt 18.38/8.43 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.43 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.43 isNat(0) -> tt 18.38/8.43 isNat(V) -> U161(isNzNat(V)) 18.38/8.43 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.43 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.43 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.43 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.43 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.43 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.43 isNzNat(1) -> tt 18.38/8.43 isNzNat(2) -> tt 18.38/8.43 isNzNat(3) -> tt 18.38/8.43 isNzNat(4) -> tt 18.38/8.43 isNzNat(5) -> tt 18.38/8.43 isNzNat(6) -> tt 18.38/8.43 isNzNat(7) -> tt 18.38/8.43 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.43 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.43 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.43 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.43 quot(M', M') -> U271(isNzNat(M')) 18.38/8.43 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.43 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.43 18.38/8.43 The set E consists of the following equations: 18.38/8.43 18.38/8.43 _*_(x, y) == _*_(y, x) 18.38/8.43 _+_(x, y) == _+_(y, x) 18.38/8.43 d(x, y) == d(y, x) 18.38/8.43 gcd(x, y) == gcd(y, x) 18.38/8.43 18.38/8.43 The set E# consists of the following equations: 18.38/8.43 18.38/8.43 _*_^1(x, y) == _*_^1(y, x) 18.38/8.43 _+_^1(x, y) == _+_^1(y, x) 18.38/8.43 D(x, y) == D(y, x) 18.38/8.43 GCD(x, y) == GCD(y, x) 18.38/8.43 18.38/8.43 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (27) ESharpUsableEquationsProof (EQUIVALENT) 18.38/8.43 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 18.38/8.43 _+_^1(x, y) == _+_^1(y, x) 18.38/8.43 D(x, y) == D(y, x) 18.38/8.43 GCD(x, y) == GCD(y, x) 18.38/8.43 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (28) 18.38/8.43 Obligation: 18.38/8.43 The TRS P consists of the following rules: 18.38/8.43 18.38/8.43 U21^1(tt, M, N) -> U22^1(isNat(N), M, N) 18.38/8.43 U22^1(tt, M, N) -> _*_^1(N, M) 18.38/8.43 _*_^1(s_(N), s_(M)) -> U21^1(isNat(M), M, N) 18.38/8.43 18.38/8.43 The TRS R consists of the following rules: 18.38/8.43 18.38/8.43 1 -> s_(0) 18.38/8.43 2 -> s_(s_(0)) 18.38/8.43 3 -> s_(s_(s_(0))) 18.38/8.43 4 -> s_(s_(s_(s_(0)))) 18.38/8.43 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.43 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.43 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.43 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.43 U102(tt, M, N) -> d(N, M) 18.38/8.43 U11(tt) -> 0 18.38/8.43 U111(tt) -> 0 18.38/8.43 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.43 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.43 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.43 U131(tt, N') -> N' 18.38/8.43 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.43 U142(tt) -> tt 18.38/8.43 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.43 U152(tt) -> tt 18.38/8.43 U161(tt) -> tt 18.38/8.43 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.43 U172(tt) -> tt 18.38/8.43 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.43 U182(tt) -> tt 18.38/8.43 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.43 U192(tt) -> tt 18.38/8.43 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.43 U202(tt) -> tt 18.38/8.43 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.43 U211(tt) -> tt 18.38/8.43 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.43 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.43 U222(tt) -> tt 18.38/8.43 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.43 U232(tt) -> tt 18.38/8.43 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.43 U242(tt) -> tt 18.38/8.43 U251(tt) -> tt 18.38/8.43 U261(tt, N) -> N 18.38/8.43 U271(tt) -> s_(0) 18.38/8.43 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.43 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.43 U283(tt) -> 0 18.38/8.43 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.43 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.43 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.43 U31(tt, N) -> N 18.38/8.43 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.43 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.43 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.43 U52(tt, M, N) -> _>_(M, N) 18.38/8.43 U61(tt) -> false 18.38/8.43 U71(tt) -> true 18.38/8.43 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.43 U82(tt, M, N) -> _>_(N, M) 18.38/8.43 U91(tt, N) -> N 18.38/8.43 _*_(N, 0) -> U11(isNat(N)) 18.38/8.43 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.43 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.43 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.43 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.43 _>_(0, M) -> U61(isNat(M)) 18.38/8.43 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.43 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.43 d(0, N) -> U91(isNat(N), N) 18.38/8.43 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.43 equal(X, X) -> tt 18.38/8.43 gcd(0, N) -> U111(isNat(N)) 18.38/8.43 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.43 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.43 isBoolean(false) -> tt 18.38/8.43 isBoolean(true) -> tt 18.38/8.43 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.43 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.43 isNat(0) -> tt 18.38/8.43 isNat(V) -> U161(isNzNat(V)) 18.38/8.43 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.43 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.43 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.43 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.43 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.43 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.43 isNzNat(1) -> tt 18.38/8.43 isNzNat(2) -> tt 18.38/8.43 isNzNat(3) -> tt 18.38/8.43 isNzNat(4) -> tt 18.38/8.43 isNzNat(5) -> tt 18.38/8.43 isNzNat(6) -> tt 18.38/8.43 isNzNat(7) -> tt 18.38/8.43 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.43 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.43 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.43 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.43 quot(M', M') -> U271(isNzNat(M')) 18.38/8.43 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.43 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.43 18.38/8.43 The set E consists of the following equations: 18.38/8.43 18.38/8.43 _*_(x, y) == _*_(y, x) 18.38/8.43 _+_(x, y) == _+_(y, x) 18.38/8.43 d(x, y) == d(y, x) 18.38/8.43 gcd(x, y) == gcd(y, x) 18.38/8.43 18.38/8.43 The set E# consists of the following equations: 18.38/8.43 18.38/8.43 _*_^1(x, y) == _*_^1(y, x) 18.38/8.43 18.38/8.43 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (29) EUsableRulesReductionPairsProof (EQUIVALENT) 18.38/8.43 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. 18.38/8.43 18.38/8.43 The following dependency pairs can be deleted: 18.38/8.43 18.38/8.43 U21^1(tt, M, N) -> U22^1(isNat(N), M, N) 18.38/8.43 _*_^1(s_(N), s_(M)) -> U21^1(isNat(M), M, N) 18.38/8.43 The following rules are removed from R: 18.38/8.43 18.38/8.43 1 -> s_(0) 18.38/8.43 2 -> s_(s_(0)) 18.38/8.43 3 -> s_(s_(s_(0))) 18.38/8.43 4 -> s_(s_(s_(s_(0)))) 18.38/8.43 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.43 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.43 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.43 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.43 U102(tt, M, N) -> d(N, M) 18.38/8.43 U11(tt) -> 0 18.38/8.43 U111(tt) -> 0 18.38/8.43 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.43 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.43 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.43 U131(tt, N') -> N' 18.38/8.43 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.43 U142(tt) -> tt 18.38/8.43 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.43 U152(tt) -> tt 18.38/8.43 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.43 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.43 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.43 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.43 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.43 U232(tt) -> tt 18.38/8.43 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.43 U261(tt, N) -> N 18.38/8.43 U271(tt) -> s_(0) 18.38/8.43 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.43 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.43 U283(tt) -> 0 18.38/8.43 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.43 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.43 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.43 U31(tt, N) -> N 18.38/8.43 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.43 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.43 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.43 U52(tt, M, N) -> _>_(M, N) 18.38/8.43 U61(tt) -> false 18.38/8.43 U71(tt) -> true 18.38/8.43 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.43 U82(tt, M, N) -> _>_(N, M) 18.38/8.43 U91(tt, N) -> N 18.38/8.43 _*_(N, 0) -> U11(isNat(N)) 18.38/8.43 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.43 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.43 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.43 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.43 _>_(0, M) -> U61(isNat(M)) 18.38/8.43 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.43 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.43 d(0, N) -> U91(isNat(N), N) 18.38/8.43 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.43 equal(X, X) -> tt 18.38/8.43 gcd(0, N) -> U111(isNat(N)) 18.38/8.43 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.43 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.43 isBoolean(false) -> tt 18.38/8.43 isBoolean(true) -> tt 18.38/8.43 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.43 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.43 isNat(0) -> tt 18.38/8.43 isNat(V) -> U161(isNzNat(V)) 18.38/8.43 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.43 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.43 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.43 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.43 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.43 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.43 isNzNat(1) -> tt 18.38/8.43 isNzNat(2) -> tt 18.38/8.43 isNzNat(3) -> tt 18.38/8.43 isNzNat(4) -> tt 18.38/8.43 isNzNat(5) -> tt 18.38/8.43 isNzNat(6) -> tt 18.38/8.43 isNzNat(7) -> tt 18.38/8.43 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.43 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.43 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.43 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.43 quot(M', M') -> U271(isNzNat(M')) 18.38/8.43 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.43 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.43 The following equations are removed from E: 18.38/8.43 18.38/8.43 _*_(x, y) == _*_(y, x) 18.38/8.43 _+_(x, y) == _+_(y, x) 18.38/8.43 d(x, y) == d(y, x) 18.38/8.43 gcd(x, y) == gcd(y, x) 18.38/8.43 Used ordering: POLO with Polynomial interpretation [POLO]: 18.38/8.43 18.38/8.43 POL(0) = 0 18.38/8.43 POL(1) = 2 18.38/8.43 POL(2) = 2 18.38/8.43 POL(3) = 2 18.38/8.43 POL(4) = 2 18.38/8.43 POL(5) = 2 18.38/8.43 POL(6) = 2 18.38/8.43 POL(7) = 2 18.38/8.43 POL(U161(x_1)) = x_1 18.38/8.43 POL(U171(x_1, x_2)) = x_1 + 2*x_2 18.38/8.43 POL(U172(x_1)) = x_1 18.38/8.43 POL(U181(x_1, x_2)) = x_1 + 3*x_2 18.38/8.43 POL(U182(x_1)) = x_1 18.38/8.43 POL(U191(x_1, x_2)) = x_1 + 2*x_2 18.38/8.43 POL(U192(x_1)) = x_1 18.38/8.43 POL(U201(x_1, x_2)) = 1 + x_1 + x_2 18.38/8.43 POL(U202(x_1)) = x_1 18.38/8.43 POL(U211(x_1)) = x_1 18.38/8.43 POL(U21^1(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 3*x_3 18.38/8.43 POL(U221(x_1, x_2)) = x_1 + 3*x_2 18.38/8.43 POL(U222(x_1)) = x_1 18.38/8.43 POL(U22^1(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 18.38/8.43 POL(U231(x_1, x_2)) = 2 + x_1 + 2*x_2 18.38/8.43 POL(U232(x_1)) = 2*x_1 18.38/8.43 POL(U241(x_1, x_2)) = 2*x_1 + x_2 18.38/8.43 POL(U242(x_1)) = x_1 18.38/8.43 POL(U251(x_1)) = x_1 18.38/8.43 POL(_*_(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 18.38/8.43 POL(_*_^1(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 18.38/8.43 POL(_+_(x_1, x_2)) = 2*x_1 + 3*x_2 18.38/8.43 POL(d(x_1, x_2)) = 2*x_1 + 3*x_2 18.38/8.43 POL(gcd(x_1, x_2)) = 2 + 3*x_1 + x_2 18.38/8.43 POL(isNat(x_1)) = 2 + x_1 18.38/8.43 POL(isNzNat(x_1)) = x_1 18.38/8.43 POL(p_(x_1)) = 2*x_1 18.38/8.43 POL(quot(x_1, x_2)) = 2 + 2*x_1 + 3*x_2 18.38/8.43 POL(s_(x_1)) = 2 + 2*x_1 18.38/8.43 POL(tt) = 2 18.38/8.43 18.38/8.43 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (30) 18.38/8.43 Obligation: 18.38/8.43 The TRS P consists of the following rules: 18.38/8.43 18.38/8.43 U22^1(tt, M, N) -> _*_^1(N, M) 18.38/8.43 18.38/8.43 The TRS R consists of the following rules: 18.38/8.43 18.38/8.43 U242(tt) -> tt 18.38/8.43 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.43 U202(tt) -> tt 18.38/8.43 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.43 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.43 U251(tt) -> tt 18.38/8.43 U222(tt) -> tt 18.38/8.43 U161(tt) -> tt 18.38/8.43 U172(tt) -> tt 18.38/8.43 U192(tt) -> tt 18.38/8.43 U182(tt) -> tt 18.38/8.43 U211(tt) -> tt 18.38/8.43 18.38/8.43 E is empty. 18.38/8.43 The set E# consists of the following equations: 18.38/8.43 18.38/8.43 _*_^1(x, y) == _*_^1(y, x) 18.38/8.43 18.38/8.43 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (31) EDependencyGraphProof (EQUIVALENT) 18.38/8.43 The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 1 less node. 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (32) 18.38/8.43 TRUE 18.38/8.43 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (33) 18.38/8.43 Obligation: 18.38/8.43 The TRS P consists of the following rules: 18.38/8.43 18.38/8.43 U101^1(tt, M, N) -> U102^1(isNat(N), M, N) 18.38/8.43 U102^1(tt, M, N) -> D(N, M) 18.38/8.43 D(s_(N), s_(M)) -> U101^1(isNat(M), M, N) 18.38/8.43 18.38/8.43 The TRS R consists of the following rules: 18.38/8.43 18.38/8.43 1 -> s_(0) 18.38/8.43 2 -> s_(s_(0)) 18.38/8.43 3 -> s_(s_(s_(0))) 18.38/8.43 4 -> s_(s_(s_(s_(0)))) 18.38/8.43 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.43 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.43 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.43 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.43 U102(tt, M, N) -> d(N, M) 18.38/8.43 U11(tt) -> 0 18.38/8.43 U111(tt) -> 0 18.38/8.43 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.43 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.43 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.43 U131(tt, N') -> N' 18.38/8.43 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.43 U142(tt) -> tt 18.38/8.43 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.43 U152(tt) -> tt 18.38/8.43 U161(tt) -> tt 18.38/8.43 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.43 U172(tt) -> tt 18.38/8.43 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.43 U182(tt) -> tt 18.38/8.43 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.43 U192(tt) -> tt 18.38/8.43 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.43 U202(tt) -> tt 18.38/8.43 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.43 U211(tt) -> tt 18.38/8.43 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.43 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.43 U222(tt) -> tt 18.38/8.43 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.43 U232(tt) -> tt 18.38/8.43 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.43 U242(tt) -> tt 18.38/8.43 U251(tt) -> tt 18.38/8.43 U261(tt, N) -> N 18.38/8.43 U271(tt) -> s_(0) 18.38/8.43 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.43 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.43 U283(tt) -> 0 18.38/8.43 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.43 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.43 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.43 U31(tt, N) -> N 18.38/8.43 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.43 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.43 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.43 U52(tt, M, N) -> _>_(M, N) 18.38/8.43 U61(tt) -> false 18.38/8.43 U71(tt) -> true 18.38/8.43 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.43 U82(tt, M, N) -> _>_(N, M) 18.38/8.43 U91(tt, N) -> N 18.38/8.43 _*_(N, 0) -> U11(isNat(N)) 18.38/8.43 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.43 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.43 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.43 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.43 _>_(0, M) -> U61(isNat(M)) 18.38/8.43 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.43 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.43 d(0, N) -> U91(isNat(N), N) 18.38/8.43 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.43 equal(X, X) -> tt 18.38/8.43 gcd(0, N) -> U111(isNat(N)) 18.38/8.43 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.43 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.43 isBoolean(false) -> tt 18.38/8.43 isBoolean(true) -> tt 18.38/8.43 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.43 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.43 isNat(0) -> tt 18.38/8.43 isNat(V) -> U161(isNzNat(V)) 18.38/8.43 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.43 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.43 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.43 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.43 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.43 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.43 isNzNat(1) -> tt 18.38/8.43 isNzNat(2) -> tt 18.38/8.43 isNzNat(3) -> tt 18.38/8.43 isNzNat(4) -> tt 18.38/8.43 isNzNat(5) -> tt 18.38/8.43 isNzNat(6) -> tt 18.38/8.43 isNzNat(7) -> tt 18.38/8.43 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.43 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.43 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.43 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.43 quot(M', M') -> U271(isNzNat(M')) 18.38/8.43 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.43 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.43 18.38/8.43 The set E consists of the following equations: 18.38/8.43 18.38/8.43 _*_(x, y) == _*_(y, x) 18.38/8.43 _+_(x, y) == _+_(y, x) 18.38/8.43 d(x, y) == d(y, x) 18.38/8.43 gcd(x, y) == gcd(y, x) 18.38/8.43 18.38/8.43 The set E# consists of the following equations: 18.38/8.43 18.38/8.43 _*_^1(x, y) == _*_^1(y, x) 18.38/8.43 _+_^1(x, y) == _+_^1(y, x) 18.38/8.43 D(x, y) == D(y, x) 18.38/8.43 GCD(x, y) == GCD(y, x) 18.38/8.43 18.38/8.43 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (34) ESharpUsableEquationsProof (EQUIVALENT) 18.38/8.43 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 18.38/8.43 _*_^1(x, y) == _*_^1(y, x) 18.38/8.43 _+_^1(x, y) == _+_^1(y, x) 18.38/8.43 GCD(x, y) == GCD(y, x) 18.38/8.43 18.38/8.43 ---------------------------------------- 18.38/8.43 18.38/8.43 (35) 18.38/8.43 Obligation: 18.38/8.43 The TRS P consists of the following rules: 18.38/8.43 18.38/8.43 U101^1(tt, M, N) -> U102^1(isNat(N), M, N) 18.38/8.43 U102^1(tt, M, N) -> D(N, M) 18.38/8.43 D(s_(N), s_(M)) -> U101^1(isNat(M), M, N) 18.38/8.43 18.38/8.43 The TRS R consists of the following rules: 18.38/8.43 18.38/8.43 1 -> s_(0) 18.38/8.43 2 -> s_(s_(0)) 18.38/8.43 3 -> s_(s_(s_(0))) 18.38/8.43 4 -> s_(s_(s_(s_(0)))) 18.38/8.43 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.43 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.43 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.43 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.43 U102(tt, M, N) -> d(N, M) 18.38/8.43 U11(tt) -> 0 18.38/8.43 U111(tt) -> 0 18.38/8.43 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.43 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.43 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.43 U131(tt, N') -> N' 18.38/8.43 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.43 U142(tt) -> tt 18.38/8.43 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.43 U152(tt) -> tt 18.38/8.43 U161(tt) -> tt 18.38/8.43 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.43 U172(tt) -> tt 18.38/8.43 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.43 U182(tt) -> tt 18.38/8.43 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.43 U192(tt) -> tt 18.38/8.43 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.43 U202(tt) -> tt 18.38/8.43 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.43 U211(tt) -> tt 18.38/8.43 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.43 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.43 U222(tt) -> tt 18.38/8.43 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.43 U232(tt) -> tt 18.38/8.43 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.43 U242(tt) -> tt 18.38/8.43 U251(tt) -> tt 18.38/8.43 U261(tt, N) -> N 18.38/8.43 U271(tt) -> s_(0) 18.38/8.43 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.43 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.43 U283(tt) -> 0 18.38/8.43 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.43 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.43 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.43 U31(tt, N) -> N 18.38/8.43 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.43 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.43 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.43 U52(tt, M, N) -> _>_(M, N) 18.38/8.43 U61(tt) -> false 18.38/8.43 U71(tt) -> true 18.38/8.43 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.43 U82(tt, M, N) -> _>_(N, M) 18.38/8.43 U91(tt, N) -> N 18.38/8.43 _*_(N, 0) -> U11(isNat(N)) 18.38/8.43 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.43 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.43 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.43 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.44 _>_(0, M) -> U61(isNat(M)) 18.38/8.44 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.44 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.44 d(0, N) -> U91(isNat(N), N) 18.38/8.44 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.44 equal(X, X) -> tt 18.38/8.44 gcd(0, N) -> U111(isNat(N)) 18.38/8.44 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.44 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.44 isBoolean(false) -> tt 18.38/8.44 isBoolean(true) -> tt 18.38/8.44 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.44 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.44 isNat(0) -> tt 18.38/8.44 isNat(V) -> U161(isNzNat(V)) 18.38/8.44 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.44 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.44 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.44 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.44 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.44 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.44 isNzNat(1) -> tt 18.38/8.44 isNzNat(2) -> tt 18.38/8.44 isNzNat(3) -> tt 18.38/8.44 isNzNat(4) -> tt 18.38/8.44 isNzNat(5) -> tt 18.38/8.44 isNzNat(6) -> tt 18.38/8.44 isNzNat(7) -> tt 18.38/8.44 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.44 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.44 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.44 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.44 quot(M', M') -> U271(isNzNat(M')) 18.38/8.44 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.44 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.44 18.38/8.44 The set E consists of the following equations: 18.38/8.44 18.38/8.44 _*_(x, y) == _*_(y, x) 18.38/8.44 _+_(x, y) == _+_(y, x) 18.38/8.44 d(x, y) == d(y, x) 18.38/8.44 gcd(x, y) == gcd(y, x) 18.38/8.44 18.38/8.44 The set E# consists of the following equations: 18.38/8.44 18.38/8.44 D(x, y) == D(y, x) 18.38/8.44 18.38/8.44 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.44 ---------------------------------------- 18.38/8.44 18.38/8.44 (36) EUsableRulesReductionPairsProof (EQUIVALENT) 18.38/8.44 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. 18.38/8.44 18.38/8.44 The following dependency pairs can be deleted: 18.38/8.44 18.38/8.44 U101^1(tt, M, N) -> U102^1(isNat(N), M, N) 18.38/8.44 D(s_(N), s_(M)) -> U101^1(isNat(M), M, N) 18.38/8.44 The following rules are removed from R: 18.38/8.44 18.38/8.44 1 -> s_(0) 18.38/8.44 2 -> s_(s_(0)) 18.38/8.44 3 -> s_(s_(s_(0))) 18.38/8.44 4 -> s_(s_(s_(s_(0)))) 18.38/8.44 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.44 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.44 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.44 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.44 U102(tt, M, N) -> d(N, M) 18.38/8.44 U11(tt) -> 0 18.38/8.44 U111(tt) -> 0 18.38/8.44 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.44 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.44 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.44 U131(tt, N') -> N' 18.38/8.44 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.44 U142(tt) -> tt 18.38/8.44 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.44 U152(tt) -> tt 18.38/8.44 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.44 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.44 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.44 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.44 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.44 U232(tt) -> tt 18.38/8.44 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.44 U261(tt, N) -> N 18.38/8.44 U271(tt) -> s_(0) 18.38/8.44 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.44 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.44 U283(tt) -> 0 18.38/8.44 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.44 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.44 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.44 U31(tt, N) -> N 18.38/8.44 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.44 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.44 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.44 U52(tt, M, N) -> _>_(M, N) 18.38/8.44 U61(tt) -> false 18.38/8.44 U71(tt) -> true 18.38/8.44 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.44 U82(tt, M, N) -> _>_(N, M) 18.38/8.44 U91(tt, N) -> N 18.38/8.44 _*_(N, 0) -> U11(isNat(N)) 18.38/8.44 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.44 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.44 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.44 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.44 _>_(0, M) -> U61(isNat(M)) 18.38/8.44 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.44 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.44 d(0, N) -> U91(isNat(N), N) 18.38/8.44 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.44 equal(X, X) -> tt 18.38/8.44 gcd(0, N) -> U111(isNat(N)) 18.38/8.44 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.44 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.44 isBoolean(false) -> tt 18.38/8.44 isBoolean(true) -> tt 18.38/8.44 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.44 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.44 isNat(0) -> tt 18.38/8.44 isNat(V) -> U161(isNzNat(V)) 18.38/8.44 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.44 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.44 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.44 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.44 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.44 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.44 isNzNat(1) -> tt 18.38/8.44 isNzNat(2) -> tt 18.38/8.44 isNzNat(3) -> tt 18.38/8.44 isNzNat(4) -> tt 18.38/8.44 isNzNat(5) -> tt 18.38/8.44 isNzNat(6) -> tt 18.38/8.44 isNzNat(7) -> tt 18.38/8.44 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.44 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.44 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.44 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.44 quot(M', M') -> U271(isNzNat(M')) 18.38/8.44 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.44 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.44 The following equations are removed from E: 18.38/8.44 18.38/8.44 _*_(x, y) == _*_(y, x) 18.38/8.44 _+_(x, y) == _+_(y, x) 18.38/8.44 d(x, y) == d(y, x) 18.38/8.44 gcd(x, y) == gcd(y, x) 18.38/8.44 Used ordering: POLO with Polynomial interpretation [POLO]: 18.38/8.44 18.38/8.44 POL(0) = 0 18.38/8.44 POL(1) = 2 18.38/8.44 POL(2) = 2 18.38/8.44 POL(3) = 2 18.38/8.44 POL(4) = 2 18.38/8.44 POL(5) = 2 18.38/8.44 POL(6) = 2 18.38/8.44 POL(7) = 2 18.38/8.44 POL(D(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 18.38/8.44 POL(U101^1(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 3*x_3 18.38/8.44 POL(U102^1(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 18.38/8.44 POL(U161(x_1)) = x_1 18.38/8.44 POL(U171(x_1, x_2)) = x_1 + 2*x_2 18.38/8.44 POL(U172(x_1)) = x_1 18.38/8.44 POL(U181(x_1, x_2)) = x_1 + 3*x_2 18.38/8.44 POL(U182(x_1)) = x_1 18.38/8.44 POL(U191(x_1, x_2)) = x_1 + 2*x_2 18.38/8.44 POL(U192(x_1)) = x_1 18.38/8.44 POL(U201(x_1, x_2)) = 1 + x_1 + x_2 18.38/8.44 POL(U202(x_1)) = x_1 18.38/8.44 POL(U211(x_1)) = x_1 18.38/8.44 POL(U221(x_1, x_2)) = x_1 + 3*x_2 18.38/8.44 POL(U222(x_1)) = x_1 18.38/8.44 POL(U231(x_1, x_2)) = 2 + x_1 + 2*x_2 18.38/8.44 POL(U232(x_1)) = 2*x_1 18.38/8.44 POL(U241(x_1, x_2)) = 2*x_1 + x_2 18.38/8.44 POL(U242(x_1)) = x_1 18.38/8.44 POL(U251(x_1)) = x_1 18.38/8.44 POL(_*_(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 18.38/8.44 POL(_+_(x_1, x_2)) = 2*x_1 + 3*x_2 18.38/8.44 POL(d(x_1, x_2)) = 2*x_1 + 3*x_2 18.38/8.44 POL(gcd(x_1, x_2)) = 2 + 3*x_1 + x_2 18.38/8.44 POL(isNat(x_1)) = 2 + x_1 18.38/8.44 POL(isNzNat(x_1)) = x_1 18.38/8.44 POL(p_(x_1)) = 2*x_1 18.38/8.44 POL(quot(x_1, x_2)) = 2 + 2*x_1 + 3*x_2 18.38/8.44 POL(s_(x_1)) = 2 + 2*x_1 18.38/8.44 POL(tt) = 2 18.38/8.44 18.38/8.44 18.38/8.44 ---------------------------------------- 18.38/8.44 18.38/8.44 (37) 18.38/8.44 Obligation: 18.38/8.44 The TRS P consists of the following rules: 18.38/8.44 18.38/8.44 U102^1(tt, M, N) -> D(N, M) 18.38/8.44 18.38/8.44 The TRS R consists of the following rules: 18.38/8.44 18.38/8.44 U242(tt) -> tt 18.38/8.44 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.44 U202(tt) -> tt 18.38/8.44 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.44 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.44 U251(tt) -> tt 18.38/8.44 U222(tt) -> tt 18.38/8.44 U161(tt) -> tt 18.38/8.44 U172(tt) -> tt 18.38/8.44 U192(tt) -> tt 18.38/8.44 U182(tt) -> tt 18.38/8.44 U211(tt) -> tt 18.38/8.44 18.38/8.44 E is empty. 18.38/8.44 The set E# consists of the following equations: 18.38/8.44 18.38/8.44 D(x, y) == D(y, x) 18.38/8.44 18.38/8.44 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.44 ---------------------------------------- 18.38/8.44 18.38/8.44 (38) EDependencyGraphProof (EQUIVALENT) 18.38/8.44 The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 1 less node. 18.38/8.44 ---------------------------------------- 18.38/8.44 18.38/8.44 (39) 18.38/8.44 TRUE 18.38/8.44 18.38/8.44 ---------------------------------------- 18.38/8.44 18.38/8.44 (40) 18.38/8.44 Obligation: 18.38/8.44 The TRS P consists of the following rules: 18.38/8.44 18.38/8.44 U293^1(tt, M', N) -> QUOT(d(N, M'), M') 18.38/8.44 U291^1(tt, M', N) -> U292^1(isNat(N), M', N) 18.38/8.44 QUOT(N, M') -> U291^1(isNzNat(M'), M', N) 18.38/8.44 U292^1(tt, M', N) -> U293^1(equal(_>_(N, M'), true), M', N) 18.38/8.44 18.38/8.44 The TRS R consists of the following rules: 18.38/8.44 18.38/8.44 1 -> s_(0) 18.38/8.44 2 -> s_(s_(0)) 18.38/8.44 3 -> s_(s_(s_(0))) 18.38/8.44 4 -> s_(s_(s_(s_(0)))) 18.38/8.44 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.44 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.44 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.44 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.44 U102(tt, M, N) -> d(N, M) 18.38/8.44 U11(tt) -> 0 18.38/8.44 U111(tt) -> 0 18.38/8.44 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.44 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.44 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.44 U131(tt, N') -> N' 18.38/8.44 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.44 U142(tt) -> tt 18.38/8.44 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.44 U152(tt) -> tt 18.38/8.44 U161(tt) -> tt 18.38/8.44 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.44 U172(tt) -> tt 18.38/8.44 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.44 U182(tt) -> tt 18.38/8.44 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.44 U192(tt) -> tt 18.38/8.44 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.44 U202(tt) -> tt 18.38/8.44 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.44 U211(tt) -> tt 18.38/8.44 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.44 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.44 U222(tt) -> tt 18.38/8.44 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.44 U232(tt) -> tt 18.38/8.44 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.44 U242(tt) -> tt 18.38/8.44 U251(tt) -> tt 18.38/8.44 U261(tt, N) -> N 18.38/8.44 U271(tt) -> s_(0) 18.38/8.44 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.44 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.44 U283(tt) -> 0 18.38/8.44 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.44 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.44 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.44 U31(tt, N) -> N 18.38/8.44 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.44 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.44 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.44 U52(tt, M, N) -> _>_(M, N) 18.38/8.44 U61(tt) -> false 18.38/8.44 U71(tt) -> true 18.38/8.44 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.44 U82(tt, M, N) -> _>_(N, M) 18.38/8.44 U91(tt, N) -> N 18.38/8.44 _*_(N, 0) -> U11(isNat(N)) 18.38/8.44 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.44 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.44 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.44 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.44 _>_(0, M) -> U61(isNat(M)) 18.38/8.44 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.44 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.44 d(0, N) -> U91(isNat(N), N) 18.38/8.44 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.44 equal(X, X) -> tt 18.38/8.44 gcd(0, N) -> U111(isNat(N)) 18.38/8.44 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.44 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.44 isBoolean(false) -> tt 18.38/8.44 isBoolean(true) -> tt 18.38/8.44 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.44 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.44 isNat(0) -> tt 18.38/8.44 isNat(V) -> U161(isNzNat(V)) 18.38/8.44 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.44 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.44 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.44 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.44 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.44 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.44 isNzNat(1) -> tt 18.38/8.44 isNzNat(2) -> tt 18.38/8.44 isNzNat(3) -> tt 18.38/8.44 isNzNat(4) -> tt 18.38/8.44 isNzNat(5) -> tt 18.38/8.44 isNzNat(6) -> tt 18.38/8.44 isNzNat(7) -> tt 18.38/8.44 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.44 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.44 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.44 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.44 quot(M', M') -> U271(isNzNat(M')) 18.38/8.44 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.44 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.44 18.38/8.44 The set E consists of the following equations: 18.38/8.44 18.38/8.44 _*_(x, y) == _*_(y, x) 18.38/8.44 _+_(x, y) == _+_(y, x) 18.38/8.44 d(x, y) == d(y, x) 18.38/8.44 gcd(x, y) == gcd(y, x) 18.38/8.44 18.38/8.44 The set E# consists of the following equations: 18.38/8.44 18.38/8.44 _*_^1(x, y) == _*_^1(y, x) 18.38/8.44 _+_^1(x, y) == _+_^1(y, x) 18.38/8.44 D(x, y) == D(y, x) 18.38/8.44 GCD(x, y) == GCD(y, x) 18.38/8.44 18.38/8.44 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.44 ---------------------------------------- 18.38/8.44 18.38/8.44 (41) ESharpUsableEquationsProof (EQUIVALENT) 18.38/8.44 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 18.38/8.44 _*_^1(x, y) == _*_^1(y, x) 18.38/8.44 _+_^1(x, y) == _+_^1(y, x) 18.38/8.44 D(x, y) == D(y, x) 18.38/8.44 GCD(x, y) == GCD(y, x) 18.38/8.44 18.38/8.44 ---------------------------------------- 18.38/8.44 18.38/8.44 (42) 18.38/8.44 Obligation: 18.38/8.44 The TRS P consists of the following rules: 18.38/8.44 18.38/8.44 U293^1(tt, M', N) -> QUOT(d(N, M'), M') 18.38/8.44 U291^1(tt, M', N) -> U292^1(isNat(N), M', N) 18.38/8.44 QUOT(N, M') -> U291^1(isNzNat(M'), M', N) 18.38/8.44 U292^1(tt, M', N) -> U293^1(equal(_>_(N, M'), true), M', N) 18.38/8.44 18.38/8.44 The TRS R consists of the following rules: 18.38/8.44 18.38/8.44 1 -> s_(0) 18.38/8.44 2 -> s_(s_(0)) 18.38/8.44 3 -> s_(s_(s_(0))) 18.38/8.44 4 -> s_(s_(s_(s_(0)))) 18.38/8.44 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.44 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.44 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.44 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.44 U102(tt, M, N) -> d(N, M) 18.38/8.44 U11(tt) -> 0 18.38/8.44 U111(tt) -> 0 18.38/8.44 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.44 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.44 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.44 U131(tt, N') -> N' 18.38/8.44 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.44 U142(tt) -> tt 18.38/8.44 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.44 U152(tt) -> tt 18.38/8.44 U161(tt) -> tt 18.38/8.44 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.44 U172(tt) -> tt 18.38/8.44 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.44 U182(tt) -> tt 18.38/8.44 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.44 U192(tt) -> tt 18.38/8.44 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.44 U202(tt) -> tt 18.38/8.44 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.44 U211(tt) -> tt 18.38/8.44 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.44 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.44 U222(tt) -> tt 18.38/8.44 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.44 U232(tt) -> tt 18.38/8.44 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.44 U242(tt) -> tt 18.38/8.44 U251(tt) -> tt 18.38/8.44 U261(tt, N) -> N 18.38/8.44 U271(tt) -> s_(0) 18.38/8.44 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.44 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.44 U283(tt) -> 0 18.38/8.44 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.44 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.44 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.44 U31(tt, N) -> N 18.38/8.44 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.44 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.44 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.44 U52(tt, M, N) -> _>_(M, N) 18.38/8.44 U61(tt) -> false 18.38/8.44 U71(tt) -> true 18.38/8.44 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.44 U82(tt, M, N) -> _>_(N, M) 18.38/8.44 U91(tt, N) -> N 18.38/8.44 _*_(N, 0) -> U11(isNat(N)) 18.38/8.44 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.44 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.44 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.44 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.44 _>_(0, M) -> U61(isNat(M)) 18.38/8.44 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.44 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.44 d(0, N) -> U91(isNat(N), N) 18.38/8.44 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.44 equal(X, X) -> tt 18.38/8.44 gcd(0, N) -> U111(isNat(N)) 18.38/8.44 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.44 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.44 isBoolean(false) -> tt 18.38/8.44 isBoolean(true) -> tt 18.38/8.44 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.44 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.44 isNat(0) -> tt 18.38/8.44 isNat(V) -> U161(isNzNat(V)) 18.38/8.44 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.44 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.44 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.44 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.44 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.44 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.44 isNzNat(1) -> tt 18.38/8.44 isNzNat(2) -> tt 18.38/8.44 isNzNat(3) -> tt 18.38/8.44 isNzNat(4) -> tt 18.38/8.44 isNzNat(5) -> tt 18.38/8.44 isNzNat(6) -> tt 18.38/8.44 isNzNat(7) -> tt 18.38/8.44 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.44 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.44 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.44 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.44 quot(M', M') -> U271(isNzNat(M')) 18.38/8.44 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.44 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.44 18.38/8.44 The set E consists of the following equations: 18.38/8.44 18.38/8.44 _*_(x, y) == _*_(y, x) 18.38/8.44 _+_(x, y) == _+_(y, x) 18.38/8.44 d(x, y) == d(y, x) 18.38/8.44 gcd(x, y) == gcd(y, x) 18.38/8.44 18.38/8.44 E# is empty. 18.38/8.44 We have to consider all minimal (P,E#,R,E)-chains 18.38/8.44 ---------------------------------------- 18.38/8.44 18.38/8.44 (43) EUsableRulesProof (EQUIVALENT) 18.38/8.44 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: 18.38/8.44 c(x, y) -> x 18.38/8.44 c(x, y) -> y 18.38/8.44 18.38/8.44 ---------------------------------------- 18.38/8.44 18.38/8.44 (44) 18.38/8.44 Obligation: 18.38/8.44 The TRS P consists of the following rules: 18.38/8.44 18.38/8.44 U293^1(tt, M', N) -> QUOT(d(N, M'), M') 18.38/8.44 U291^1(tt, M', N) -> U292^1(isNat(N), M', N) 18.38/8.44 QUOT(N, M') -> U291^1(isNzNat(M'), M', N) 18.38/8.44 U292^1(tt, M', N) -> U293^1(equal(_>_(N, M'), true), M', N) 18.38/8.44 18.38/8.44 The TRS R consists of the following rules: 18.38/8.44 18.38/8.44 isNzNat(6) -> tt 18.38/8.44 isNzNat(3) -> tt 18.38/8.44 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.44 U242(tt) -> tt 18.38/8.44 isNat(0) -> tt 18.38/8.44 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.44 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.44 U202(tt) -> tt 18.38/8.44 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.44 U82(tt, M, N) -> _>_(N, M) 18.38/8.44 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.44 equal(X, X) -> tt 18.38/8.44 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.44 U61(tt) -> false 18.38/8.44 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.44 U102(tt, M, N) -> d(N, M) 18.38/8.44 U251(tt) -> tt 18.38/8.44 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.44 U91(tt, N) -> N 18.38/8.44 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.44 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.44 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.44 U222(tt) -> tt 18.38/8.44 _>_(0, M) -> U61(isNat(M)) 18.38/8.44 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.44 U161(tt) -> tt 18.38/8.44 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.44 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.44 isNat(V) -> U161(isNzNat(V)) 18.38/8.44 U172(tt) -> tt 18.38/8.44 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.44 U232(tt) -> tt 18.38/8.44 d(0, N) -> U91(isNat(N), N) 18.38/8.44 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.44 U192(tt) -> tt 18.38/8.44 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.44 isNzNat(7) -> tt 18.38/8.44 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.44 isNzNat(1) -> tt 18.38/8.44 isNzNat(4) -> tt 18.38/8.44 isNzNat(5) -> tt 18.38/8.44 U182(tt) -> tt 18.38/8.44 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.44 isNzNat(2) -> tt 18.38/8.44 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.44 U71(tt) -> true 18.38/8.44 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.44 U211(tt) -> tt 18.38/8.44 c(x, y) -> x 18.38/8.44 c(x, y) -> y 18.38/8.44 18.38/8.44 The set E consists of the following equations: 18.38/8.44 18.38/8.44 d(x, y) == d(y, x) 18.38/8.44 18.38/8.44 E# is empty. 18.38/8.44 We have to consider all (P,E#,R,E)-chains 18.38/8.44 ---------------------------------------- 18.38/8.44 18.38/8.44 (45) 18.38/8.44 Obligation: 18.38/8.44 The TRS P consists of the following rules: 18.38/8.44 18.38/8.44 U122^1(tt, M', N') -> U123^1(equal(_>_(N', M'), true), M', N') 18.38/8.44 U121^1(tt, M', N') -> U122^1(isNzNat(N'), M', N') 18.38/8.44 GCD(N', M') -> U121^1(isNzNat(M'), M', N') 18.38/8.44 U123^1(tt, M', N') -> GCD(d(N', M'), M') 18.38/8.44 18.38/8.44 The TRS R consists of the following rules: 18.38/8.44 18.38/8.44 1 -> s_(0) 18.38/8.44 2 -> s_(s_(0)) 18.38/8.44 3 -> s_(s_(s_(0))) 18.38/8.44 4 -> s_(s_(s_(s_(0)))) 18.38/8.44 5 -> s_(s_(s_(s_(s_(0))))) 18.38/8.44 6 -> s_(s_(s_(s_(s_(s_(0)))))) 18.38/8.44 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 18.38/8.44 U101(tt, M, N) -> U102(isNat(N), M, N) 18.38/8.44 U102(tt, M, N) -> d(N, M) 18.38/8.44 U11(tt) -> 0 18.38/8.44 U111(tt) -> 0 18.38/8.44 U121(tt, M', N') -> U122(isNzNat(N'), M', N') 18.38/8.44 U122(tt, M', N') -> U123(equal(_>_(N', M'), true), M', N') 18.38/8.44 U123(tt, M', N') -> gcd(d(N', M'), M') 18.38/8.44 U131(tt, N') -> N' 18.38/8.44 U141(tt, V2) -> U142(isNat(V2)) 18.38/8.44 U142(tt) -> tt 18.38/8.44 U151(tt, V2) -> U152(isNat(V2)) 18.38/8.44 U152(tt) -> tt 18.38/8.44 U161(tt) -> tt 18.38/8.44 U171(tt, V2) -> U172(isNat(V2)) 18.38/8.44 U172(tt) -> tt 18.38/8.44 U181(tt, V2) -> U182(isNat(V2)) 18.38/8.44 U182(tt) -> tt 18.38/8.44 U191(tt, V2) -> U192(isNat(V2)) 18.38/8.44 U192(tt) -> tt 18.38/8.44 U201(tt, V2) -> U202(isNat(V2)) 18.38/8.44 U202(tt) -> tt 18.38/8.44 U21(tt, M, N) -> U22(isNat(N), M, N) 18.38/8.44 U211(tt) -> tt 18.38/8.44 U22(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 18.38/8.44 U221(tt, V2) -> U222(isNzNat(V2)) 18.38/8.44 U222(tt) -> tt 18.38/8.44 U231(tt, V2) -> U232(isNzNat(V2)) 18.38/8.44 U232(tt) -> tt 18.38/8.44 U241(tt, V2) -> U242(isNzNat(V2)) 18.38/8.44 U242(tt) -> tt 18.38/8.44 U251(tt) -> tt 18.38/8.44 U261(tt, N) -> N 18.38/8.44 U271(tt) -> s_(0) 18.38/8.44 U281(tt, M', N) -> U282(isNat(N), M', N) 18.38/8.44 U282(tt, M', N) -> U283(equal(_>_(M', N), true)) 18.38/8.44 U283(tt) -> 0 18.38/8.44 U291(tt, M', N) -> U292(isNat(N), M', N) 18.38/8.44 U292(tt, M', N) -> U293(equal(_>_(N, M'), true), M', N) 18.38/8.44 U293(tt, M', N) -> s_(quot(d(N, M'), M')) 18.38/8.44 U31(tt, N) -> N 18.38/8.44 U41(tt, M, N) -> U42(isNat(N), M, N) 18.38/8.44 U42(tt, M, N) -> s_(s_(_+_(N, M))) 18.38/8.44 U51(tt, M, N) -> U52(isNat(N), M, N) 18.38/8.44 U52(tt, M, N) -> _>_(M, N) 18.38/8.44 U61(tt) -> false 18.38/8.44 U71(tt) -> true 18.38/8.44 U81(tt, M, N) -> U82(isNat(N), M, N) 18.38/8.44 U82(tt, M, N) -> _>_(N, M) 18.38/8.44 U91(tt, N) -> N 18.38/8.44 _*_(N, 0) -> U11(isNat(N)) 18.38/8.44 _*_(s_(N), s_(M)) -> U21(isNat(M), M, N) 18.38/8.44 _+_(N, 0) -> U31(isNat(N), N) 18.38/8.44 _+_(s_(N), s_(M)) -> U41(isNat(M), M, N) 18.38/8.44 _<_(N, M) -> U51(isNat(M), M, N) 18.38/8.44 _>_(0, M) -> U61(isNat(M)) 18.38/8.44 _>_(N', 0) -> U71(isNzNat(N')) 18.38/8.44 _>_(s_(N), s_(M)) -> U81(isNat(M), M, N) 18.38/8.44 d(0, N) -> U91(isNat(N), N) 18.38/8.44 d(s_(N), s_(M)) -> U101(isNat(M), M, N) 18.38/8.44 equal(X, X) -> tt 18.38/8.44 gcd(0, N) -> U111(isNat(N)) 18.38/8.44 gcd(N', M') -> U121(isNzNat(M'), M', N') 18.38/8.44 gcd(N', N') -> U131(isNzNat(N'), N') 18.38/8.44 isBoolean(false) -> tt 18.38/8.44 isBoolean(true) -> tt 18.38/8.44 isBoolean(_<_(V1, V2)) -> U141(isNat(V1), V2) 18.38/8.44 isBoolean(_>_(V1, V2)) -> U151(isNat(V1), V2) 18.38/8.44 isNat(0) -> tt 18.38/8.44 isNat(V) -> U161(isNzNat(V)) 18.38/8.44 isNat(_*_(V1, V2)) -> U171(isNat(V1), V2) 18.38/8.44 isNat(_+_(V1, V2)) -> U181(isNat(V1), V2) 18.38/8.44 isNat(d(V1, V2)) -> U191(isNat(V1), V2) 18.38/8.44 isNat(gcd(V1, V2)) -> U201(isNat(V1), V2) 18.38/8.44 isNat(p_(V1)) -> U211(isNzNat(V1)) 18.38/8.44 isNat(quot(V1, V2)) -> U221(isNat(V1), V2) 18.38/8.44 isNzNat(1) -> tt 18.38/8.44 isNzNat(2) -> tt 18.38/8.44 isNzNat(3) -> tt 18.38/8.44 isNzNat(4) -> tt 18.38/8.44 isNzNat(5) -> tt 18.38/8.44 isNzNat(6) -> tt 18.38/8.44 isNzNat(7) -> tt 18.38/8.44 isNzNat(_*_(V1, V2)) -> U231(isNzNat(V1), V2) 18.38/8.44 isNzNat(gcd(V1, V2)) -> U241(isNzNat(V1), V2) 18.38/8.44 isNzNat(s_(V1)) -> U251(isNat(V1)) 18.38/8.44 p_(s_(N)) -> U261(isNat(N), N) 18.38/8.44 quot(M', M') -> U271(isNzNat(M')) 18.38/8.44 quot(N, M') -> U281(isNzNat(M'), M', N) 18.38/8.44 quot(N, M') -> U291(isNzNat(M'), M', N) 18.38/8.44 18.38/8.44 The set E consists of the following equations: 18.38/8.44 18.38/8.44 _*_(x, y) == _*_(y, x) 18.38/8.44 _+_(x, y) == _+_(y, x) 18.38/8.44 d(x, y) == d(y, x) 18.38/8.44 gcd(x, y) == gcd(y, x) 18.38/8.44 18.38/8.44 The set E# consists of the following equations: 18.38/8.44 18.38/8.44 _*_^1(x, y) == _*_^1(y, x) 18.38/8.44 _+_^1(x, y) == _+_^1(y, x) 18.38/8.44 D(x, y) == D(y, x) 18.38/8.44 GCD(x, y) == GCD(y, x) 18.38/8.44 18.38/8.44 We have to consider all minimal (P,E#,R,E)-chains 18.59/8.48 EOF