10.49/5.50 MAYBE 10.49/5.52 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 10.49/5.52 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 10.49/5.52 10.49/5.52 10.49/5.52 Termination of the given ETRS could not be shown: 10.49/5.52 10.49/5.52 (0) ETRS 10.49/5.52 (1) EquationalDependencyPairsProof [EQUIVALENT, 0 ms] 10.49/5.52 (2) EDP 10.49/5.52 (3) EDependencyGraphProof [EQUIVALENT, 0 ms] 10.49/5.52 (4) AND 10.49/5.52 (5) EDP 10.49/5.52 (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 10.49/5.52 (7) EDP 10.49/5.52 (8) EUsableRulesReductionPairsProof [EQUIVALENT, 42 ms] 10.49/5.52 (9) EDP 10.49/5.52 (10) PisEmptyProof [EQUIVALENT, 0 ms] 10.49/5.52 (11) YES 10.49/5.52 (12) EDP 10.49/5.52 (13) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 10.49/5.52 (14) EDP 10.49/5.52 (15) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 10.49/5.52 (16) EDP 10.49/5.52 (17) EDependencyGraphProof [EQUIVALENT, 0 ms] 10.49/5.52 (18) TRUE 10.49/5.52 (19) EDP 10.49/5.52 (20) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 10.49/5.52 (21) EDP 10.49/5.52 (22) EUsableRulesProof [EQUIVALENT, 0 ms] 10.49/5.52 (23) EDP 10.49/5.52 (24) EDP 10.49/5.52 (25) EDP 10.49/5.52 (26) EDP 10.49/5.52 10.49/5.52 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (0) 10.49/5.52 Obligation: 10.49/5.52 Equational rewrite system: 10.49/5.52 The TRS R consists of the following rules: 10.49/5.52 10.49/5.52 1 -> s_(0) 10.49/5.52 2 -> s_(s_(0)) 10.49/5.52 3 -> s_(s_(s_(0))) 10.49/5.52 4 -> s_(s_(s_(s_(0)))) 10.49/5.52 5 -> s_(s_(s_(s_(s_(0))))) 10.49/5.52 6 -> s_(s_(s_(s_(s_(s_(0)))))) 10.49/5.52 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 10.49/5.52 U11(tt, M, N) -> U12(tt, M, N) 10.49/5.52 U12(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 10.49/5.52 U21(tt, M, N) -> U22(tt, M, N) 10.49/5.52 U22(tt, M, N) -> s_(s_(_+_(N, M))) 10.49/5.52 U31(tt, M, N) -> U32(tt, M, N) 10.49/5.52 U32(tt, M, N) -> _>_(M, N) 10.49/5.52 U41(tt, M, N) -> U42(tt, M, N) 10.49/5.52 U42(tt, M, N) -> _>_(N, M) 10.49/5.52 U51(tt, M, N) -> U52(tt, M, N) 10.49/5.52 U52(tt, M, N) -> d(N, M) 10.49/5.52 U61(tt, M', N') -> U62(tt, M', N') 10.49/5.52 U62(tt, M', N') -> U63(equal(_>_(N', M'), true), M', N') 10.49/5.52 U63(tt, M', N') -> gcd(d(N', M'), M') 10.49/5.52 U71(tt, M', N) -> U72(tt, M', N) 10.49/5.52 U72(tt, M', N) -> U73(equal(_>_(M', N), true)) 10.49/5.52 U73(tt) -> 0 10.49/5.52 U81(tt, M', N) -> U82(tt, M', N) 10.49/5.52 U82(tt, M', N) -> U83(equal(_>_(N, M'), true), M', N) 10.49/5.52 U83(tt, M', N) -> s_(quot(d(N, M'), M')) 10.49/5.52 _*_(N, 0) -> 0 10.49/5.52 _*_(s_(N), s_(M)) -> U11(tt, M, N) 10.49/5.52 _+_(N, 0) -> N 10.49/5.52 _+_(s_(N), s_(M)) -> U21(tt, M, N) 10.49/5.52 _<_(N, M) -> U31(tt, M, N) 10.49/5.52 _>_(0, M) -> false 10.49/5.52 _>_(N', 0) -> true 10.49/5.52 _>_(s_(N), s_(M)) -> U41(tt, M, N) 10.49/5.52 d(0, N) -> N 10.49/5.52 d(s_(N), s_(M)) -> U51(tt, M, N) 10.49/5.52 equal(X, X) -> tt 10.49/5.52 gcd(0, N) -> 0 10.49/5.52 gcd(N', M') -> U61(tt, M', N') 10.49/5.52 gcd(N', N') -> N' 10.49/5.52 p_(s_(N)) -> N 10.49/5.52 quot(M', M') -> s_(0) 10.49/5.52 quot(N, M') -> U71(tt, M', N) 10.49/5.52 quot(N, M') -> U81(tt, M', N) 10.49/5.52 10.49/5.52 The set E consists of the following equations: 10.49/5.52 10.49/5.52 _*_(x, y) == _*_(y, x) 10.49/5.52 _+_(x, y) == _+_(y, x) 10.49/5.52 d(x, y) == d(y, x) 10.49/5.52 gcd(x, y) == gcd(y, x) 10.49/5.52 10.49/5.52 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (1) EquationalDependencyPairsProof (EQUIVALENT) 10.49/5.52 Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: 10.49/5.52 The TRS P consists of the following rules: 10.49/5.52 10.49/5.52 U11^1(tt, M, N) -> U12^1(tt, M, N) 10.49/5.52 U12^1(tt, M, N) -> _+_^1(N, _+_(M, _*_(N, M))) 10.49/5.52 U12^1(tt, M, N) -> _+_^1(M, _*_(N, M)) 10.49/5.52 U12^1(tt, M, N) -> _*_^1(N, M) 10.49/5.52 U21^1(tt, M, N) -> U22^1(tt, M, N) 10.49/5.52 U22^1(tt, M, N) -> _+_^1(N, M) 10.49/5.52 U31^1(tt, M, N) -> U32^1(tt, M, N) 10.49/5.52 U32^1(tt, M, N) -> _>_^1(M, N) 10.49/5.52 U41^1(tt, M, N) -> U42^1(tt, M, N) 10.49/5.52 U42^1(tt, M, N) -> _>_^1(N, M) 10.49/5.52 U51^1(tt, M, N) -> U52^1(tt, M, N) 10.49/5.52 U52^1(tt, M, N) -> D(N, M) 10.49/5.52 U61^1(tt, M', N') -> U62^1(tt, M', N') 10.49/5.52 U62^1(tt, M', N') -> U63^1(equal(_>_(N', M'), true), M', N') 10.49/5.52 U62^1(tt, M', N') -> EQUAL(_>_(N', M'), true) 10.49/5.52 U62^1(tt, M', N') -> _>_^1(N', M') 10.49/5.52 U63^1(tt, M', N') -> GCD(d(N', M'), M') 10.49/5.52 U63^1(tt, M', N') -> D(N', M') 10.49/5.52 U71^1(tt, M', N) -> U72^1(tt, M', N) 10.49/5.52 U72^1(tt, M', N) -> U73^1(equal(_>_(M', N), true)) 10.49/5.52 U72^1(tt, M', N) -> EQUAL(_>_(M', N), true) 10.49/5.52 U72^1(tt, M', N) -> _>_^1(M', N) 10.49/5.52 U81^1(tt, M', N) -> U82^1(tt, M', N) 10.49/5.52 U82^1(tt, M', N) -> U83^1(equal(_>_(N, M'), true), M', N) 10.49/5.52 U82^1(tt, M', N) -> EQUAL(_>_(N, M'), true) 10.49/5.52 U82^1(tt, M', N) -> _>_^1(N, M') 10.49/5.52 U83^1(tt, M', N) -> QUOT(d(N, M'), M') 10.49/5.52 U83^1(tt, M', N) -> D(N, M') 10.49/5.52 _*_^1(s_(N), s_(M)) -> U11^1(tt, M, N) 10.49/5.52 _+_^1(s_(N), s_(M)) -> U21^1(tt, M, N) 10.49/5.52 _<_^1(N, M) -> U31^1(tt, M, N) 10.49/5.52 _>_^1(s_(N), s_(M)) -> U41^1(tt, M, N) 10.49/5.52 D(s_(N), s_(M)) -> U51^1(tt, M, N) 10.49/5.52 GCD(N', M') -> U61^1(tt, M', N') 10.49/5.52 QUOT(N, M') -> U71^1(tt, M', N) 10.49/5.52 QUOT(N, M') -> U81^1(tt, M', N) 10.49/5.52 10.49/5.52 The TRS R consists of the following rules: 10.49/5.52 10.49/5.52 1 -> s_(0) 10.49/5.52 2 -> s_(s_(0)) 10.49/5.52 3 -> s_(s_(s_(0))) 10.49/5.52 4 -> s_(s_(s_(s_(0)))) 10.49/5.52 5 -> s_(s_(s_(s_(s_(0))))) 10.49/5.52 6 -> s_(s_(s_(s_(s_(s_(0)))))) 10.49/5.52 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 10.49/5.52 U11(tt, M, N) -> U12(tt, M, N) 10.49/5.52 U12(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 10.49/5.52 U21(tt, M, N) -> U22(tt, M, N) 10.49/5.52 U22(tt, M, N) -> s_(s_(_+_(N, M))) 10.49/5.52 U31(tt, M, N) -> U32(tt, M, N) 10.49/5.52 U32(tt, M, N) -> _>_(M, N) 10.49/5.52 U41(tt, M, N) -> U42(tt, M, N) 10.49/5.52 U42(tt, M, N) -> _>_(N, M) 10.49/5.52 U51(tt, M, N) -> U52(tt, M, N) 10.49/5.52 U52(tt, M, N) -> d(N, M) 10.49/5.52 U61(tt, M', N') -> U62(tt, M', N') 10.49/5.52 U62(tt, M', N') -> U63(equal(_>_(N', M'), true), M', N') 10.49/5.52 U63(tt, M', N') -> gcd(d(N', M'), M') 10.49/5.52 U71(tt, M', N) -> U72(tt, M', N) 10.49/5.52 U72(tt, M', N) -> U73(equal(_>_(M', N), true)) 10.49/5.52 U73(tt) -> 0 10.49/5.52 U81(tt, M', N) -> U82(tt, M', N) 10.49/5.52 U82(tt, M', N) -> U83(equal(_>_(N, M'), true), M', N) 10.49/5.52 U83(tt, M', N) -> s_(quot(d(N, M'), M')) 10.49/5.52 _*_(N, 0) -> 0 10.49/5.52 _*_(s_(N), s_(M)) -> U11(tt, M, N) 10.49/5.52 _+_(N, 0) -> N 10.49/5.52 _+_(s_(N), s_(M)) -> U21(tt, M, N) 10.49/5.52 _<_(N, M) -> U31(tt, M, N) 10.49/5.52 _>_(0, M) -> false 10.49/5.52 _>_(N', 0) -> true 10.49/5.52 _>_(s_(N), s_(M)) -> U41(tt, M, N) 10.49/5.52 d(0, N) -> N 10.49/5.52 d(s_(N), s_(M)) -> U51(tt, M, N) 10.49/5.52 equal(X, X) -> tt 10.49/5.52 gcd(0, N) -> 0 10.49/5.52 gcd(N', M') -> U61(tt, M', N') 10.49/5.52 gcd(N', N') -> N' 10.49/5.52 p_(s_(N)) -> N 10.49/5.52 quot(M', M') -> s_(0) 10.49/5.52 quot(N, M') -> U71(tt, M', N) 10.49/5.52 quot(N, M') -> U81(tt, M', N) 10.49/5.52 10.49/5.52 The set E consists of the following equations: 10.49/5.52 10.49/5.52 _*_(x, y) == _*_(y, x) 10.49/5.52 _+_(x, y) == _+_(y, x) 10.49/5.52 d(x, y) == d(y, x) 10.49/5.52 gcd(x, y) == gcd(y, x) 10.49/5.52 10.49/5.52 The set E# consists of the following equations: 10.49/5.52 10.49/5.52 _*_^1(x, y) == _*_^1(y, x) 10.49/5.52 _+_^1(x, y) == _+_^1(y, x) 10.49/5.52 D(x, y) == D(y, x) 10.49/5.52 GCD(x, y) == GCD(y, x) 10.49/5.52 10.49/5.52 We have to consider all minimal (P,E#,R,E)-chains 10.49/5.52 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (2) 10.49/5.52 Obligation: 10.49/5.52 The TRS P consists of the following rules: 10.49/5.52 10.49/5.52 U11^1(tt, M, N) -> U12^1(tt, M, N) 10.49/5.52 U12^1(tt, M, N) -> _+_^1(N, _+_(M, _*_(N, M))) 10.49/5.52 U12^1(tt, M, N) -> _+_^1(M, _*_(N, M)) 10.49/5.52 U12^1(tt, M, N) -> _*_^1(N, M) 10.49/5.52 U21^1(tt, M, N) -> U22^1(tt, M, N) 10.49/5.52 U22^1(tt, M, N) -> _+_^1(N, M) 10.49/5.52 U31^1(tt, M, N) -> U32^1(tt, M, N) 10.49/5.52 U32^1(tt, M, N) -> _>_^1(M, N) 10.49/5.52 U41^1(tt, M, N) -> U42^1(tt, M, N) 10.49/5.52 U42^1(tt, M, N) -> _>_^1(N, M) 10.49/5.52 U51^1(tt, M, N) -> U52^1(tt, M, N) 10.49/5.52 U52^1(tt, M, N) -> D(N, M) 10.49/5.52 U61^1(tt, M', N') -> U62^1(tt, M', N') 10.49/5.52 U62^1(tt, M', N') -> U63^1(equal(_>_(N', M'), true), M', N') 10.49/5.52 U62^1(tt, M', N') -> EQUAL(_>_(N', M'), true) 10.49/5.52 U62^1(tt, M', N') -> _>_^1(N', M') 10.49/5.52 U63^1(tt, M', N') -> GCD(d(N', M'), M') 10.49/5.52 U63^1(tt, M', N') -> D(N', M') 10.49/5.52 U71^1(tt, M', N) -> U72^1(tt, M', N) 10.49/5.52 U72^1(tt, M', N) -> U73^1(equal(_>_(M', N), true)) 10.49/5.52 U72^1(tt, M', N) -> EQUAL(_>_(M', N), true) 10.49/5.52 U72^1(tt, M', N) -> _>_^1(M', N) 10.49/5.52 U81^1(tt, M', N) -> U82^1(tt, M', N) 10.49/5.52 U82^1(tt, M', N) -> U83^1(equal(_>_(N, M'), true), M', N) 10.49/5.52 U82^1(tt, M', N) -> EQUAL(_>_(N, M'), true) 10.49/5.52 U82^1(tt, M', N) -> _>_^1(N, M') 10.49/5.52 U83^1(tt, M', N) -> QUOT(d(N, M'), M') 10.49/5.52 U83^1(tt, M', N) -> D(N, M') 10.49/5.52 _*_^1(s_(N), s_(M)) -> U11^1(tt, M, N) 10.49/5.52 _+_^1(s_(N), s_(M)) -> U21^1(tt, M, N) 10.49/5.52 _<_^1(N, M) -> U31^1(tt, M, N) 10.49/5.52 _>_^1(s_(N), s_(M)) -> U41^1(tt, M, N) 10.49/5.52 D(s_(N), s_(M)) -> U51^1(tt, M, N) 10.49/5.52 GCD(N', M') -> U61^1(tt, M', N') 10.49/5.52 QUOT(N, M') -> U71^1(tt, M', N) 10.49/5.52 QUOT(N, M') -> U81^1(tt, M', N) 10.49/5.52 10.49/5.52 The TRS R consists of the following rules: 10.49/5.52 10.49/5.52 1 -> s_(0) 10.49/5.52 2 -> s_(s_(0)) 10.49/5.52 3 -> s_(s_(s_(0))) 10.49/5.52 4 -> s_(s_(s_(s_(0)))) 10.49/5.52 5 -> s_(s_(s_(s_(s_(0))))) 10.49/5.52 6 -> s_(s_(s_(s_(s_(s_(0)))))) 10.49/5.52 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 10.49/5.52 U11(tt, M, N) -> U12(tt, M, N) 10.49/5.52 U12(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 10.49/5.52 U21(tt, M, N) -> U22(tt, M, N) 10.49/5.52 U22(tt, M, N) -> s_(s_(_+_(N, M))) 10.49/5.52 U31(tt, M, N) -> U32(tt, M, N) 10.49/5.52 U32(tt, M, N) -> _>_(M, N) 10.49/5.52 U41(tt, M, N) -> U42(tt, M, N) 10.49/5.52 U42(tt, M, N) -> _>_(N, M) 10.49/5.52 U51(tt, M, N) -> U52(tt, M, N) 10.49/5.52 U52(tt, M, N) -> d(N, M) 10.49/5.52 U61(tt, M', N') -> U62(tt, M', N') 10.49/5.52 U62(tt, M', N') -> U63(equal(_>_(N', M'), true), M', N') 10.49/5.52 U63(tt, M', N') -> gcd(d(N', M'), M') 10.49/5.52 U71(tt, M', N) -> U72(tt, M', N) 10.49/5.52 U72(tt, M', N) -> U73(equal(_>_(M', N), true)) 10.49/5.52 U73(tt) -> 0 10.49/5.52 U81(tt, M', N) -> U82(tt, M', N) 10.49/5.52 U82(tt, M', N) -> U83(equal(_>_(N, M'), true), M', N) 10.49/5.52 U83(tt, M', N) -> s_(quot(d(N, M'), M')) 10.49/5.52 _*_(N, 0) -> 0 10.49/5.52 _*_(s_(N), s_(M)) -> U11(tt, M, N) 10.49/5.52 _+_(N, 0) -> N 10.49/5.52 _+_(s_(N), s_(M)) -> U21(tt, M, N) 10.49/5.52 _<_(N, M) -> U31(tt, M, N) 10.49/5.52 _>_(0, M) -> false 10.49/5.52 _>_(N', 0) -> true 10.49/5.52 _>_(s_(N), s_(M)) -> U41(tt, M, N) 10.49/5.52 d(0, N) -> N 10.49/5.52 d(s_(N), s_(M)) -> U51(tt, M, N) 10.49/5.52 equal(X, X) -> tt 10.49/5.52 gcd(0, N) -> 0 10.49/5.52 gcd(N', M') -> U61(tt, M', N') 10.49/5.52 gcd(N', N') -> N' 10.49/5.52 p_(s_(N)) -> N 10.49/5.52 quot(M', M') -> s_(0) 10.49/5.52 quot(N, M') -> U71(tt, M', N) 10.49/5.52 quot(N, M') -> U81(tt, M', N) 10.49/5.52 10.49/5.52 The set E consists of the following equations: 10.49/5.52 10.49/5.52 _*_(x, y) == _*_(y, x) 10.49/5.52 _+_(x, y) == _+_(y, x) 10.49/5.52 d(x, y) == d(y, x) 10.49/5.52 gcd(x, y) == gcd(y, x) 10.49/5.52 10.49/5.52 The set E# consists of the following equations: 10.49/5.52 10.49/5.52 _*_^1(x, y) == _*_^1(y, x) 10.49/5.52 _+_^1(x, y) == _+_^1(y, x) 10.49/5.52 D(x, y) == D(y, x) 10.49/5.52 GCD(x, y) == GCD(y, x) 10.49/5.52 10.49/5.52 We have to consider all minimal (P,E#,R,E)-chains 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (3) EDependencyGraphProof (EQUIVALENT) 10.49/5.52 The approximation of the Equational Dependency Graph [DA_STEIN] contains 6 SCCs with 16 less nodes. 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (4) 10.49/5.52 Complex Obligation (AND) 10.49/5.52 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (5) 10.49/5.52 Obligation: 10.49/5.52 The TRS P consists of the following rules: 10.49/5.52 10.49/5.52 U51^1(tt, M, N) -> U52^1(tt, M, N) 10.49/5.52 D(s_(N), s_(M)) -> U51^1(tt, M, N) 10.49/5.52 U52^1(tt, M, N) -> D(N, M) 10.49/5.52 10.49/5.52 The TRS R consists of the following rules: 10.49/5.52 10.49/5.52 1 -> s_(0) 10.49/5.52 2 -> s_(s_(0)) 10.49/5.52 3 -> s_(s_(s_(0))) 10.49/5.52 4 -> s_(s_(s_(s_(0)))) 10.49/5.52 5 -> s_(s_(s_(s_(s_(0))))) 10.49/5.52 6 -> s_(s_(s_(s_(s_(s_(0)))))) 10.49/5.52 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 10.49/5.52 U11(tt, M, N) -> U12(tt, M, N) 10.49/5.52 U12(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 10.49/5.52 U21(tt, M, N) -> U22(tt, M, N) 10.49/5.52 U22(tt, M, N) -> s_(s_(_+_(N, M))) 10.49/5.52 U31(tt, M, N) -> U32(tt, M, N) 10.49/5.52 U32(tt, M, N) -> _>_(M, N) 10.49/5.52 U41(tt, M, N) -> U42(tt, M, N) 10.49/5.52 U42(tt, M, N) -> _>_(N, M) 10.49/5.52 U51(tt, M, N) -> U52(tt, M, N) 10.49/5.52 U52(tt, M, N) -> d(N, M) 10.49/5.52 U61(tt, M', N') -> U62(tt, M', N') 10.49/5.52 U62(tt, M', N') -> U63(equal(_>_(N', M'), true), M', N') 10.49/5.52 U63(tt, M', N') -> gcd(d(N', M'), M') 10.49/5.52 U71(tt, M', N) -> U72(tt, M', N) 10.49/5.52 U72(tt, M', N) -> U73(equal(_>_(M', N), true)) 10.49/5.52 U73(tt) -> 0 10.49/5.52 U81(tt, M', N) -> U82(tt, M', N) 10.49/5.52 U82(tt, M', N) -> U83(equal(_>_(N, M'), true), M', N) 10.49/5.52 U83(tt, M', N) -> s_(quot(d(N, M'), M')) 10.49/5.52 _*_(N, 0) -> 0 10.49/5.52 _*_(s_(N), s_(M)) -> U11(tt, M, N) 10.49/5.52 _+_(N, 0) -> N 10.49/5.52 _+_(s_(N), s_(M)) -> U21(tt, M, N) 10.49/5.52 _<_(N, M) -> U31(tt, M, N) 10.49/5.52 _>_(0, M) -> false 10.49/5.52 _>_(N', 0) -> true 10.49/5.52 _>_(s_(N), s_(M)) -> U41(tt, M, N) 10.49/5.52 d(0, N) -> N 10.49/5.52 d(s_(N), s_(M)) -> U51(tt, M, N) 10.49/5.52 equal(X, X) -> tt 10.49/5.52 gcd(0, N) -> 0 10.49/5.52 gcd(N', M') -> U61(tt, M', N') 10.49/5.52 gcd(N', N') -> N' 10.49/5.52 p_(s_(N)) -> N 10.49/5.52 quot(M', M') -> s_(0) 10.49/5.52 quot(N, M') -> U71(tt, M', N) 10.49/5.52 quot(N, M') -> U81(tt, M', N) 10.49/5.52 10.49/5.52 The set E consists of the following equations: 10.49/5.52 10.49/5.52 _*_(x, y) == _*_(y, x) 10.49/5.52 _+_(x, y) == _+_(y, x) 10.49/5.52 d(x, y) == d(y, x) 10.49/5.52 gcd(x, y) == gcd(y, x) 10.49/5.52 10.49/5.52 The set E# consists of the following equations: 10.49/5.52 10.49/5.52 _*_^1(x, y) == _*_^1(y, x) 10.49/5.52 _+_^1(x, y) == _+_^1(y, x) 10.49/5.52 D(x, y) == D(y, x) 10.49/5.52 GCD(x, y) == GCD(y, x) 10.49/5.52 10.49/5.52 We have to consider all minimal (P,E#,R,E)-chains 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (6) ESharpUsableEquationsProof (EQUIVALENT) 10.49/5.52 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 10.49/5.52 _*_^1(x, y) == _*_^1(y, x) 10.49/5.52 _+_^1(x, y) == _+_^1(y, x) 10.49/5.52 GCD(x, y) == GCD(y, x) 10.49/5.52 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (7) 10.49/5.52 Obligation: 10.49/5.52 The TRS P consists of the following rules: 10.49/5.52 10.49/5.52 U51^1(tt, M, N) -> U52^1(tt, M, N) 10.49/5.52 D(s_(N), s_(M)) -> U51^1(tt, M, N) 10.49/5.52 U52^1(tt, M, N) -> D(N, M) 10.49/5.52 10.49/5.52 The TRS R consists of the following rules: 10.49/5.52 10.49/5.52 1 -> s_(0) 10.49/5.52 2 -> s_(s_(0)) 10.49/5.52 3 -> s_(s_(s_(0))) 10.49/5.52 4 -> s_(s_(s_(s_(0)))) 10.49/5.52 5 -> s_(s_(s_(s_(s_(0))))) 10.49/5.52 6 -> s_(s_(s_(s_(s_(s_(0)))))) 10.49/5.52 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 10.49/5.52 U11(tt, M, N) -> U12(tt, M, N) 10.49/5.52 U12(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 10.49/5.52 U21(tt, M, N) -> U22(tt, M, N) 10.49/5.52 U22(tt, M, N) -> s_(s_(_+_(N, M))) 10.49/5.52 U31(tt, M, N) -> U32(tt, M, N) 10.49/5.52 U32(tt, M, N) -> _>_(M, N) 10.49/5.52 U41(tt, M, N) -> U42(tt, M, N) 10.49/5.52 U42(tt, M, N) -> _>_(N, M) 10.49/5.52 U51(tt, M, N) -> U52(tt, M, N) 10.49/5.52 U52(tt, M, N) -> d(N, M) 10.49/5.52 U61(tt, M', N') -> U62(tt, M', N') 10.49/5.52 U62(tt, M', N') -> U63(equal(_>_(N', M'), true), M', N') 10.49/5.52 U63(tt, M', N') -> gcd(d(N', M'), M') 10.49/5.52 U71(tt, M', N) -> U72(tt, M', N) 10.49/5.52 U72(tt, M', N) -> U73(equal(_>_(M', N), true)) 10.49/5.52 U73(tt) -> 0 10.49/5.52 U81(tt, M', N) -> U82(tt, M', N) 10.49/5.52 U82(tt, M', N) -> U83(equal(_>_(N, M'), true), M', N) 10.49/5.52 U83(tt, M', N) -> s_(quot(d(N, M'), M')) 10.49/5.52 _*_(N, 0) -> 0 10.49/5.52 _*_(s_(N), s_(M)) -> U11(tt, M, N) 10.49/5.52 _+_(N, 0) -> N 10.49/5.52 _+_(s_(N), s_(M)) -> U21(tt, M, N) 10.49/5.52 _<_(N, M) -> U31(tt, M, N) 10.49/5.52 _>_(0, M) -> false 10.49/5.52 _>_(N', 0) -> true 10.49/5.52 _>_(s_(N), s_(M)) -> U41(tt, M, N) 10.49/5.52 d(0, N) -> N 10.49/5.52 d(s_(N), s_(M)) -> U51(tt, M, N) 10.49/5.52 equal(X, X) -> tt 10.49/5.52 gcd(0, N) -> 0 10.49/5.52 gcd(N', M') -> U61(tt, M', N') 10.49/5.52 gcd(N', N') -> N' 10.49/5.52 p_(s_(N)) -> N 10.49/5.52 quot(M', M') -> s_(0) 10.49/5.52 quot(N, M') -> U71(tt, M', N) 10.49/5.52 quot(N, M') -> U81(tt, M', N) 10.49/5.52 10.49/5.52 The set E consists of the following equations: 10.49/5.52 10.49/5.52 _*_(x, y) == _*_(y, x) 10.49/5.52 _+_(x, y) == _+_(y, x) 10.49/5.52 d(x, y) == d(y, x) 10.49/5.52 gcd(x, y) == gcd(y, x) 10.49/5.52 10.49/5.52 The set E# consists of the following equations: 10.49/5.52 10.49/5.52 D(x, y) == D(y, x) 10.49/5.52 10.49/5.52 We have to consider all minimal (P,E#,R,E)-chains 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (8) EUsableRulesReductionPairsProof (EQUIVALENT) 10.49/5.52 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. 10.49/5.52 10.49/5.52 The following dependency pairs can be deleted: 10.49/5.52 10.49/5.52 U51^1(tt, M, N) -> U52^1(tt, M, N) 10.49/5.52 D(s_(N), s_(M)) -> U51^1(tt, M, N) 10.49/5.52 U52^1(tt, M, N) -> D(N, M) 10.49/5.52 The following rules are removed from R: 10.49/5.52 10.49/5.52 1 -> s_(0) 10.49/5.52 2 -> s_(s_(0)) 10.49/5.52 3 -> s_(s_(s_(0))) 10.49/5.52 4 -> s_(s_(s_(s_(0)))) 10.49/5.52 5 -> s_(s_(s_(s_(s_(0))))) 10.49/5.52 6 -> s_(s_(s_(s_(s_(s_(0)))))) 10.49/5.52 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 10.49/5.52 U11(tt, M, N) -> U12(tt, M, N) 10.49/5.52 U12(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 10.49/5.52 U21(tt, M, N) -> U22(tt, M, N) 10.49/5.52 U22(tt, M, N) -> s_(s_(_+_(N, M))) 10.49/5.52 U31(tt, M, N) -> U32(tt, M, N) 10.49/5.52 U32(tt, M, N) -> _>_(M, N) 10.49/5.52 U41(tt, M, N) -> U42(tt, M, N) 10.49/5.52 U42(tt, M, N) -> _>_(N, M) 10.49/5.52 U51(tt, M, N) -> U52(tt, M, N) 10.49/5.52 U52(tt, M, N) -> d(N, M) 10.49/5.52 U61(tt, M', N') -> U62(tt, M', N') 10.49/5.52 U62(tt, M', N') -> U63(equal(_>_(N', M'), true), M', N') 10.49/5.52 U63(tt, M', N') -> gcd(d(N', M'), M') 10.49/5.52 U71(tt, M', N) -> U72(tt, M', N) 10.49/5.52 U72(tt, M', N) -> U73(equal(_>_(M', N), true)) 10.49/5.52 U73(tt) -> 0 10.49/5.52 U81(tt, M', N) -> U82(tt, M', N) 10.49/5.52 U82(tt, M', N) -> U83(equal(_>_(N, M'), true), M', N) 10.49/5.52 U83(tt, M', N) -> s_(quot(d(N, M'), M')) 10.49/5.52 _*_(N, 0) -> 0 10.49/5.52 _*_(s_(N), s_(M)) -> U11(tt, M, N) 10.49/5.52 _+_(N, 0) -> N 10.49/5.52 _+_(s_(N), s_(M)) -> U21(tt, M, N) 10.49/5.52 _<_(N, M) -> U31(tt, M, N) 10.49/5.52 _>_(0, M) -> false 10.49/5.52 _>_(N', 0) -> true 10.49/5.52 _>_(s_(N), s_(M)) -> U41(tt, M, N) 10.49/5.52 d(0, N) -> N 10.49/5.52 d(s_(N), s_(M)) -> U51(tt, M, N) 10.49/5.52 equal(X, X) -> tt 10.49/5.52 gcd(0, N) -> 0 10.49/5.52 gcd(N', M') -> U61(tt, M', N') 10.49/5.52 gcd(N', N') -> N' 10.49/5.52 p_(s_(N)) -> N 10.49/5.52 quot(M', M') -> s_(0) 10.49/5.52 quot(N, M') -> U71(tt, M', N) 10.49/5.52 quot(N, M') -> U81(tt, M', N) 10.49/5.52 The following equations are removed from E: 10.49/5.52 10.49/5.52 _*_(x, y) == _*_(y, x) 10.49/5.52 _+_(x, y) == _+_(y, x) 10.49/5.52 d(x, y) == d(y, x) 10.49/5.52 gcd(x, y) == gcd(y, x) 10.49/5.52 Used ordering: POLO with Polynomial interpretation [POLO]: 10.49/5.52 10.49/5.52 POL(D(x_1, x_2)) = 2*x_1 + 2*x_2 10.49/5.52 POL(U51^1(x_1, x_2, x_3)) = 3 + 2*x_1 + 2*x_2 + 2*x_3 10.49/5.52 POL(U52^1(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + 2*x_3 10.49/5.52 POL(s_(x_1)) = 2 + 2*x_1 10.49/5.52 POL(tt) = 0 10.49/5.52 10.49/5.52 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (9) 10.49/5.52 Obligation: 10.49/5.52 P is empty. 10.49/5.52 R is empty. 10.49/5.52 E is empty. 10.49/5.52 The set E# consists of the following equations: 10.49/5.52 10.49/5.52 D(x, y) == D(y, x) 10.49/5.52 10.49/5.52 We have to consider all minimal (P,E#,R,E)-chains 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (10) PisEmptyProof (EQUIVALENT) 10.49/5.52 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (11) 10.49/5.52 YES 10.49/5.52 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (12) 10.49/5.52 Obligation: 10.49/5.52 The TRS P consists of the following rules: 10.49/5.52 10.49/5.52 U42^1(tt, M, N) -> _>_^1(N, M) 10.49/5.52 _>_^1(s_(N), s_(M)) -> U41^1(tt, M, N) 10.49/5.52 U41^1(tt, M, N) -> U42^1(tt, M, N) 10.49/5.52 10.49/5.52 The TRS R consists of the following rules: 10.49/5.52 10.49/5.52 1 -> s_(0) 10.49/5.52 2 -> s_(s_(0)) 10.49/5.52 3 -> s_(s_(s_(0))) 10.49/5.52 4 -> s_(s_(s_(s_(0)))) 10.49/5.52 5 -> s_(s_(s_(s_(s_(0))))) 10.49/5.52 6 -> s_(s_(s_(s_(s_(s_(0)))))) 10.49/5.52 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 10.49/5.52 U11(tt, M, N) -> U12(tt, M, N) 10.49/5.52 U12(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 10.49/5.52 U21(tt, M, N) -> U22(tt, M, N) 10.49/5.52 U22(tt, M, N) -> s_(s_(_+_(N, M))) 10.49/5.52 U31(tt, M, N) -> U32(tt, M, N) 10.49/5.52 U32(tt, M, N) -> _>_(M, N) 10.49/5.52 U41(tt, M, N) -> U42(tt, M, N) 10.49/5.52 U42(tt, M, N) -> _>_(N, M) 10.49/5.52 U51(tt, M, N) -> U52(tt, M, N) 10.49/5.52 U52(tt, M, N) -> d(N, M) 10.49/5.52 U61(tt, M', N') -> U62(tt, M', N') 10.49/5.52 U62(tt, M', N') -> U63(equal(_>_(N', M'), true), M', N') 10.49/5.52 U63(tt, M', N') -> gcd(d(N', M'), M') 10.49/5.52 U71(tt, M', N) -> U72(tt, M', N) 10.49/5.52 U72(tt, M', N) -> U73(equal(_>_(M', N), true)) 10.49/5.52 U73(tt) -> 0 10.49/5.52 U81(tt, M', N) -> U82(tt, M', N) 10.49/5.52 U82(tt, M', N) -> U83(equal(_>_(N, M'), true), M', N) 10.49/5.52 U83(tt, M', N) -> s_(quot(d(N, M'), M')) 10.49/5.52 _*_(N, 0) -> 0 10.49/5.52 _*_(s_(N), s_(M)) -> U11(tt, M, N) 10.49/5.52 _+_(N, 0) -> N 10.49/5.52 _+_(s_(N), s_(M)) -> U21(tt, M, N) 10.49/5.52 _<_(N, M) -> U31(tt, M, N) 10.49/5.52 _>_(0, M) -> false 10.49/5.52 _>_(N', 0) -> true 10.49/5.52 _>_(s_(N), s_(M)) -> U41(tt, M, N) 10.49/5.52 d(0, N) -> N 10.49/5.52 d(s_(N), s_(M)) -> U51(tt, M, N) 10.49/5.52 equal(X, X) -> tt 10.49/5.52 gcd(0, N) -> 0 10.49/5.52 gcd(N', M') -> U61(tt, M', N') 10.49/5.52 gcd(N', N') -> N' 10.49/5.52 p_(s_(N)) -> N 10.49/5.52 quot(M', M') -> s_(0) 10.49/5.52 quot(N, M') -> U71(tt, M', N) 10.49/5.52 quot(N, M') -> U81(tt, M', N) 10.49/5.52 10.49/5.52 The set E consists of the following equations: 10.49/5.52 10.49/5.52 _*_(x, y) == _*_(y, x) 10.49/5.52 _+_(x, y) == _+_(y, x) 10.49/5.52 d(x, y) == d(y, x) 10.49/5.52 gcd(x, y) == gcd(y, x) 10.49/5.52 10.49/5.52 The set E# consists of the following equations: 10.49/5.52 10.49/5.52 _*_^1(x, y) == _*_^1(y, x) 10.49/5.52 _+_^1(x, y) == _+_^1(y, x) 10.49/5.52 D(x, y) == D(y, x) 10.49/5.52 GCD(x, y) == GCD(y, x) 10.49/5.52 10.49/5.52 We have to consider all minimal (P,E#,R,E)-chains 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (13) ESharpUsableEquationsProof (EQUIVALENT) 10.49/5.52 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 10.49/5.52 _*_^1(x, y) == _*_^1(y, x) 10.49/5.52 _+_^1(x, y) == _+_^1(y, x) 10.49/5.52 D(x, y) == D(y, x) 10.49/5.52 GCD(x, y) == GCD(y, x) 10.49/5.52 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (14) 10.49/5.52 Obligation: 10.49/5.52 The TRS P consists of the following rules: 10.49/5.52 10.49/5.52 U42^1(tt, M, N) -> _>_^1(N, M) 10.49/5.52 _>_^1(s_(N), s_(M)) -> U41^1(tt, M, N) 10.49/5.52 U41^1(tt, M, N) -> U42^1(tt, M, N) 10.49/5.52 10.49/5.52 The TRS R consists of the following rules: 10.49/5.52 10.49/5.52 1 -> s_(0) 10.49/5.52 2 -> s_(s_(0)) 10.49/5.52 3 -> s_(s_(s_(0))) 10.49/5.52 4 -> s_(s_(s_(s_(0)))) 10.49/5.52 5 -> s_(s_(s_(s_(s_(0))))) 10.49/5.52 6 -> s_(s_(s_(s_(s_(s_(0)))))) 10.49/5.52 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 10.49/5.52 U11(tt, M, N) -> U12(tt, M, N) 10.49/5.52 U12(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 10.49/5.52 U21(tt, M, N) -> U22(tt, M, N) 10.49/5.52 U22(tt, M, N) -> s_(s_(_+_(N, M))) 10.49/5.52 U31(tt, M, N) -> U32(tt, M, N) 10.49/5.52 U32(tt, M, N) -> _>_(M, N) 10.49/5.52 U41(tt, M, N) -> U42(tt, M, N) 10.49/5.52 U42(tt, M, N) -> _>_(N, M) 10.49/5.52 U51(tt, M, N) -> U52(tt, M, N) 10.49/5.52 U52(tt, M, N) -> d(N, M) 10.49/5.52 U61(tt, M', N') -> U62(tt, M', N') 10.49/5.52 U62(tt, M', N') -> U63(equal(_>_(N', M'), true), M', N') 10.49/5.52 U63(tt, M', N') -> gcd(d(N', M'), M') 10.49/5.52 U71(tt, M', N) -> U72(tt, M', N) 10.49/5.52 U72(tt, M', N) -> U73(equal(_>_(M', N), true)) 10.49/5.52 U73(tt) -> 0 10.49/5.52 U81(tt, M', N) -> U82(tt, M', N) 10.49/5.52 U82(tt, M', N) -> U83(equal(_>_(N, M'), true), M', N) 10.49/5.52 U83(tt, M', N) -> s_(quot(d(N, M'), M')) 10.49/5.52 _*_(N, 0) -> 0 10.49/5.52 _*_(s_(N), s_(M)) -> U11(tt, M, N) 10.49/5.52 _+_(N, 0) -> N 10.49/5.52 _+_(s_(N), s_(M)) -> U21(tt, M, N) 10.49/5.52 _<_(N, M) -> U31(tt, M, N) 10.49/5.52 _>_(0, M) -> false 10.49/5.52 _>_(N', 0) -> true 10.49/5.52 _>_(s_(N), s_(M)) -> U41(tt, M, N) 10.49/5.52 d(0, N) -> N 10.49/5.52 d(s_(N), s_(M)) -> U51(tt, M, N) 10.49/5.52 equal(X, X) -> tt 10.49/5.52 gcd(0, N) -> 0 10.49/5.52 gcd(N', M') -> U61(tt, M', N') 10.49/5.52 gcd(N', N') -> N' 10.49/5.52 p_(s_(N)) -> N 10.49/5.52 quot(M', M') -> s_(0) 10.49/5.52 quot(N, M') -> U71(tt, M', N) 10.49/5.52 quot(N, M') -> U81(tt, M', N) 10.49/5.52 10.49/5.52 The set E consists of the following equations: 10.49/5.52 10.49/5.52 _*_(x, y) == _*_(y, x) 10.49/5.52 _+_(x, y) == _+_(y, x) 10.49/5.52 d(x, y) == d(y, x) 10.49/5.52 gcd(x, y) == gcd(y, x) 10.49/5.52 10.49/5.52 E# is empty. 10.49/5.52 We have to consider all minimal (P,E#,R,E)-chains 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (15) EUsableRulesReductionPairsProof (EQUIVALENT) 10.49/5.52 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. 10.49/5.52 10.49/5.52 The following dependency pairs can be deleted: 10.49/5.52 10.49/5.52 _>_^1(s_(N), s_(M)) -> U41^1(tt, M, N) 10.49/5.52 U41^1(tt, M, N) -> U42^1(tt, M, N) 10.49/5.52 The following rules are removed from R: 10.49/5.52 10.49/5.52 1 -> s_(0) 10.49/5.52 2 -> s_(s_(0)) 10.49/5.52 3 -> s_(s_(s_(0))) 10.49/5.52 4 -> s_(s_(s_(s_(0)))) 10.49/5.52 5 -> s_(s_(s_(s_(s_(0))))) 10.49/5.52 6 -> s_(s_(s_(s_(s_(s_(0)))))) 10.49/5.52 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 10.49/5.52 U11(tt, M, N) -> U12(tt, M, N) 10.49/5.52 U12(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 10.49/5.52 U21(tt, M, N) -> U22(tt, M, N) 10.49/5.52 U22(tt, M, N) -> s_(s_(_+_(N, M))) 10.49/5.52 U31(tt, M, N) -> U32(tt, M, N) 10.49/5.52 U32(tt, M, N) -> _>_(M, N) 10.49/5.52 U41(tt, M, N) -> U42(tt, M, N) 10.49/5.52 U42(tt, M, N) -> _>_(N, M) 10.49/5.52 U51(tt, M, N) -> U52(tt, M, N) 10.49/5.52 U52(tt, M, N) -> d(N, M) 10.49/5.52 U61(tt, M', N') -> U62(tt, M', N') 10.49/5.52 U62(tt, M', N') -> U63(equal(_>_(N', M'), true), M', N') 10.49/5.52 U63(tt, M', N') -> gcd(d(N', M'), M') 10.49/5.52 U71(tt, M', N) -> U72(tt, M', N) 10.49/5.52 U72(tt, M', N) -> U73(equal(_>_(M', N), true)) 10.49/5.52 U73(tt) -> 0 10.49/5.52 U81(tt, M', N) -> U82(tt, M', N) 10.49/5.52 U82(tt, M', N) -> U83(equal(_>_(N, M'), true), M', N) 10.49/5.52 U83(tt, M', N) -> s_(quot(d(N, M'), M')) 10.49/5.52 _*_(N, 0) -> 0 10.49/5.52 _*_(s_(N), s_(M)) -> U11(tt, M, N) 10.49/5.52 _+_(N, 0) -> N 10.49/5.52 _+_(s_(N), s_(M)) -> U21(tt, M, N) 10.49/5.52 _<_(N, M) -> U31(tt, M, N) 10.49/5.52 _>_(0, M) -> false 10.49/5.52 _>_(N', 0) -> true 10.49/5.52 _>_(s_(N), s_(M)) -> U41(tt, M, N) 10.49/5.52 d(0, N) -> N 10.49/5.52 d(s_(N), s_(M)) -> U51(tt, M, N) 10.49/5.52 equal(X, X) -> tt 10.49/5.52 gcd(0, N) -> 0 10.49/5.52 gcd(N', M') -> U61(tt, M', N') 10.49/5.52 gcd(N', N') -> N' 10.49/5.52 p_(s_(N)) -> N 10.49/5.52 quot(M', M') -> s_(0) 10.49/5.52 quot(N, M') -> U71(tt, M', N) 10.49/5.52 quot(N, M') -> U81(tt, M', N) 10.49/5.52 The following equations are removed from E: 10.49/5.52 10.49/5.52 _*_(x, y) == _*_(y, x) 10.49/5.52 _+_(x, y) == _+_(y, x) 10.49/5.52 d(x, y) == d(y, x) 10.49/5.52 gcd(x, y) == gcd(y, x) 10.49/5.52 Used ordering: POLO with Polynomial interpretation [POLO]: 10.49/5.52 10.49/5.52 POL(U41^1(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + 3*x_3 10.49/5.52 POL(U42^1(x_1, x_2, x_3)) = 2*x_1 + x_2 + 3*x_3 10.49/5.52 POL(_>_^1(x_1, x_2)) = 2 + 3*x_1 + x_2 10.49/5.52 POL(s_(x_1)) = 2 + 3*x_1 10.49/5.52 POL(tt) = 1 10.49/5.52 10.49/5.52 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (16) 10.49/5.52 Obligation: 10.49/5.52 The TRS P consists of the following rules: 10.49/5.52 10.49/5.52 U42^1(tt, M, N) -> _>_^1(N, M) 10.49/5.52 10.49/5.52 R is empty. 10.49/5.52 E is empty. 10.49/5.52 E# is empty. 10.49/5.52 We have to consider all minimal (P,E#,R,E)-chains 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (17) EDependencyGraphProof (EQUIVALENT) 10.49/5.52 The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 1 less node. 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (18) 10.49/5.52 TRUE 10.49/5.52 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (19) 10.49/5.52 Obligation: 10.49/5.52 The TRS P consists of the following rules: 10.49/5.52 10.49/5.52 U82^1(tt, M', N) -> U83^1(equal(_>_(N, M'), true), M', N) 10.49/5.52 QUOT(N, M') -> U81^1(tt, M', N) 10.49/5.52 U81^1(tt, M', N) -> U82^1(tt, M', N) 10.49/5.52 U83^1(tt, M', N) -> QUOT(d(N, M'), M') 10.49/5.52 10.49/5.52 The TRS R consists of the following rules: 10.49/5.52 10.49/5.52 1 -> s_(0) 10.49/5.52 2 -> s_(s_(0)) 10.49/5.52 3 -> s_(s_(s_(0))) 10.49/5.52 4 -> s_(s_(s_(s_(0)))) 10.49/5.52 5 -> s_(s_(s_(s_(s_(0))))) 10.49/5.52 6 -> s_(s_(s_(s_(s_(s_(0)))))) 10.49/5.52 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 10.49/5.52 U11(tt, M, N) -> U12(tt, M, N) 10.49/5.52 U12(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 10.49/5.52 U21(tt, M, N) -> U22(tt, M, N) 10.49/5.52 U22(tt, M, N) -> s_(s_(_+_(N, M))) 10.49/5.52 U31(tt, M, N) -> U32(tt, M, N) 10.49/5.52 U32(tt, M, N) -> _>_(M, N) 10.49/5.52 U41(tt, M, N) -> U42(tt, M, N) 10.49/5.52 U42(tt, M, N) -> _>_(N, M) 10.49/5.52 U51(tt, M, N) -> U52(tt, M, N) 10.49/5.52 U52(tt, M, N) -> d(N, M) 10.49/5.52 U61(tt, M', N') -> U62(tt, M', N') 10.49/5.52 U62(tt, M', N') -> U63(equal(_>_(N', M'), true), M', N') 10.49/5.52 U63(tt, M', N') -> gcd(d(N', M'), M') 10.49/5.52 U71(tt, M', N) -> U72(tt, M', N) 10.49/5.52 U72(tt, M', N) -> U73(equal(_>_(M', N), true)) 10.49/5.52 U73(tt) -> 0 10.49/5.52 U81(tt, M', N) -> U82(tt, M', N) 10.49/5.52 U82(tt, M', N) -> U83(equal(_>_(N, M'), true), M', N) 10.49/5.52 U83(tt, M', N) -> s_(quot(d(N, M'), M')) 10.49/5.52 _*_(N, 0) -> 0 10.49/5.52 _*_(s_(N), s_(M)) -> U11(tt, M, N) 10.49/5.52 _+_(N, 0) -> N 10.49/5.52 _+_(s_(N), s_(M)) -> U21(tt, M, N) 10.49/5.52 _<_(N, M) -> U31(tt, M, N) 10.49/5.52 _>_(0, M) -> false 10.49/5.52 _>_(N', 0) -> true 10.49/5.52 _>_(s_(N), s_(M)) -> U41(tt, M, N) 10.49/5.52 d(0, N) -> N 10.49/5.52 d(s_(N), s_(M)) -> U51(tt, M, N) 10.49/5.52 equal(X, X) -> tt 10.49/5.52 gcd(0, N) -> 0 10.49/5.52 gcd(N', M') -> U61(tt, M', N') 10.49/5.52 gcd(N', N') -> N' 10.49/5.52 p_(s_(N)) -> N 10.49/5.52 quot(M', M') -> s_(0) 10.49/5.52 quot(N, M') -> U71(tt, M', N) 10.49/5.52 quot(N, M') -> U81(tt, M', N) 10.49/5.52 10.49/5.52 The set E consists of the following equations: 10.49/5.52 10.49/5.52 _*_(x, y) == _*_(y, x) 10.49/5.52 _+_(x, y) == _+_(y, x) 10.49/5.52 d(x, y) == d(y, x) 10.49/5.52 gcd(x, y) == gcd(y, x) 10.49/5.52 10.49/5.52 The set E# consists of the following equations: 10.49/5.52 10.49/5.52 _*_^1(x, y) == _*_^1(y, x) 10.49/5.52 _+_^1(x, y) == _+_^1(y, x) 10.49/5.52 D(x, y) == D(y, x) 10.49/5.52 GCD(x, y) == GCD(y, x) 10.49/5.52 10.49/5.52 We have to consider all minimal (P,E#,R,E)-chains 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (20) ESharpUsableEquationsProof (EQUIVALENT) 10.49/5.52 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 10.49/5.52 _*_^1(x, y) == _*_^1(y, x) 10.49/5.52 _+_^1(x, y) == _+_^1(y, x) 10.49/5.52 D(x, y) == D(y, x) 10.49/5.52 GCD(x, y) == GCD(y, x) 10.49/5.52 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (21) 10.49/5.52 Obligation: 10.49/5.52 The TRS P consists of the following rules: 10.49/5.52 10.49/5.52 U82^1(tt, M', N) -> U83^1(equal(_>_(N, M'), true), M', N) 10.49/5.52 QUOT(N, M') -> U81^1(tt, M', N) 10.49/5.52 U81^1(tt, M', N) -> U82^1(tt, M', N) 10.49/5.52 U83^1(tt, M', N) -> QUOT(d(N, M'), M') 10.49/5.52 10.49/5.52 The TRS R consists of the following rules: 10.49/5.52 10.49/5.52 1 -> s_(0) 10.49/5.52 2 -> s_(s_(0)) 10.49/5.52 3 -> s_(s_(s_(0))) 10.49/5.52 4 -> s_(s_(s_(s_(0)))) 10.49/5.52 5 -> s_(s_(s_(s_(s_(0))))) 10.49/5.52 6 -> s_(s_(s_(s_(s_(s_(0)))))) 10.49/5.52 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 10.49/5.52 U11(tt, M, N) -> U12(tt, M, N) 10.49/5.52 U12(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 10.49/5.52 U21(tt, M, N) -> U22(tt, M, N) 10.49/5.52 U22(tt, M, N) -> s_(s_(_+_(N, M))) 10.49/5.52 U31(tt, M, N) -> U32(tt, M, N) 10.49/5.52 U32(tt, M, N) -> _>_(M, N) 10.49/5.52 U41(tt, M, N) -> U42(tt, M, N) 10.49/5.52 U42(tt, M, N) -> _>_(N, M) 10.49/5.52 U51(tt, M, N) -> U52(tt, M, N) 10.49/5.52 U52(tt, M, N) -> d(N, M) 10.49/5.52 U61(tt, M', N') -> U62(tt, M', N') 10.49/5.52 U62(tt, M', N') -> U63(equal(_>_(N', M'), true), M', N') 10.49/5.52 U63(tt, M', N') -> gcd(d(N', M'), M') 10.49/5.52 U71(tt, M', N) -> U72(tt, M', N) 10.49/5.52 U72(tt, M', N) -> U73(equal(_>_(M', N), true)) 10.49/5.52 U73(tt) -> 0 10.49/5.52 U81(tt, M', N) -> U82(tt, M', N) 10.49/5.52 U82(tt, M', N) -> U83(equal(_>_(N, M'), true), M', N) 10.49/5.52 U83(tt, M', N) -> s_(quot(d(N, M'), M')) 10.49/5.52 _*_(N, 0) -> 0 10.49/5.52 _*_(s_(N), s_(M)) -> U11(tt, M, N) 10.49/5.52 _+_(N, 0) -> N 10.49/5.52 _+_(s_(N), s_(M)) -> U21(tt, M, N) 10.49/5.52 _<_(N, M) -> U31(tt, M, N) 10.49/5.52 _>_(0, M) -> false 10.49/5.52 _>_(N', 0) -> true 10.49/5.52 _>_(s_(N), s_(M)) -> U41(tt, M, N) 10.49/5.52 d(0, N) -> N 10.49/5.52 d(s_(N), s_(M)) -> U51(tt, M, N) 10.49/5.52 equal(X, X) -> tt 10.49/5.52 gcd(0, N) -> 0 10.49/5.52 gcd(N', M') -> U61(tt, M', N') 10.49/5.52 gcd(N', N') -> N' 10.49/5.52 p_(s_(N)) -> N 10.49/5.52 quot(M', M') -> s_(0) 10.49/5.52 quot(N, M') -> U71(tt, M', N) 10.49/5.52 quot(N, M') -> U81(tt, M', N) 10.49/5.52 10.49/5.52 The set E consists of the following equations: 10.49/5.52 10.49/5.52 _*_(x, y) == _*_(y, x) 10.49/5.52 _+_(x, y) == _+_(y, x) 10.49/5.52 d(x, y) == d(y, x) 10.49/5.52 gcd(x, y) == gcd(y, x) 10.49/5.52 10.49/5.52 E# is empty. 10.49/5.52 We have to consider all minimal (P,E#,R,E)-chains 10.49/5.52 ---------------------------------------- 10.49/5.52 10.49/5.52 (22) EUsableRulesProof (EQUIVALENT) 10.49/5.52 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: 10.49/5.52 c(x, y) -> x 10.49/5.52 c(x, y) -> y 10.61/5.52 10.61/5.52 ---------------------------------------- 10.61/5.52 10.61/5.52 (23) 10.61/5.52 Obligation: 10.61/5.52 The TRS P consists of the following rules: 10.61/5.52 10.61/5.52 U82^1(tt, M', N) -> U83^1(equal(_>_(N, M'), true), M', N) 10.61/5.52 QUOT(N, M') -> U81^1(tt, M', N) 10.61/5.52 U81^1(tt, M', N) -> U82^1(tt, M', N) 10.61/5.52 U83^1(tt, M', N) -> QUOT(d(N, M'), M') 10.61/5.52 10.61/5.52 The TRS R consists of the following rules: 10.61/5.52 10.61/5.52 equal(X, X) -> tt 10.61/5.52 _>_(0, M) -> false 10.61/5.52 U42(tt, M, N) -> _>_(N, M) 10.61/5.52 U41(tt, M, N) -> U42(tt, M, N) 10.61/5.52 d(s_(N), s_(M)) -> U51(tt, M, N) 10.61/5.52 U51(tt, M, N) -> U52(tt, M, N) 10.61/5.52 _>_(s_(N), s_(M)) -> U41(tt, M, N) 10.61/5.52 _>_(N', 0) -> true 10.61/5.52 U52(tt, M, N) -> d(N, M) 10.61/5.52 d(0, N) -> N 10.61/5.52 c(x, y) -> x 10.61/5.52 c(x, y) -> y 10.61/5.52 10.61/5.52 The set E consists of the following equations: 10.61/5.52 10.61/5.52 d(x, y) == d(y, x) 10.61/5.52 10.61/5.52 E# is empty. 10.61/5.52 We have to consider all (P,E#,R,E)-chains 10.61/5.52 ---------------------------------------- 10.61/5.52 10.61/5.52 (24) 10.61/5.52 Obligation: 10.61/5.52 The TRS P consists of the following rules: 10.61/5.52 10.61/5.52 U62^1(tt, M', N') -> U63^1(equal(_>_(N', M'), true), M', N') 10.61/5.52 GCD(N', M') -> U61^1(tt, M', N') 10.61/5.52 U61^1(tt, M', N') -> U62^1(tt, M', N') 10.61/5.52 U63^1(tt, M', N') -> GCD(d(N', M'), M') 10.61/5.52 10.61/5.52 The TRS R consists of the following rules: 10.61/5.52 10.61/5.52 1 -> s_(0) 10.61/5.52 2 -> s_(s_(0)) 10.61/5.52 3 -> s_(s_(s_(0))) 10.61/5.52 4 -> s_(s_(s_(s_(0)))) 10.61/5.52 5 -> s_(s_(s_(s_(s_(0))))) 10.61/5.52 6 -> s_(s_(s_(s_(s_(s_(0)))))) 10.61/5.52 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 10.61/5.52 U11(tt, M, N) -> U12(tt, M, N) 10.61/5.52 U12(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 10.61/5.52 U21(tt, M, N) -> U22(tt, M, N) 10.61/5.52 U22(tt, M, N) -> s_(s_(_+_(N, M))) 10.61/5.52 U31(tt, M, N) -> U32(tt, M, N) 10.61/5.52 U32(tt, M, N) -> _>_(M, N) 10.61/5.52 U41(tt, M, N) -> U42(tt, M, N) 10.61/5.52 U42(tt, M, N) -> _>_(N, M) 10.61/5.52 U51(tt, M, N) -> U52(tt, M, N) 10.61/5.52 U52(tt, M, N) -> d(N, M) 10.61/5.52 U61(tt, M', N') -> U62(tt, M', N') 10.61/5.52 U62(tt, M', N') -> U63(equal(_>_(N', M'), true), M', N') 10.61/5.52 U63(tt, M', N') -> gcd(d(N', M'), M') 10.61/5.52 U71(tt, M', N) -> U72(tt, M', N) 10.61/5.52 U72(tt, M', N) -> U73(equal(_>_(M', N), true)) 10.61/5.52 U73(tt) -> 0 10.61/5.52 U81(tt, M', N) -> U82(tt, M', N) 10.61/5.52 U82(tt, M', N) -> U83(equal(_>_(N, M'), true), M', N) 10.61/5.52 U83(tt, M', N) -> s_(quot(d(N, M'), M')) 10.61/5.52 _*_(N, 0) -> 0 10.61/5.52 _*_(s_(N), s_(M)) -> U11(tt, M, N) 10.61/5.52 _+_(N, 0) -> N 10.61/5.52 _+_(s_(N), s_(M)) -> U21(tt, M, N) 10.61/5.52 _<_(N, M) -> U31(tt, M, N) 10.61/5.52 _>_(0, M) -> false 10.61/5.52 _>_(N', 0) -> true 10.61/5.52 _>_(s_(N), s_(M)) -> U41(tt, M, N) 10.61/5.52 d(0, N) -> N 10.61/5.52 d(s_(N), s_(M)) -> U51(tt, M, N) 10.61/5.52 equal(X, X) -> tt 10.61/5.52 gcd(0, N) -> 0 10.61/5.52 gcd(N', M') -> U61(tt, M', N') 10.61/5.52 gcd(N', N') -> N' 10.61/5.52 p_(s_(N)) -> N 10.61/5.52 quot(M', M') -> s_(0) 10.61/5.52 quot(N, M') -> U71(tt, M', N) 10.61/5.52 quot(N, M') -> U81(tt, M', N) 10.61/5.52 10.61/5.52 The set E consists of the following equations: 10.61/5.52 10.61/5.52 _*_(x, y) == _*_(y, x) 10.61/5.52 _+_(x, y) == _+_(y, x) 10.61/5.52 d(x, y) == d(y, x) 10.61/5.52 gcd(x, y) == gcd(y, x) 10.61/5.52 10.61/5.52 The set E# consists of the following equations: 10.61/5.52 10.61/5.52 _*_^1(x, y) == _*_^1(y, x) 10.61/5.52 _+_^1(x, y) == _+_^1(y, x) 10.61/5.52 D(x, y) == D(y, x) 10.61/5.52 GCD(x, y) == GCD(y, x) 10.61/5.52 10.61/5.52 We have to consider all minimal (P,E#,R,E)-chains 10.61/5.52 ---------------------------------------- 10.61/5.52 10.61/5.52 (25) 10.61/5.52 Obligation: 10.61/5.52 The TRS P consists of the following rules: 10.61/5.52 10.61/5.52 _+_^1(s_(N), s_(M)) -> U21^1(tt, M, N) 10.61/5.52 U21^1(tt, M, N) -> U22^1(tt, M, N) 10.61/5.52 U22^1(tt, M, N) -> _+_^1(N, M) 10.61/5.52 10.61/5.52 The TRS R consists of the following rules: 10.61/5.52 10.61/5.52 1 -> s_(0) 10.61/5.52 2 -> s_(s_(0)) 10.61/5.52 3 -> s_(s_(s_(0))) 10.61/5.52 4 -> s_(s_(s_(s_(0)))) 10.61/5.52 5 -> s_(s_(s_(s_(s_(0))))) 10.61/5.52 6 -> s_(s_(s_(s_(s_(s_(0)))))) 10.61/5.52 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 10.61/5.52 U11(tt, M, N) -> U12(tt, M, N) 10.61/5.52 U12(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 10.61/5.52 U21(tt, M, N) -> U22(tt, M, N) 10.61/5.52 U22(tt, M, N) -> s_(s_(_+_(N, M))) 10.61/5.52 U31(tt, M, N) -> U32(tt, M, N) 10.61/5.52 U32(tt, M, N) -> _>_(M, N) 10.61/5.52 U41(tt, M, N) -> U42(tt, M, N) 10.61/5.52 U42(tt, M, N) -> _>_(N, M) 10.61/5.52 U51(tt, M, N) -> U52(tt, M, N) 10.61/5.52 U52(tt, M, N) -> d(N, M) 10.61/5.52 U61(tt, M', N') -> U62(tt, M', N') 10.61/5.52 U62(tt, M', N') -> U63(equal(_>_(N', M'), true), M', N') 10.61/5.52 U63(tt, M', N') -> gcd(d(N', M'), M') 10.61/5.52 U71(tt, M', N) -> U72(tt, M', N) 10.61/5.52 U72(tt, M', N) -> U73(equal(_>_(M', N), true)) 10.61/5.52 U73(tt) -> 0 10.61/5.52 U81(tt, M', N) -> U82(tt, M', N) 10.61/5.52 U82(tt, M', N) -> U83(equal(_>_(N, M'), true), M', N) 10.61/5.52 U83(tt, M', N) -> s_(quot(d(N, M'), M')) 10.61/5.52 _*_(N, 0) -> 0 10.61/5.52 _*_(s_(N), s_(M)) -> U11(tt, M, N) 10.61/5.52 _+_(N, 0) -> N 10.61/5.52 _+_(s_(N), s_(M)) -> U21(tt, M, N) 10.61/5.52 _<_(N, M) -> U31(tt, M, N) 10.61/5.52 _>_(0, M) -> false 10.61/5.52 _>_(N', 0) -> true 10.61/5.52 _>_(s_(N), s_(M)) -> U41(tt, M, N) 10.61/5.52 d(0, N) -> N 10.61/5.52 d(s_(N), s_(M)) -> U51(tt, M, N) 10.61/5.52 equal(X, X) -> tt 10.61/5.52 gcd(0, N) -> 0 10.61/5.52 gcd(N', M') -> U61(tt, M', N') 10.61/5.52 gcd(N', N') -> N' 10.61/5.52 p_(s_(N)) -> N 10.61/5.52 quot(M', M') -> s_(0) 10.61/5.52 quot(N, M') -> U71(tt, M', N) 10.61/5.52 quot(N, M') -> U81(tt, M', N) 10.61/5.52 10.61/5.52 The set E consists of the following equations: 10.61/5.52 10.61/5.52 _*_(x, y) == _*_(y, x) 10.61/5.52 _+_(x, y) == _+_(y, x) 10.61/5.52 d(x, y) == d(y, x) 10.61/5.52 gcd(x, y) == gcd(y, x) 10.61/5.52 10.61/5.52 The set E# consists of the following equations: 10.61/5.52 10.61/5.52 _*_^1(x, y) == _*_^1(y, x) 10.61/5.52 _+_^1(x, y) == _+_^1(y, x) 10.61/5.52 D(x, y) == D(y, x) 10.61/5.52 GCD(x, y) == GCD(y, x) 10.61/5.52 10.61/5.52 We have to consider all minimal (P,E#,R,E)-chains 10.61/5.52 ---------------------------------------- 10.61/5.52 10.61/5.52 (26) 10.61/5.52 Obligation: 10.61/5.52 The TRS P consists of the following rules: 10.61/5.52 10.61/5.52 U12^1(tt, M, N) -> _*_^1(N, M) 10.61/5.52 _*_^1(s_(N), s_(M)) -> U11^1(tt, M, N) 10.61/5.52 U11^1(tt, M, N) -> U12^1(tt, M, N) 10.61/5.52 10.61/5.52 The TRS R consists of the following rules: 10.61/5.52 10.61/5.52 1 -> s_(0) 10.61/5.52 2 -> s_(s_(0)) 10.61/5.52 3 -> s_(s_(s_(0))) 10.61/5.52 4 -> s_(s_(s_(s_(0)))) 10.61/5.52 5 -> s_(s_(s_(s_(s_(0))))) 10.61/5.52 6 -> s_(s_(s_(s_(s_(s_(0)))))) 10.61/5.52 7 -> s_(s_(s_(s_(s_(s_(s_(0))))))) 10.61/5.52 U11(tt, M, N) -> U12(tt, M, N) 10.61/5.52 U12(tt, M, N) -> s_(_+_(N, _+_(M, _*_(N, M)))) 10.61/5.52 U21(tt, M, N) -> U22(tt, M, N) 10.61/5.52 U22(tt, M, N) -> s_(s_(_+_(N, M))) 10.61/5.52 U31(tt, M, N) -> U32(tt, M, N) 10.61/5.52 U32(tt, M, N) -> _>_(M, N) 10.61/5.52 U41(tt, M, N) -> U42(tt, M, N) 10.61/5.52 U42(tt, M, N) -> _>_(N, M) 10.61/5.52 U51(tt, M, N) -> U52(tt, M, N) 10.61/5.52 U52(tt, M, N) -> d(N, M) 10.61/5.52 U61(tt, M', N') -> U62(tt, M', N') 10.61/5.52 U62(tt, M', N') -> U63(equal(_>_(N', M'), true), M', N') 10.61/5.52 U63(tt, M', N') -> gcd(d(N', M'), M') 10.61/5.52 U71(tt, M', N) -> U72(tt, M', N) 10.61/5.52 U72(tt, M', N) -> U73(equal(_>_(M', N), true)) 10.61/5.52 U73(tt) -> 0 10.61/5.52 U81(tt, M', N) -> U82(tt, M', N) 10.61/5.52 U82(tt, M', N) -> U83(equal(_>_(N, M'), true), M', N) 10.61/5.52 U83(tt, M', N) -> s_(quot(d(N, M'), M')) 10.61/5.52 _*_(N, 0) -> 0 10.61/5.52 _*_(s_(N), s_(M)) -> U11(tt, M, N) 10.61/5.52 _+_(N, 0) -> N 10.61/5.52 _+_(s_(N), s_(M)) -> U21(tt, M, N) 10.61/5.52 _<_(N, M) -> U31(tt, M, N) 10.61/5.52 _>_(0, M) -> false 10.61/5.52 _>_(N', 0) -> true 10.61/5.52 _>_(s_(N), s_(M)) -> U41(tt, M, N) 10.61/5.52 d(0, N) -> N 10.61/5.52 d(s_(N), s_(M)) -> U51(tt, M, N) 10.61/5.52 equal(X, X) -> tt 10.61/5.52 gcd(0, N) -> 0 10.61/5.52 gcd(N', M') -> U61(tt, M', N') 10.61/5.52 gcd(N', N') -> N' 10.61/5.52 p_(s_(N)) -> N 10.61/5.52 quot(M', M') -> s_(0) 10.61/5.52 quot(N, M') -> U71(tt, M', N) 10.61/5.52 quot(N, M') -> U81(tt, M', N) 10.61/5.52 10.61/5.52 The set E consists of the following equations: 10.61/5.52 10.61/5.52 _*_(x, y) == _*_(y, x) 10.61/5.52 _+_(x, y) == _+_(y, x) 10.61/5.52 d(x, y) == d(y, x) 10.61/5.52 gcd(x, y) == gcd(y, x) 10.61/5.52 10.61/5.52 The set E# consists of the following equations: 10.61/5.52 10.61/5.52 _*_^1(x, y) == _*_^1(y, x) 10.61/5.52 _+_^1(x, y) == _+_^1(y, x) 10.61/5.52 D(x, y) == D(y, x) 10.61/5.52 GCD(x, y) == GCD(y, x) 10.61/5.52 10.61/5.52 We have to consider all minimal (P,E#,R,E)-chains 10.71/5.64 EOF