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