15.15/5.59 YES 15.15/5.60 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 15.15/5.60 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 15.15/5.60 15.15/5.60 15.15/5.60 Termination of the given ETRS could be proven: 15.15/5.60 15.15/5.60 (0) ETRS 15.15/5.60 (1) EquationalDependencyPairsProof [EQUIVALENT, 370 ms] 15.15/5.60 (2) EDP 15.15/5.60 (3) EDependencyGraphProof [EQUIVALENT, 0 ms] 15.15/5.60 (4) AND 15.15/5.60 (5) EDP 15.15/5.60 (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 15.15/5.60 (7) EDP 15.15/5.60 (8) EUsableRulesReductionPairsProof [EQUIVALENT, 7 ms] 15.15/5.60 (9) EDP 15.15/5.60 (10) EDPProblemToQDPProblemProof [EQUIVALENT, 0 ms] 15.15/5.60 (11) QDP 15.15/5.60 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 15.15/5.60 (13) YES 15.15/5.60 (14) EDP 15.15/5.60 (15) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 15.15/5.60 (16) EDP 15.15/5.60 (17) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 15.15/5.60 (18) EDP 15.15/5.60 (19) EDPProblemToQDPProblemProof [EQUIVALENT, 0 ms] 15.15/5.60 (20) QDP 15.15/5.60 (21) QDPSizeChangeProof [EQUIVALENT, 0 ms] 15.15/5.60 (22) YES 15.15/5.60 (23) EDP 15.15/5.60 (24) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 15.15/5.60 (25) EDP 15.15/5.60 (26) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 15.15/5.60 (27) EDP 15.15/5.60 (28) PisEmptyProof [EQUIVALENT, 0 ms] 15.15/5.60 (29) YES 15.15/5.60 (30) EDP 15.15/5.60 (31) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 15.15/5.60 (32) EDP 15.15/5.60 (33) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 15.15/5.60 (34) EDP 15.15/5.60 (35) EDPProblemToQDPProblemProof [EQUIVALENT, 0 ms] 15.15/5.60 (36) QDP 15.15/5.60 (37) QDPSizeChangeProof [EQUIVALENT, 0 ms] 15.15/5.60 (38) YES 15.15/5.60 (39) EDP 15.15/5.60 (40) ESharpUsableEquationsProof [EQUIVALENT, 201 ms] 15.15/5.60 (41) EDP 15.15/5.60 (42) EUsableRulesReductionPairsProof [EQUIVALENT, 237 ms] 15.15/5.60 (43) EDP 15.15/5.60 (44) ERuleRemovalProof [EQUIVALENT, 67 ms] 15.15/5.60 (45) EDP 15.15/5.60 (46) EDPPoloProof [EQUIVALENT, 13 ms] 15.15/5.60 (47) EDP 15.15/5.60 (48) PisEmptyProof [EQUIVALENT, 0 ms] 15.15/5.60 (49) YES 15.15/5.60 (50) EDP 15.15/5.60 (51) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 15.15/5.60 (52) EDP 15.15/5.60 (53) EDPPoloProof [EQUIVALENT, 257 ms] 15.15/5.60 (54) EDP 15.15/5.60 (55) EDPPoloProof [EQUIVALENT, 208 ms] 15.15/5.60 (56) EDP 15.15/5.60 (57) EDPPoloProof [EQUIVALENT, 184 ms] 15.15/5.60 (58) EDP 15.15/5.60 (59) EDPPoloProof [EQUIVALENT, 32 ms] 15.15/5.60 (60) EDP 15.15/5.60 (61) PisEmptyProof [EQUIVALENT, 0 ms] 15.15/5.60 (62) YES 15.15/5.60 15.15/5.60 15.15/5.60 ---------------------------------------- 15.15/5.60 15.15/5.60 (0) 15.15/5.60 Obligation: 15.15/5.60 Equational rewrite system: 15.15/5.60 The TRS R consists of the following rules: 15.15/5.60 15.15/5.60 0(S) -> S 15.15/5.60 plus(S, x) -> x 15.15/5.60 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.60 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.60 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.60 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.60 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.60 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.60 opp(S) -> S 15.15/5.60 opp(0(x)) -> 0(opp(x)) 15.15/5.60 opp(1(x)) -> j(opp(x)) 15.15/5.60 opp(j(x)) -> 1(opp(x)) 15.15/5.60 minus(x, y) -> plus(opp(y), x) 15.15/5.60 times(S, x) -> S 15.15/5.60 times(0(x), y) -> 0(times(x, y)) 15.15/5.60 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.60 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.60 sign(x) -> if_sign(x, S) 15.15/5.60 if_sign(S, x) -> x 15.15/5.60 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.60 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.60 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.60 abs(x) -> if_abs(x, x, S) 15.15/5.60 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.60 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.60 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.60 if_abs(S, x, S) -> S 15.15/5.60 if_abs(S, x, 1(S)) -> x 15.15/5.60 if_abs(S, x, j(S)) -> opp(x) 15.15/5.60 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.60 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.60 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.60 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.60 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.60 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.60 if_min(S, x, y, S) -> x 15.15/5.60 if_min(S, x, y, 1(S)) -> x 15.15/5.60 if_min(S, x, y, j(S)) -> y 15.15/5.60 15.15/5.60 The set E consists of the following equations: 15.15/5.60 15.15/5.60 plus(x, y) == plus(y, x) 15.15/5.60 times(x, y) == times(y, x) 15.15/5.60 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.60 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.60 15.15/5.60 15.15/5.60 ---------------------------------------- 15.15/5.60 15.15/5.60 (1) EquationalDependencyPairsProof (EQUIVALENT) 15.15/5.60 Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: 15.15/5.60 The TRS P consists of the following rules: 15.15/5.60 15.15/5.60 PLUS(0(x), 0(y)) -> 0^1(plus(x, y)) 15.15/5.60 PLUS(0(x), 0(y)) -> PLUS(x, y) 15.15/5.60 PLUS(0(x), 1(y)) -> PLUS(x, y) 15.15/5.60 PLUS(0(x), j(y)) -> PLUS(x, y) 15.15/5.60 PLUS(1(x), 1(y)) -> PLUS(1(S), plus(x, y)) 15.15/5.60 PLUS(1(x), 1(y)) -> PLUS(x, y) 15.15/5.60 PLUS(j(x), j(y)) -> PLUS(j(S), plus(x, y)) 15.15/5.60 PLUS(j(x), j(y)) -> PLUS(x, y) 15.15/5.60 PLUS(1(x), j(y)) -> 0^1(plus(x, y)) 15.15/5.60 PLUS(1(x), j(y)) -> PLUS(x, y) 15.15/5.60 OPP(0(x)) -> 0^1(opp(x)) 15.15/5.60 OPP(0(x)) -> OPP(x) 15.15/5.60 OPP(1(x)) -> OPP(x) 15.15/5.60 OPP(j(x)) -> OPP(x) 15.15/5.60 MINUS(x, y) -> PLUS(opp(y), x) 15.15/5.60 MINUS(x, y) -> OPP(y) 15.15/5.60 TIMES(0(x), y) -> 0^1(times(x, y)) 15.15/5.60 TIMES(0(x), y) -> TIMES(x, y) 15.15/5.60 TIMES(1(x), y) -> PLUS(0(times(x, y)), y) 15.15/5.60 TIMES(1(x), y) -> 0^1(times(x, y)) 15.15/5.60 TIMES(1(x), y) -> TIMES(x, y) 15.15/5.60 TIMES(j(x), y) -> MINUS(0(times(x, y)), y) 15.15/5.60 TIMES(j(x), y) -> 0^1(times(x, y)) 15.15/5.60 TIMES(j(x), y) -> TIMES(x, y) 15.15/5.60 SIGN(x) -> IF_SIGN(x, S) 15.15/5.60 IF_SIGN(0(x), y) -> IF_SIGN(x, y) 15.15/5.60 IF_SIGN(1(x), y) -> IF_SIGN(x, 1(S)) 15.15/5.60 IF_SIGN(j(x), y) -> IF_SIGN(x, j(S)) 15.15/5.60 ABS(x) -> IF_ABS(x, x, S) 15.15/5.60 IF_ABS(0(x), y, z) -> IF_ABS(x, y, z) 15.15/5.60 IF_ABS(1(x), y, z) -> IF_ABS(x, y, 1(S)) 15.15/5.60 IF_ABS(j(x), y, z) -> IF_ABS(x, y, j(S)) 15.15/5.60 IF_ABS(S, x, j(S)) -> OPP(x) 15.15/5.60 MIN(x, y) -> IF_MIN(minus(abs(y), abs(x)), x, y, S) 15.15/5.60 MIN(x, y) -> MINUS(abs(y), abs(x)) 15.15/5.60 MIN(x, y) -> ABS(y) 15.15/5.60 MIN(x, y) -> ABS(x) 15.15/5.60 MIN'(x, y) -> IF_MIN(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.60 MIN'(x, y) -> MINUS(abs(1(y)), abs(1(x))) 15.15/5.60 MIN'(x, y) -> ABS(1(y)) 15.15/5.60 MIN'(x, y) -> ABS(1(x)) 15.15/5.60 MIN''(x, y) -> IF_MIN(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.60 MIN''(x, y) -> MINUS(abs(j(y)), abs(j(x))) 15.15/5.60 MIN''(x, y) -> ABS(j(y)) 15.15/5.60 MIN''(x, y) -> ABS(j(x)) 15.15/5.60 IF_MIN(0(x), y, z, u) -> IF_MIN(x, y, z, u) 15.15/5.60 IF_MIN(1(x), y, z, u) -> IF_MIN(x, y, z, 1(S)) 15.15/5.60 IF_MIN(j(x), y, z, u) -> IF_MIN(x, y, z, j(S)) 15.15/5.60 PLUS(plus(0(x), 0(y)), ext) -> PLUS(0(plus(x, y)), ext) 15.15/5.60 PLUS(plus(0(x), 0(y)), ext) -> 0^1(plus(x, y)) 15.15/5.60 PLUS(plus(0(x), 0(y)), ext) -> PLUS(x, y) 15.15/5.60 PLUS(plus(0(x), 1(y)), ext) -> PLUS(1(plus(x, y)), ext) 15.15/5.60 PLUS(plus(0(x), 1(y)), ext) -> PLUS(x, y) 15.15/5.60 PLUS(plus(0(x), j(y)), ext) -> PLUS(j(plus(x, y)), ext) 15.15/5.60 PLUS(plus(0(x), j(y)), ext) -> PLUS(x, y) 15.15/5.60 PLUS(plus(1(x), 1(y)), ext) -> PLUS(j(plus(1(S), plus(x, y))), ext) 15.15/5.60 PLUS(plus(1(x), 1(y)), ext) -> PLUS(1(S), plus(x, y)) 15.15/5.60 PLUS(plus(1(x), 1(y)), ext) -> PLUS(x, y) 15.15/5.60 PLUS(plus(j(x), j(y)), ext) -> PLUS(1(plus(j(S), plus(x, y))), ext) 15.15/5.60 PLUS(plus(j(x), j(y)), ext) -> PLUS(j(S), plus(x, y)) 15.15/5.60 PLUS(plus(j(x), j(y)), ext) -> PLUS(x, y) 15.15/5.60 PLUS(plus(1(x), j(y)), ext) -> PLUS(0(plus(x, y)), ext) 15.15/5.60 PLUS(plus(1(x), j(y)), ext) -> 0^1(plus(x, y)) 15.15/5.60 PLUS(plus(1(x), j(y)), ext) -> PLUS(x, y) 15.15/5.60 TIMES(times(S, x), ext) -> TIMES(S, ext) 15.15/5.60 TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) 15.15/5.60 TIMES(times(0(x), y), ext) -> 0^1(times(x, y)) 15.15/5.60 TIMES(times(0(x), y), ext) -> TIMES(x, y) 15.15/5.60 TIMES(times(1(x), y), ext) -> TIMES(plus(0(times(x, y)), y), ext) 15.15/5.60 TIMES(times(1(x), y), ext) -> PLUS(0(times(x, y)), y) 15.15/5.60 TIMES(times(1(x), y), ext) -> 0^1(times(x, y)) 15.15/5.60 TIMES(times(1(x), y), ext) -> TIMES(x, y) 15.15/5.60 TIMES(times(j(x), y), ext) -> TIMES(minus(0(times(x, y)), y), ext) 15.15/5.60 TIMES(times(j(x), y), ext) -> MINUS(0(times(x, y)), y) 15.15/5.60 TIMES(times(j(x), y), ext) -> 0^1(times(x, y)) 15.15/5.60 TIMES(times(j(x), y), ext) -> TIMES(x, y) 15.15/5.60 15.15/5.60 The TRS R consists of the following rules: 15.15/5.60 15.15/5.60 0(S) -> S 15.15/5.60 plus(S, x) -> x 15.15/5.60 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.60 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.60 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.60 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.60 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.60 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.60 opp(S) -> S 15.15/5.60 opp(0(x)) -> 0(opp(x)) 15.15/5.60 opp(1(x)) -> j(opp(x)) 15.15/5.60 opp(j(x)) -> 1(opp(x)) 15.15/5.60 minus(x, y) -> plus(opp(y), x) 15.15/5.60 times(S, x) -> S 15.15/5.60 times(0(x), y) -> 0(times(x, y)) 15.15/5.60 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.60 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.60 sign(x) -> if_sign(x, S) 15.15/5.60 if_sign(S, x) -> x 15.15/5.60 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.60 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.60 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.60 abs(x) -> if_abs(x, x, S) 15.15/5.60 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.60 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.60 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.60 if_abs(S, x, S) -> S 15.15/5.60 if_abs(S, x, 1(S)) -> x 15.15/5.60 if_abs(S, x, j(S)) -> opp(x) 15.15/5.60 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.60 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.60 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.60 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.60 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.60 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.60 if_min(S, x, y, S) -> x 15.15/5.60 if_min(S, x, y, 1(S)) -> x 15.15/5.60 if_min(S, x, y, j(S)) -> y 15.15/5.60 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.60 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.60 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.60 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.60 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.60 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.60 times(times(S, x), ext) -> times(S, ext) 15.15/5.60 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.60 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.60 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.60 15.15/5.60 The set E consists of the following equations: 15.15/5.60 15.15/5.60 plus(x, y) == plus(y, x) 15.15/5.60 times(x, y) == times(y, x) 15.15/5.60 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.60 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.60 15.15/5.60 The set E# consists of the following equations: 15.15/5.60 15.15/5.60 PLUS(x, y) == PLUS(y, x) 15.15/5.60 TIMES(x, y) == TIMES(y, x) 15.15/5.60 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.60 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.60 15.15/5.60 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.60 15.15/5.60 ---------------------------------------- 15.15/5.60 15.15/5.60 (2) 15.15/5.60 Obligation: 15.15/5.60 The TRS P consists of the following rules: 15.15/5.60 15.15/5.60 PLUS(0(x), 0(y)) -> 0^1(plus(x, y)) 15.15/5.60 PLUS(0(x), 0(y)) -> PLUS(x, y) 15.15/5.60 PLUS(0(x), 1(y)) -> PLUS(x, y) 15.15/5.60 PLUS(0(x), j(y)) -> PLUS(x, y) 15.15/5.60 PLUS(1(x), 1(y)) -> PLUS(1(S), plus(x, y)) 15.15/5.60 PLUS(1(x), 1(y)) -> PLUS(x, y) 15.15/5.60 PLUS(j(x), j(y)) -> PLUS(j(S), plus(x, y)) 15.15/5.60 PLUS(j(x), j(y)) -> PLUS(x, y) 15.15/5.60 PLUS(1(x), j(y)) -> 0^1(plus(x, y)) 15.15/5.60 PLUS(1(x), j(y)) -> PLUS(x, y) 15.15/5.60 OPP(0(x)) -> 0^1(opp(x)) 15.15/5.60 OPP(0(x)) -> OPP(x) 15.15/5.60 OPP(1(x)) -> OPP(x) 15.15/5.60 OPP(j(x)) -> OPP(x) 15.15/5.60 MINUS(x, y) -> PLUS(opp(y), x) 15.15/5.60 MINUS(x, y) -> OPP(y) 15.15/5.60 TIMES(0(x), y) -> 0^1(times(x, y)) 15.15/5.60 TIMES(0(x), y) -> TIMES(x, y) 15.15/5.60 TIMES(1(x), y) -> PLUS(0(times(x, y)), y) 15.15/5.60 TIMES(1(x), y) -> 0^1(times(x, y)) 15.15/5.60 TIMES(1(x), y) -> TIMES(x, y) 15.15/5.60 TIMES(j(x), y) -> MINUS(0(times(x, y)), y) 15.15/5.60 TIMES(j(x), y) -> 0^1(times(x, y)) 15.15/5.60 TIMES(j(x), y) -> TIMES(x, y) 15.15/5.60 SIGN(x) -> IF_SIGN(x, S) 15.15/5.60 IF_SIGN(0(x), y) -> IF_SIGN(x, y) 15.15/5.60 IF_SIGN(1(x), y) -> IF_SIGN(x, 1(S)) 15.15/5.60 IF_SIGN(j(x), y) -> IF_SIGN(x, j(S)) 15.15/5.60 ABS(x) -> IF_ABS(x, x, S) 15.15/5.60 IF_ABS(0(x), y, z) -> IF_ABS(x, y, z) 15.15/5.60 IF_ABS(1(x), y, z) -> IF_ABS(x, y, 1(S)) 15.15/5.60 IF_ABS(j(x), y, z) -> IF_ABS(x, y, j(S)) 15.15/5.60 IF_ABS(S, x, j(S)) -> OPP(x) 15.15/5.60 MIN(x, y) -> IF_MIN(minus(abs(y), abs(x)), x, y, S) 15.15/5.60 MIN(x, y) -> MINUS(abs(y), abs(x)) 15.15/5.60 MIN(x, y) -> ABS(y) 15.15/5.60 MIN(x, y) -> ABS(x) 15.15/5.60 MIN'(x, y) -> IF_MIN(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.60 MIN'(x, y) -> MINUS(abs(1(y)), abs(1(x))) 15.15/5.60 MIN'(x, y) -> ABS(1(y)) 15.15/5.60 MIN'(x, y) -> ABS(1(x)) 15.15/5.60 MIN''(x, y) -> IF_MIN(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.60 MIN''(x, y) -> MINUS(abs(j(y)), abs(j(x))) 15.15/5.60 MIN''(x, y) -> ABS(j(y)) 15.15/5.60 MIN''(x, y) -> ABS(j(x)) 15.15/5.60 IF_MIN(0(x), y, z, u) -> IF_MIN(x, y, z, u) 15.15/5.60 IF_MIN(1(x), y, z, u) -> IF_MIN(x, y, z, 1(S)) 15.15/5.60 IF_MIN(j(x), y, z, u) -> IF_MIN(x, y, z, j(S)) 15.15/5.60 PLUS(plus(0(x), 0(y)), ext) -> PLUS(0(plus(x, y)), ext) 15.15/5.60 PLUS(plus(0(x), 0(y)), ext) -> 0^1(plus(x, y)) 15.15/5.60 PLUS(plus(0(x), 0(y)), ext) -> PLUS(x, y) 15.15/5.60 PLUS(plus(0(x), 1(y)), ext) -> PLUS(1(plus(x, y)), ext) 15.15/5.60 PLUS(plus(0(x), 1(y)), ext) -> PLUS(x, y) 15.15/5.60 PLUS(plus(0(x), j(y)), ext) -> PLUS(j(plus(x, y)), ext) 15.15/5.60 PLUS(plus(0(x), j(y)), ext) -> PLUS(x, y) 15.15/5.60 PLUS(plus(1(x), 1(y)), ext) -> PLUS(j(plus(1(S), plus(x, y))), ext) 15.15/5.60 PLUS(plus(1(x), 1(y)), ext) -> PLUS(1(S), plus(x, y)) 15.15/5.60 PLUS(plus(1(x), 1(y)), ext) -> PLUS(x, y) 15.15/5.60 PLUS(plus(j(x), j(y)), ext) -> PLUS(1(plus(j(S), plus(x, y))), ext) 15.15/5.60 PLUS(plus(j(x), j(y)), ext) -> PLUS(j(S), plus(x, y)) 15.15/5.60 PLUS(plus(j(x), j(y)), ext) -> PLUS(x, y) 15.15/5.60 PLUS(plus(1(x), j(y)), ext) -> PLUS(0(plus(x, y)), ext) 15.15/5.60 PLUS(plus(1(x), j(y)), ext) -> 0^1(plus(x, y)) 15.15/5.60 PLUS(plus(1(x), j(y)), ext) -> PLUS(x, y) 15.15/5.60 TIMES(times(S, x), ext) -> TIMES(S, ext) 15.15/5.60 TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) 15.15/5.60 TIMES(times(0(x), y), ext) -> 0^1(times(x, y)) 15.15/5.60 TIMES(times(0(x), y), ext) -> TIMES(x, y) 15.15/5.60 TIMES(times(1(x), y), ext) -> TIMES(plus(0(times(x, y)), y), ext) 15.15/5.60 TIMES(times(1(x), y), ext) -> PLUS(0(times(x, y)), y) 15.15/5.60 TIMES(times(1(x), y), ext) -> 0^1(times(x, y)) 15.15/5.60 TIMES(times(1(x), y), ext) -> TIMES(x, y) 15.15/5.60 TIMES(times(j(x), y), ext) -> TIMES(minus(0(times(x, y)), y), ext) 15.15/5.60 TIMES(times(j(x), y), ext) -> MINUS(0(times(x, y)), y) 15.15/5.60 TIMES(times(j(x), y), ext) -> 0^1(times(x, y)) 15.15/5.60 TIMES(times(j(x), y), ext) -> TIMES(x, y) 15.15/5.60 15.15/5.60 The TRS R consists of the following rules: 15.15/5.60 15.15/5.60 0(S) -> S 15.15/5.60 plus(S, x) -> x 15.15/5.60 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.60 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.60 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.60 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.60 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.60 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.60 opp(S) -> S 15.15/5.60 opp(0(x)) -> 0(opp(x)) 15.15/5.60 opp(1(x)) -> j(opp(x)) 15.15/5.60 opp(j(x)) -> 1(opp(x)) 15.15/5.60 minus(x, y) -> plus(opp(y), x) 15.15/5.60 times(S, x) -> S 15.15/5.60 times(0(x), y) -> 0(times(x, y)) 15.15/5.60 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.60 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.60 sign(x) -> if_sign(x, S) 15.15/5.60 if_sign(S, x) -> x 15.15/5.60 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.60 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.60 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.60 abs(x) -> if_abs(x, x, S) 15.15/5.60 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.60 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.60 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.60 if_abs(S, x, S) -> S 15.15/5.60 if_abs(S, x, 1(S)) -> x 15.15/5.60 if_abs(S, x, j(S)) -> opp(x) 15.15/5.60 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.60 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.60 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.60 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.60 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.60 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.60 if_min(S, x, y, S) -> x 15.15/5.60 if_min(S, x, y, 1(S)) -> x 15.15/5.60 if_min(S, x, y, j(S)) -> y 15.15/5.60 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.60 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.60 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.60 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.60 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.60 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.60 times(times(S, x), ext) -> times(S, ext) 15.15/5.60 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.60 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.60 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.60 15.15/5.60 The set E consists of the following equations: 15.15/5.60 15.15/5.60 plus(x, y) == plus(y, x) 15.15/5.60 times(x, y) == times(y, x) 15.15/5.60 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.60 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.60 15.15/5.60 The set E# consists of the following equations: 15.15/5.60 15.15/5.60 PLUS(x, y) == PLUS(y, x) 15.15/5.60 TIMES(x, y) == TIMES(y, x) 15.15/5.60 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.60 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.60 15.15/5.60 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.60 ---------------------------------------- 15.15/5.60 15.15/5.60 (3) EDependencyGraphProof (EQUIVALENT) 15.15/5.60 The approximation of the Equational Dependency Graph [DA_STEIN] contains 6 SCCs with 32 less nodes. 15.15/5.60 ---------------------------------------- 15.15/5.60 15.15/5.60 (4) 15.15/5.60 Complex Obligation (AND) 15.15/5.60 15.15/5.60 ---------------------------------------- 15.15/5.60 15.15/5.60 (5) 15.15/5.60 Obligation: 15.15/5.60 The TRS P consists of the following rules: 15.15/5.60 15.15/5.60 IF_MIN(1(x), y, z, u) -> IF_MIN(x, y, z, 1(S)) 15.15/5.60 IF_MIN(j(x), y, z, u) -> IF_MIN(x, y, z, j(S)) 15.15/5.60 IF_MIN(0(x), y, z, u) -> IF_MIN(x, y, z, u) 15.15/5.62 15.15/5.62 The TRS R consists of the following rules: 15.15/5.62 15.15/5.62 0(S) -> S 15.15/5.62 plus(S, x) -> x 15.15/5.62 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.62 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.62 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.62 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.62 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.62 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.62 opp(S) -> S 15.15/5.62 opp(0(x)) -> 0(opp(x)) 15.15/5.62 opp(1(x)) -> j(opp(x)) 15.15/5.62 opp(j(x)) -> 1(opp(x)) 15.15/5.62 minus(x, y) -> plus(opp(y), x) 15.15/5.62 times(S, x) -> S 15.15/5.62 times(0(x), y) -> 0(times(x, y)) 15.15/5.62 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.62 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.62 sign(x) -> if_sign(x, S) 15.15/5.62 if_sign(S, x) -> x 15.15/5.62 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.62 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.62 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.62 abs(x) -> if_abs(x, x, S) 15.15/5.62 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.62 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.62 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.62 if_abs(S, x, S) -> S 15.15/5.62 if_abs(S, x, 1(S)) -> x 15.15/5.62 if_abs(S, x, j(S)) -> opp(x) 15.15/5.62 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.62 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.62 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.62 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.62 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.62 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.62 if_min(S, x, y, S) -> x 15.15/5.62 if_min(S, x, y, 1(S)) -> x 15.15/5.62 if_min(S, x, y, j(S)) -> y 15.15/5.62 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.62 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.62 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.62 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 times(times(S, x), ext) -> times(S, ext) 15.15/5.62 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.62 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.62 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.62 15.15/5.62 The set E consists of the following equations: 15.15/5.62 15.15/5.62 plus(x, y) == plus(y, x) 15.15/5.62 times(x, y) == times(y, x) 15.15/5.62 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.62 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.62 15.15/5.62 The set E# consists of the following equations: 15.15/5.62 15.15/5.62 PLUS(x, y) == PLUS(y, x) 15.15/5.62 TIMES(x, y) == TIMES(y, x) 15.15/5.62 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.62 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.62 15.15/5.62 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (6) ESharpUsableEquationsProof (EQUIVALENT) 15.15/5.62 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 15.15/5.62 PLUS(x, y) == PLUS(y, x) 15.15/5.62 TIMES(x, y) == TIMES(y, x) 15.15/5.62 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.62 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.62 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (7) 15.15/5.62 Obligation: 15.15/5.62 The TRS P consists of the following rules: 15.15/5.62 15.15/5.62 IF_MIN(1(x), y, z, u) -> IF_MIN(x, y, z, 1(S)) 15.15/5.62 IF_MIN(j(x), y, z, u) -> IF_MIN(x, y, z, j(S)) 15.15/5.62 IF_MIN(0(x), y, z, u) -> IF_MIN(x, y, z, u) 15.15/5.62 15.15/5.62 The TRS R consists of the following rules: 15.15/5.62 15.15/5.62 0(S) -> S 15.15/5.62 plus(S, x) -> x 15.15/5.62 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.62 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.62 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.62 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.62 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.62 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.62 opp(S) -> S 15.15/5.62 opp(0(x)) -> 0(opp(x)) 15.15/5.62 opp(1(x)) -> j(opp(x)) 15.15/5.62 opp(j(x)) -> 1(opp(x)) 15.15/5.62 minus(x, y) -> plus(opp(y), x) 15.15/5.62 times(S, x) -> S 15.15/5.62 times(0(x), y) -> 0(times(x, y)) 15.15/5.62 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.62 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.62 sign(x) -> if_sign(x, S) 15.15/5.62 if_sign(S, x) -> x 15.15/5.62 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.62 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.62 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.62 abs(x) -> if_abs(x, x, S) 15.15/5.62 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.62 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.62 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.62 if_abs(S, x, S) -> S 15.15/5.62 if_abs(S, x, 1(S)) -> x 15.15/5.62 if_abs(S, x, j(S)) -> opp(x) 15.15/5.62 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.62 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.62 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.62 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.62 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.62 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.62 if_min(S, x, y, S) -> x 15.15/5.62 if_min(S, x, y, 1(S)) -> x 15.15/5.62 if_min(S, x, y, j(S)) -> y 15.15/5.62 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.62 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.62 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.62 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 times(times(S, x), ext) -> times(S, ext) 15.15/5.62 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.62 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.62 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.62 15.15/5.62 The set E consists of the following equations: 15.15/5.62 15.15/5.62 plus(x, y) == plus(y, x) 15.15/5.62 times(x, y) == times(y, x) 15.15/5.62 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.62 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.62 15.15/5.62 E# is empty. 15.15/5.62 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (8) EUsableRulesReductionPairsProof (EQUIVALENT) 15.15/5.62 By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 15.15/5.62 15.15/5.62 The following dependency pairs can be deleted: 15.15/5.62 15.15/5.62 IF_MIN(0(x), y, z, u) -> IF_MIN(x, y, z, u) 15.15/5.62 The following rules are removed from R: 15.15/5.62 15.15/5.62 0(S) -> S 15.15/5.62 plus(S, x) -> x 15.15/5.62 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.62 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.62 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.62 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.62 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.62 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.62 opp(S) -> S 15.15/5.62 opp(0(x)) -> 0(opp(x)) 15.15/5.62 opp(1(x)) -> j(opp(x)) 15.15/5.62 opp(j(x)) -> 1(opp(x)) 15.15/5.62 minus(x, y) -> plus(opp(y), x) 15.15/5.62 times(S, x) -> S 15.15/5.62 times(0(x), y) -> 0(times(x, y)) 15.15/5.62 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.62 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.62 sign(x) -> if_sign(x, S) 15.15/5.62 if_sign(S, x) -> x 15.15/5.62 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.62 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.62 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.62 abs(x) -> if_abs(x, x, S) 15.15/5.62 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.62 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.62 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.62 if_abs(S, x, S) -> S 15.15/5.62 if_abs(S, x, 1(S)) -> x 15.15/5.62 if_abs(S, x, j(S)) -> opp(x) 15.15/5.62 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.62 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.62 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.62 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.62 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.62 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.62 if_min(S, x, y, S) -> x 15.15/5.62 if_min(S, x, y, 1(S)) -> x 15.15/5.62 if_min(S, x, y, j(S)) -> y 15.15/5.62 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.62 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.62 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.62 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 times(times(S, x), ext) -> times(S, ext) 15.15/5.62 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.62 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.62 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.62 The following equations are removed from E: 15.15/5.62 15.15/5.62 plus(x, y) == plus(y, x) 15.15/5.62 times(x, y) == times(y, x) 15.15/5.62 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.62 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.62 Used ordering: POLO with Polynomial interpretation [POLO]: 15.15/5.62 15.15/5.62 POL(0(x_1)) = 3*x_1 15.15/5.62 POL(1(x_1)) = x_1 15.15/5.62 POL(IF_MIN(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 15.15/5.62 POL(S) = 0 15.15/5.62 POL(j(x_1)) = x_1 15.15/5.62 15.15/5.62 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (9) 15.15/5.62 Obligation: 15.15/5.62 The TRS P consists of the following rules: 15.15/5.62 15.15/5.62 IF_MIN(1(x), y, z, u) -> IF_MIN(x, y, z, 1(S)) 15.15/5.62 IF_MIN(j(x), y, z, u) -> IF_MIN(x, y, z, j(S)) 15.15/5.62 15.15/5.62 R is empty. 15.15/5.62 E is empty. 15.15/5.62 E# is empty. 15.15/5.62 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (10) EDPProblemToQDPProblemProof (EQUIVALENT) 15.15/5.62 The EDP problem does not contain equations anymore, so we can transform it with the EDP to QDP problem processor [DA_STEIN] into a QDP problem. 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (11) 15.15/5.62 Obligation: 15.15/5.62 Q DP problem: 15.15/5.62 The TRS P consists of the following rules: 15.15/5.62 15.15/5.62 IF_MIN(1(x), y, z, u) -> IF_MIN(x, y, z, 1(S)) 15.15/5.62 IF_MIN(j(x), y, z, u) -> IF_MIN(x, y, z, j(S)) 15.15/5.62 15.15/5.62 R is empty. 15.15/5.62 Q is empty. 15.15/5.62 We have to consider all minimal (P,Q,R)-chains. 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (12) QDPSizeChangeProof (EQUIVALENT) 15.15/5.62 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 15.15/5.62 15.15/5.62 From the DPs we obtained the following set of size-change graphs: 15.15/5.62 *IF_MIN(1(x), y, z, u) -> IF_MIN(x, y, z, 1(S)) 15.15/5.62 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 15.15/5.62 15.15/5.62 15.15/5.62 *IF_MIN(j(x), y, z, u) -> IF_MIN(x, y, z, j(S)) 15.15/5.62 The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 15.15/5.62 15.15/5.62 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (13) 15.15/5.62 YES 15.15/5.62 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (14) 15.15/5.62 Obligation: 15.15/5.62 The TRS P consists of the following rules: 15.15/5.62 15.15/5.62 IF_SIGN(0(x), y) -> IF_SIGN(x, y) 15.15/5.62 IF_SIGN(1(x), y) -> IF_SIGN(x, 1(S)) 15.15/5.62 IF_SIGN(j(x), y) -> IF_SIGN(x, j(S)) 15.15/5.62 15.15/5.62 The TRS R consists of the following rules: 15.15/5.62 15.15/5.62 0(S) -> S 15.15/5.62 plus(S, x) -> x 15.15/5.62 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.62 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.62 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.62 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.62 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.62 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.62 opp(S) -> S 15.15/5.62 opp(0(x)) -> 0(opp(x)) 15.15/5.62 opp(1(x)) -> j(opp(x)) 15.15/5.62 opp(j(x)) -> 1(opp(x)) 15.15/5.62 minus(x, y) -> plus(opp(y), x) 15.15/5.62 times(S, x) -> S 15.15/5.62 times(0(x), y) -> 0(times(x, y)) 15.15/5.62 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.62 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.62 sign(x) -> if_sign(x, S) 15.15/5.62 if_sign(S, x) -> x 15.15/5.62 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.62 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.62 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.62 abs(x) -> if_abs(x, x, S) 15.15/5.62 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.62 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.62 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.62 if_abs(S, x, S) -> S 15.15/5.62 if_abs(S, x, 1(S)) -> x 15.15/5.62 if_abs(S, x, j(S)) -> opp(x) 15.15/5.62 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.62 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.62 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.62 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.62 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.62 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.62 if_min(S, x, y, S) -> x 15.15/5.62 if_min(S, x, y, 1(S)) -> x 15.15/5.62 if_min(S, x, y, j(S)) -> y 15.15/5.62 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.62 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.62 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.62 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 times(times(S, x), ext) -> times(S, ext) 15.15/5.62 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.62 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.62 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.62 15.15/5.62 The set E consists of the following equations: 15.15/5.62 15.15/5.62 plus(x, y) == plus(y, x) 15.15/5.62 times(x, y) == times(y, x) 15.15/5.62 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.62 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.62 15.15/5.62 The set E# consists of the following equations: 15.15/5.62 15.15/5.62 PLUS(x, y) == PLUS(y, x) 15.15/5.62 TIMES(x, y) == TIMES(y, x) 15.15/5.62 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.62 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.62 15.15/5.62 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (15) ESharpUsableEquationsProof (EQUIVALENT) 15.15/5.62 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 15.15/5.62 PLUS(x, y) == PLUS(y, x) 15.15/5.62 TIMES(x, y) == TIMES(y, x) 15.15/5.62 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.62 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.62 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (16) 15.15/5.62 Obligation: 15.15/5.62 The TRS P consists of the following rules: 15.15/5.62 15.15/5.62 IF_SIGN(0(x), y) -> IF_SIGN(x, y) 15.15/5.62 IF_SIGN(1(x), y) -> IF_SIGN(x, 1(S)) 15.15/5.62 IF_SIGN(j(x), y) -> IF_SIGN(x, j(S)) 15.15/5.62 15.15/5.62 The TRS R consists of the following rules: 15.15/5.62 15.15/5.62 0(S) -> S 15.15/5.62 plus(S, x) -> x 15.15/5.62 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.62 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.62 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.62 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.62 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.62 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.62 opp(S) -> S 15.15/5.62 opp(0(x)) -> 0(opp(x)) 15.15/5.62 opp(1(x)) -> j(opp(x)) 15.15/5.62 opp(j(x)) -> 1(opp(x)) 15.15/5.62 minus(x, y) -> plus(opp(y), x) 15.15/5.62 times(S, x) -> S 15.15/5.62 times(0(x), y) -> 0(times(x, y)) 15.15/5.62 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.62 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.62 sign(x) -> if_sign(x, S) 15.15/5.62 if_sign(S, x) -> x 15.15/5.62 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.62 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.62 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.62 abs(x) -> if_abs(x, x, S) 15.15/5.62 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.62 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.62 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.62 if_abs(S, x, S) -> S 15.15/5.62 if_abs(S, x, 1(S)) -> x 15.15/5.62 if_abs(S, x, j(S)) -> opp(x) 15.15/5.62 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.62 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.62 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.62 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.62 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.62 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.62 if_min(S, x, y, S) -> x 15.15/5.62 if_min(S, x, y, 1(S)) -> x 15.15/5.62 if_min(S, x, y, j(S)) -> y 15.15/5.62 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.62 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.62 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.62 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 times(times(S, x), ext) -> times(S, ext) 15.15/5.62 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.62 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.62 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.62 15.15/5.62 The set E consists of the following equations: 15.15/5.62 15.15/5.62 plus(x, y) == plus(y, x) 15.15/5.62 times(x, y) == times(y, x) 15.15/5.62 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.62 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.62 15.15/5.62 E# is empty. 15.15/5.62 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (17) EUsableRulesReductionPairsProof (EQUIVALENT) 15.15/5.62 By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 15.15/5.62 15.15/5.62 The following dependency pairs can be deleted: 15.15/5.62 15.15/5.62 IF_SIGN(0(x), y) -> IF_SIGN(x, y) 15.15/5.62 The following rules are removed from R: 15.15/5.62 15.15/5.62 0(S) -> S 15.15/5.62 plus(S, x) -> x 15.15/5.62 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.62 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.62 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.62 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.62 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.62 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.62 opp(S) -> S 15.15/5.62 opp(0(x)) -> 0(opp(x)) 15.15/5.62 opp(1(x)) -> j(opp(x)) 15.15/5.62 opp(j(x)) -> 1(opp(x)) 15.15/5.62 minus(x, y) -> plus(opp(y), x) 15.15/5.62 times(S, x) -> S 15.15/5.62 times(0(x), y) -> 0(times(x, y)) 15.15/5.62 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.62 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.62 sign(x) -> if_sign(x, S) 15.15/5.62 if_sign(S, x) -> x 15.15/5.62 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.62 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.62 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.62 abs(x) -> if_abs(x, x, S) 15.15/5.62 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.62 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.62 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.62 if_abs(S, x, S) -> S 15.15/5.62 if_abs(S, x, 1(S)) -> x 15.15/5.62 if_abs(S, x, j(S)) -> opp(x) 15.15/5.62 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.62 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.62 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.62 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.62 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.62 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.62 if_min(S, x, y, S) -> x 15.15/5.62 if_min(S, x, y, 1(S)) -> x 15.15/5.62 if_min(S, x, y, j(S)) -> y 15.15/5.62 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.62 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.62 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.62 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 times(times(S, x), ext) -> times(S, ext) 15.15/5.62 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.62 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.62 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.62 The following equations are removed from E: 15.15/5.62 15.15/5.62 plus(x, y) == plus(y, x) 15.15/5.62 times(x, y) == times(y, x) 15.15/5.62 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.62 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.62 Used ordering: POLO with Polynomial interpretation [POLO]: 15.15/5.62 15.15/5.62 POL(0(x_1)) = 3*x_1 15.15/5.62 POL(1(x_1)) = x_1 15.15/5.62 POL(IF_SIGN(x_1, x_2)) = x_1 + x_2 15.15/5.62 POL(S) = 0 15.15/5.62 POL(j(x_1)) = x_1 15.15/5.62 15.15/5.62 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (18) 15.15/5.62 Obligation: 15.15/5.62 The TRS P consists of the following rules: 15.15/5.62 15.15/5.62 IF_SIGN(1(x), y) -> IF_SIGN(x, 1(S)) 15.15/5.62 IF_SIGN(j(x), y) -> IF_SIGN(x, j(S)) 15.15/5.62 15.15/5.62 R is empty. 15.15/5.62 E is empty. 15.15/5.62 E# is empty. 15.15/5.62 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (19) EDPProblemToQDPProblemProof (EQUIVALENT) 15.15/5.62 The EDP problem does not contain equations anymore, so we can transform it with the EDP to QDP problem processor [DA_STEIN] into a QDP problem. 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (20) 15.15/5.62 Obligation: 15.15/5.62 Q DP problem: 15.15/5.62 The TRS P consists of the following rules: 15.15/5.62 15.15/5.62 IF_SIGN(1(x), y) -> IF_SIGN(x, 1(S)) 15.15/5.62 IF_SIGN(j(x), y) -> IF_SIGN(x, j(S)) 15.15/5.62 15.15/5.62 R is empty. 15.15/5.62 Q is empty. 15.15/5.62 We have to consider all minimal (P,Q,R)-chains. 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (21) QDPSizeChangeProof (EQUIVALENT) 15.15/5.62 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 15.15/5.62 15.15/5.62 From the DPs we obtained the following set of size-change graphs: 15.15/5.62 *IF_SIGN(1(x), y) -> IF_SIGN(x, 1(S)) 15.15/5.62 The graph contains the following edges 1 > 1 15.15/5.62 15.15/5.62 15.15/5.62 *IF_SIGN(j(x), y) -> IF_SIGN(x, j(S)) 15.15/5.62 The graph contains the following edges 1 > 1 15.15/5.62 15.15/5.62 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (22) 15.15/5.62 YES 15.15/5.62 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (23) 15.15/5.62 Obligation: 15.15/5.62 The TRS P consists of the following rules: 15.15/5.62 15.15/5.62 OPP(j(x)) -> OPP(x) 15.15/5.62 OPP(0(x)) -> OPP(x) 15.15/5.62 OPP(1(x)) -> OPP(x) 15.15/5.62 15.15/5.62 The TRS R consists of the following rules: 15.15/5.62 15.15/5.62 0(S) -> S 15.15/5.62 plus(S, x) -> x 15.15/5.62 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.62 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.62 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.62 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.62 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.62 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.62 opp(S) -> S 15.15/5.62 opp(0(x)) -> 0(opp(x)) 15.15/5.62 opp(1(x)) -> j(opp(x)) 15.15/5.62 opp(j(x)) -> 1(opp(x)) 15.15/5.62 minus(x, y) -> plus(opp(y), x) 15.15/5.62 times(S, x) -> S 15.15/5.62 times(0(x), y) -> 0(times(x, y)) 15.15/5.62 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.62 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.62 sign(x) -> if_sign(x, S) 15.15/5.62 if_sign(S, x) -> x 15.15/5.62 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.62 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.62 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.62 abs(x) -> if_abs(x, x, S) 15.15/5.62 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.62 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.62 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.62 if_abs(S, x, S) -> S 15.15/5.62 if_abs(S, x, 1(S)) -> x 15.15/5.62 if_abs(S, x, j(S)) -> opp(x) 15.15/5.62 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.62 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.62 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.62 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.62 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.62 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.62 if_min(S, x, y, S) -> x 15.15/5.62 if_min(S, x, y, 1(S)) -> x 15.15/5.62 if_min(S, x, y, j(S)) -> y 15.15/5.62 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.62 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.62 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.62 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 times(times(S, x), ext) -> times(S, ext) 15.15/5.62 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.62 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.62 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.62 15.15/5.62 The set E consists of the following equations: 15.15/5.62 15.15/5.62 plus(x, y) == plus(y, x) 15.15/5.62 times(x, y) == times(y, x) 15.15/5.62 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.62 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.62 15.15/5.62 The set E# consists of the following equations: 15.15/5.62 15.15/5.62 PLUS(x, y) == PLUS(y, x) 15.15/5.62 TIMES(x, y) == TIMES(y, x) 15.15/5.62 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.62 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.62 15.15/5.62 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (24) ESharpUsableEquationsProof (EQUIVALENT) 15.15/5.62 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 15.15/5.62 PLUS(x, y) == PLUS(y, x) 15.15/5.62 TIMES(x, y) == TIMES(y, x) 15.15/5.62 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.62 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.62 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (25) 15.15/5.62 Obligation: 15.15/5.62 The TRS P consists of the following rules: 15.15/5.62 15.15/5.62 OPP(j(x)) -> OPP(x) 15.15/5.62 OPP(0(x)) -> OPP(x) 15.15/5.62 OPP(1(x)) -> OPP(x) 15.15/5.62 15.15/5.62 The TRS R consists of the following rules: 15.15/5.62 15.15/5.62 0(S) -> S 15.15/5.62 plus(S, x) -> x 15.15/5.62 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.62 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.62 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.62 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.62 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.62 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.62 opp(S) -> S 15.15/5.62 opp(0(x)) -> 0(opp(x)) 15.15/5.62 opp(1(x)) -> j(opp(x)) 15.15/5.62 opp(j(x)) -> 1(opp(x)) 15.15/5.62 minus(x, y) -> plus(opp(y), x) 15.15/5.62 times(S, x) -> S 15.15/5.62 times(0(x), y) -> 0(times(x, y)) 15.15/5.62 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.62 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.62 sign(x) -> if_sign(x, S) 15.15/5.62 if_sign(S, x) -> x 15.15/5.62 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.62 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.62 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.62 abs(x) -> if_abs(x, x, S) 15.15/5.62 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.62 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.62 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.62 if_abs(S, x, S) -> S 15.15/5.62 if_abs(S, x, 1(S)) -> x 15.15/5.62 if_abs(S, x, j(S)) -> opp(x) 15.15/5.62 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.62 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.62 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.62 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.62 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.62 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.62 if_min(S, x, y, S) -> x 15.15/5.62 if_min(S, x, y, 1(S)) -> x 15.15/5.62 if_min(S, x, y, j(S)) -> y 15.15/5.62 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.62 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.62 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.62 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 times(times(S, x), ext) -> times(S, ext) 15.15/5.62 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.62 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.62 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.62 15.15/5.62 The set E consists of the following equations: 15.15/5.62 15.15/5.62 plus(x, y) == plus(y, x) 15.15/5.62 times(x, y) == times(y, x) 15.15/5.62 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.62 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.62 15.15/5.62 E# is empty. 15.15/5.62 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (26) EUsableRulesReductionPairsProof (EQUIVALENT) 15.15/5.62 By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 15.15/5.62 15.15/5.62 The following dependency pairs can be deleted: 15.15/5.62 15.15/5.62 OPP(j(x)) -> OPP(x) 15.15/5.62 OPP(0(x)) -> OPP(x) 15.15/5.62 OPP(1(x)) -> OPP(x) 15.15/5.62 The following rules are removed from R: 15.15/5.62 15.15/5.62 0(S) -> S 15.15/5.62 plus(S, x) -> x 15.15/5.62 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.62 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.62 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.62 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.62 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.62 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.62 opp(S) -> S 15.15/5.62 opp(0(x)) -> 0(opp(x)) 15.15/5.62 opp(1(x)) -> j(opp(x)) 15.15/5.62 opp(j(x)) -> 1(opp(x)) 15.15/5.62 minus(x, y) -> plus(opp(y), x) 15.15/5.62 times(S, x) -> S 15.15/5.62 times(0(x), y) -> 0(times(x, y)) 15.15/5.62 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.62 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.62 sign(x) -> if_sign(x, S) 15.15/5.62 if_sign(S, x) -> x 15.15/5.62 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.62 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.62 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.62 abs(x) -> if_abs(x, x, S) 15.15/5.62 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.62 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.62 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.62 if_abs(S, x, S) -> S 15.15/5.62 if_abs(S, x, 1(S)) -> x 15.15/5.62 if_abs(S, x, j(S)) -> opp(x) 15.15/5.62 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.62 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.62 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.62 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.62 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.62 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.62 if_min(S, x, y, S) -> x 15.15/5.62 if_min(S, x, y, 1(S)) -> x 15.15/5.62 if_min(S, x, y, j(S)) -> y 15.15/5.62 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.62 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.62 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.62 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 times(times(S, x), ext) -> times(S, ext) 15.15/5.62 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.62 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.62 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.62 The following equations are removed from E: 15.15/5.62 15.15/5.62 plus(x, y) == plus(y, x) 15.15/5.62 times(x, y) == times(y, x) 15.15/5.62 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.62 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.62 Used ordering: POLO with Polynomial interpretation [POLO]: 15.15/5.62 15.15/5.62 POL(0(x_1)) = 3*x_1 15.15/5.62 POL(1(x_1)) = x_1 15.15/5.62 POL(OPP(x_1)) = 2*x_1 15.15/5.62 POL(j(x_1)) = 3*x_1 15.15/5.62 15.15/5.62 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (27) 15.15/5.62 Obligation: 15.15/5.62 P is empty. 15.15/5.62 R is empty. 15.15/5.62 E is empty. 15.15/5.62 E# is empty. 15.15/5.62 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (28) PisEmptyProof (EQUIVALENT) 15.15/5.62 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (29) 15.15/5.62 YES 15.15/5.62 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (30) 15.15/5.62 Obligation: 15.15/5.62 The TRS P consists of the following rules: 15.15/5.62 15.15/5.62 IF_ABS(1(x), y, z) -> IF_ABS(x, y, 1(S)) 15.15/5.62 IF_ABS(j(x), y, z) -> IF_ABS(x, y, j(S)) 15.15/5.62 IF_ABS(0(x), y, z) -> IF_ABS(x, y, z) 15.15/5.62 15.15/5.62 The TRS R consists of the following rules: 15.15/5.62 15.15/5.62 0(S) -> S 15.15/5.62 plus(S, x) -> x 15.15/5.62 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.62 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.62 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.62 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.62 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.62 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.62 opp(S) -> S 15.15/5.62 opp(0(x)) -> 0(opp(x)) 15.15/5.62 opp(1(x)) -> j(opp(x)) 15.15/5.62 opp(j(x)) -> 1(opp(x)) 15.15/5.62 minus(x, y) -> plus(opp(y), x) 15.15/5.62 times(S, x) -> S 15.15/5.62 times(0(x), y) -> 0(times(x, y)) 15.15/5.62 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.62 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.62 sign(x) -> if_sign(x, S) 15.15/5.62 if_sign(S, x) -> x 15.15/5.62 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.62 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.62 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.62 abs(x) -> if_abs(x, x, S) 15.15/5.62 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.62 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.62 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.62 if_abs(S, x, S) -> S 15.15/5.62 if_abs(S, x, 1(S)) -> x 15.15/5.62 if_abs(S, x, j(S)) -> opp(x) 15.15/5.62 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.62 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.62 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.62 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.62 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.62 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.62 if_min(S, x, y, S) -> x 15.15/5.62 if_min(S, x, y, 1(S)) -> x 15.15/5.62 if_min(S, x, y, j(S)) -> y 15.15/5.62 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.62 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.62 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.62 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 times(times(S, x), ext) -> times(S, ext) 15.15/5.62 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.62 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.62 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.62 15.15/5.62 The set E consists of the following equations: 15.15/5.62 15.15/5.62 plus(x, y) == plus(y, x) 15.15/5.62 times(x, y) == times(y, x) 15.15/5.62 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.62 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.62 15.15/5.62 The set E# consists of the following equations: 15.15/5.62 15.15/5.62 PLUS(x, y) == PLUS(y, x) 15.15/5.62 TIMES(x, y) == TIMES(y, x) 15.15/5.62 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.62 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.62 15.15/5.62 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (31) ESharpUsableEquationsProof (EQUIVALENT) 15.15/5.62 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 15.15/5.62 PLUS(x, y) == PLUS(y, x) 15.15/5.62 TIMES(x, y) == TIMES(y, x) 15.15/5.62 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.62 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.62 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (32) 15.15/5.62 Obligation: 15.15/5.62 The TRS P consists of the following rules: 15.15/5.62 15.15/5.62 IF_ABS(1(x), y, z) -> IF_ABS(x, y, 1(S)) 15.15/5.62 IF_ABS(j(x), y, z) -> IF_ABS(x, y, j(S)) 15.15/5.62 IF_ABS(0(x), y, z) -> IF_ABS(x, y, z) 15.15/5.62 15.15/5.62 The TRS R consists of the following rules: 15.15/5.62 15.15/5.62 0(S) -> S 15.15/5.62 plus(S, x) -> x 15.15/5.62 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.62 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.62 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.62 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.62 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.62 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.62 opp(S) -> S 15.15/5.62 opp(0(x)) -> 0(opp(x)) 15.15/5.62 opp(1(x)) -> j(opp(x)) 15.15/5.62 opp(j(x)) -> 1(opp(x)) 15.15/5.62 minus(x, y) -> plus(opp(y), x) 15.15/5.62 times(S, x) -> S 15.15/5.62 times(0(x), y) -> 0(times(x, y)) 15.15/5.62 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.62 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.62 sign(x) -> if_sign(x, S) 15.15/5.62 if_sign(S, x) -> x 15.15/5.62 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.62 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.62 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.62 abs(x) -> if_abs(x, x, S) 15.15/5.62 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.62 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.62 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.62 if_abs(S, x, S) -> S 15.15/5.62 if_abs(S, x, 1(S)) -> x 15.15/5.62 if_abs(S, x, j(S)) -> opp(x) 15.15/5.62 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.62 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.62 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.62 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.62 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.62 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.62 if_min(S, x, y, S) -> x 15.15/5.62 if_min(S, x, y, 1(S)) -> x 15.15/5.62 if_min(S, x, y, j(S)) -> y 15.15/5.62 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.62 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.62 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.62 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 times(times(S, x), ext) -> times(S, ext) 15.15/5.62 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.62 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.62 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.62 15.15/5.62 The set E consists of the following equations: 15.15/5.62 15.15/5.62 plus(x, y) == plus(y, x) 15.15/5.62 times(x, y) == times(y, x) 15.15/5.62 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.62 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.62 15.15/5.62 E# is empty. 15.15/5.62 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (33) EUsableRulesReductionPairsProof (EQUIVALENT) 15.15/5.62 By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 15.15/5.62 15.15/5.62 The following dependency pairs can be deleted: 15.15/5.62 15.15/5.62 IF_ABS(0(x), y, z) -> IF_ABS(x, y, z) 15.15/5.62 The following rules are removed from R: 15.15/5.62 15.15/5.62 0(S) -> S 15.15/5.62 plus(S, x) -> x 15.15/5.62 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.62 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.62 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.62 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.62 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.62 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.62 opp(S) -> S 15.15/5.62 opp(0(x)) -> 0(opp(x)) 15.15/5.62 opp(1(x)) -> j(opp(x)) 15.15/5.62 opp(j(x)) -> 1(opp(x)) 15.15/5.62 minus(x, y) -> plus(opp(y), x) 15.15/5.62 times(S, x) -> S 15.15/5.62 times(0(x), y) -> 0(times(x, y)) 15.15/5.62 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.62 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.62 sign(x) -> if_sign(x, S) 15.15/5.62 if_sign(S, x) -> x 15.15/5.62 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.62 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.62 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.62 abs(x) -> if_abs(x, x, S) 15.15/5.62 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.62 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.62 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.62 if_abs(S, x, S) -> S 15.15/5.62 if_abs(S, x, 1(S)) -> x 15.15/5.62 if_abs(S, x, j(S)) -> opp(x) 15.15/5.62 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.62 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.62 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.62 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.62 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.62 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.62 if_min(S, x, y, S) -> x 15.15/5.62 if_min(S, x, y, 1(S)) -> x 15.15/5.62 if_min(S, x, y, j(S)) -> y 15.15/5.62 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.62 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.62 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.62 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.62 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.62 times(times(S, x), ext) -> times(S, ext) 15.15/5.62 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.62 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.62 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.62 The following equations are removed from E: 15.15/5.62 15.15/5.62 plus(x, y) == plus(y, x) 15.15/5.62 times(x, y) == times(y, x) 15.15/5.62 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.62 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.62 Used ordering: POLO with Polynomial interpretation [POLO]: 15.15/5.62 15.15/5.62 POL(0(x_1)) = 3*x_1 15.15/5.62 POL(1(x_1)) = x_1 15.15/5.62 POL(IF_ABS(x_1, x_2, x_3)) = x_1 + x_2 + x_3 15.15/5.62 POL(S) = 0 15.15/5.62 POL(j(x_1)) = 2*x_1 15.15/5.62 15.15/5.62 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (34) 15.15/5.62 Obligation: 15.15/5.62 The TRS P consists of the following rules: 15.15/5.62 15.15/5.62 IF_ABS(1(x), y, z) -> IF_ABS(x, y, 1(S)) 15.15/5.62 IF_ABS(j(x), y, z) -> IF_ABS(x, y, j(S)) 15.15/5.62 15.15/5.62 R is empty. 15.15/5.62 E is empty. 15.15/5.62 E# is empty. 15.15/5.62 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (35) EDPProblemToQDPProblemProof (EQUIVALENT) 15.15/5.62 The EDP problem does not contain equations anymore, so we can transform it with the EDP to QDP problem processor [DA_STEIN] into a QDP problem. 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (36) 15.15/5.62 Obligation: 15.15/5.62 Q DP problem: 15.15/5.62 The TRS P consists of the following rules: 15.15/5.62 15.15/5.62 IF_ABS(1(x), y, z) -> IF_ABS(x, y, 1(S)) 15.15/5.62 IF_ABS(j(x), y, z) -> IF_ABS(x, y, j(S)) 15.15/5.62 15.15/5.62 R is empty. 15.15/5.62 Q is empty. 15.15/5.62 We have to consider all minimal (P,Q,R)-chains. 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (37) QDPSizeChangeProof (EQUIVALENT) 15.15/5.62 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 15.15/5.62 15.15/5.62 From the DPs we obtained the following set of size-change graphs: 15.15/5.62 *IF_ABS(1(x), y, z) -> IF_ABS(x, y, 1(S)) 15.15/5.62 The graph contains the following edges 1 > 1, 2 >= 2 15.15/5.62 15.15/5.62 15.15/5.62 *IF_ABS(j(x), y, z) -> IF_ABS(x, y, j(S)) 15.15/5.62 The graph contains the following edges 1 > 1, 2 >= 2 15.15/5.62 15.15/5.62 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (38) 15.15/5.62 YES 15.15/5.62 15.15/5.62 ---------------------------------------- 15.15/5.62 15.15/5.62 (39) 15.15/5.62 Obligation: 15.15/5.62 The TRS P consists of the following rules: 15.15/5.63 15.15/5.63 PLUS(plus(0(x), 0(y)), ext) -> PLUS(0(plus(x, y)), ext) 15.15/5.63 PLUS(plus(1(x), j(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(plus(j(x), j(y)), ext) -> PLUS(j(S), plus(x, y)) 15.15/5.63 PLUS(1(x), 1(y)) -> PLUS(x, y) 15.15/5.63 PLUS(0(x), 1(y)) -> PLUS(x, y) 15.15/5.63 PLUS(plus(0(x), 1(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(j(x), j(y)) -> PLUS(x, y) 15.15/5.63 PLUS(plus(1(x), j(y)), ext) -> PLUS(0(plus(x, y)), ext) 15.15/5.63 PLUS(plus(1(x), 1(y)), ext) -> PLUS(1(S), plus(x, y)) 15.15/5.63 PLUS(plus(j(x), j(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(0(x), 0(y)) -> PLUS(x, y) 15.15/5.63 PLUS(plus(0(x), 0(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(plus(1(x), 1(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(plus(j(x), j(y)), ext) -> PLUS(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 PLUS(plus(0(x), 1(y)), ext) -> PLUS(1(plus(x, y)), ext) 15.15/5.63 PLUS(j(x), j(y)) -> PLUS(j(S), plus(x, y)) 15.15/5.63 PLUS(plus(1(x), 1(y)), ext) -> PLUS(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 PLUS(1(x), 1(y)) -> PLUS(1(S), plus(x, y)) 15.15/5.63 PLUS(plus(0(x), j(y)), ext) -> PLUS(j(plus(x, y)), ext) 15.15/5.63 PLUS(0(x), j(y)) -> PLUS(x, y) 15.15/5.63 PLUS(1(x), j(y)) -> PLUS(x, y) 15.15/5.63 PLUS(plus(0(x), j(y)), ext) -> PLUS(x, y) 15.15/5.63 15.15/5.63 The TRS R consists of the following rules: 15.15/5.63 15.15/5.63 0(S) -> S 15.15/5.63 plus(S, x) -> x 15.15/5.63 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.63 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.63 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.63 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.63 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.63 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.63 opp(S) -> S 15.15/5.63 opp(0(x)) -> 0(opp(x)) 15.15/5.63 opp(1(x)) -> j(opp(x)) 15.15/5.63 opp(j(x)) -> 1(opp(x)) 15.15/5.63 minus(x, y) -> plus(opp(y), x) 15.15/5.63 times(S, x) -> S 15.15/5.63 times(0(x), y) -> 0(times(x, y)) 15.15/5.63 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.63 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.63 sign(x) -> if_sign(x, S) 15.15/5.63 if_sign(S, x) -> x 15.15/5.63 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.63 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.63 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.63 abs(x) -> if_abs(x, x, S) 15.15/5.63 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.63 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.63 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.63 if_abs(S, x, S) -> S 15.15/5.63 if_abs(S, x, 1(S)) -> x 15.15/5.63 if_abs(S, x, j(S)) -> opp(x) 15.15/5.63 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.63 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.63 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.63 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.63 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.63 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.63 if_min(S, x, y, S) -> x 15.15/5.63 if_min(S, x, y, 1(S)) -> x 15.15/5.63 if_min(S, x, y, j(S)) -> y 15.15/5.63 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.63 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 times(times(S, x), ext) -> times(S, ext) 15.15/5.63 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.63 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.63 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.63 15.15/5.63 The set E consists of the following equations: 15.15/5.63 15.15/5.63 plus(x, y) == plus(y, x) 15.15/5.63 times(x, y) == times(y, x) 15.15/5.63 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.63 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.63 15.15/5.63 The set E# consists of the following equations: 15.15/5.63 15.15/5.63 PLUS(x, y) == PLUS(y, x) 15.15/5.63 TIMES(x, y) == TIMES(y, x) 15.15/5.63 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.63 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.63 15.15/5.63 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (40) ESharpUsableEquationsProof (EQUIVALENT) 15.15/5.63 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 15.15/5.63 TIMES(x, y) == TIMES(y, x) 15.15/5.63 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.63 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (41) 15.15/5.63 Obligation: 15.15/5.63 The TRS P consists of the following rules: 15.15/5.63 15.15/5.63 PLUS(plus(0(x), 0(y)), ext) -> PLUS(0(plus(x, y)), ext) 15.15/5.63 PLUS(plus(1(x), j(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(plus(j(x), j(y)), ext) -> PLUS(j(S), plus(x, y)) 15.15/5.63 PLUS(1(x), 1(y)) -> PLUS(x, y) 15.15/5.63 PLUS(0(x), 1(y)) -> PLUS(x, y) 15.15/5.63 PLUS(plus(0(x), 1(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(j(x), j(y)) -> PLUS(x, y) 15.15/5.63 PLUS(plus(1(x), j(y)), ext) -> PLUS(0(plus(x, y)), ext) 15.15/5.63 PLUS(plus(1(x), 1(y)), ext) -> PLUS(1(S), plus(x, y)) 15.15/5.63 PLUS(plus(j(x), j(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(0(x), 0(y)) -> PLUS(x, y) 15.15/5.63 PLUS(plus(0(x), 0(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(plus(1(x), 1(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(plus(j(x), j(y)), ext) -> PLUS(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 PLUS(plus(0(x), 1(y)), ext) -> PLUS(1(plus(x, y)), ext) 15.15/5.63 PLUS(j(x), j(y)) -> PLUS(j(S), plus(x, y)) 15.15/5.63 PLUS(plus(1(x), 1(y)), ext) -> PLUS(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 PLUS(1(x), 1(y)) -> PLUS(1(S), plus(x, y)) 15.15/5.63 PLUS(plus(0(x), j(y)), ext) -> PLUS(j(plus(x, y)), ext) 15.15/5.63 PLUS(0(x), j(y)) -> PLUS(x, y) 15.15/5.63 PLUS(1(x), j(y)) -> PLUS(x, y) 15.15/5.63 PLUS(plus(0(x), j(y)), ext) -> PLUS(x, y) 15.15/5.63 15.15/5.63 The TRS R consists of the following rules: 15.15/5.63 15.15/5.63 0(S) -> S 15.15/5.63 plus(S, x) -> x 15.15/5.63 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.63 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.63 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.63 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.63 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.63 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.63 opp(S) -> S 15.15/5.63 opp(0(x)) -> 0(opp(x)) 15.15/5.63 opp(1(x)) -> j(opp(x)) 15.15/5.63 opp(j(x)) -> 1(opp(x)) 15.15/5.63 minus(x, y) -> plus(opp(y), x) 15.15/5.63 times(S, x) -> S 15.15/5.63 times(0(x), y) -> 0(times(x, y)) 15.15/5.63 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.63 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.63 sign(x) -> if_sign(x, S) 15.15/5.63 if_sign(S, x) -> x 15.15/5.63 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.63 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.63 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.63 abs(x) -> if_abs(x, x, S) 15.15/5.63 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.63 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.63 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.63 if_abs(S, x, S) -> S 15.15/5.63 if_abs(S, x, 1(S)) -> x 15.15/5.63 if_abs(S, x, j(S)) -> opp(x) 15.15/5.63 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.63 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.63 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.63 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.63 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.63 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.63 if_min(S, x, y, S) -> x 15.15/5.63 if_min(S, x, y, 1(S)) -> x 15.15/5.63 if_min(S, x, y, j(S)) -> y 15.15/5.63 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.63 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 times(times(S, x), ext) -> times(S, ext) 15.15/5.63 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.63 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.63 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.63 15.15/5.63 The set E consists of the following equations: 15.15/5.63 15.15/5.63 plus(x, y) == plus(y, x) 15.15/5.63 times(x, y) == times(y, x) 15.15/5.63 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.63 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.63 15.15/5.63 The set E# consists of the following equations: 15.15/5.63 15.15/5.63 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.63 PLUS(x, y) == PLUS(y, x) 15.15/5.63 15.15/5.63 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (42) EUsableRulesReductionPairsProof (EQUIVALENT) 15.15/5.63 By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 15.15/5.63 15.15/5.63 No dependency pairs are removed. 15.15/5.63 15.15/5.63 The following rules are removed from R: 15.15/5.63 15.15/5.63 opp(S) -> S 15.15/5.63 opp(0(x)) -> 0(opp(x)) 15.15/5.63 opp(1(x)) -> j(opp(x)) 15.15/5.63 opp(j(x)) -> 1(opp(x)) 15.15/5.63 minus(x, y) -> plus(opp(y), x) 15.15/5.63 times(S, x) -> S 15.15/5.63 times(0(x), y) -> 0(times(x, y)) 15.15/5.63 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.63 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.63 sign(x) -> if_sign(x, S) 15.15/5.63 if_sign(S, x) -> x 15.15/5.63 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.63 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.63 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.63 abs(x) -> if_abs(x, x, S) 15.15/5.63 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.63 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.63 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.63 if_abs(S, x, S) -> S 15.15/5.63 if_abs(S, x, 1(S)) -> x 15.15/5.63 if_abs(S, x, j(S)) -> opp(x) 15.15/5.63 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.63 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.63 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.63 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.63 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.63 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.63 if_min(S, x, y, S) -> x 15.15/5.63 if_min(S, x, y, 1(S)) -> x 15.15/5.63 if_min(S, x, y, j(S)) -> y 15.15/5.63 times(times(S, x), ext) -> times(S, ext) 15.15/5.63 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.63 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.63 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.63 The following equations are removed from E: 15.15/5.63 15.15/5.63 times(x, y) == times(y, x) 15.15/5.63 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.63 Used ordering: POLO with Polynomial interpretation [POLO]: 15.15/5.63 15.15/5.63 POL(0(x_1)) = x_1 15.15/5.63 POL(1(x_1)) = x_1 15.15/5.63 POL(PLUS(x_1, x_2)) = 2*x_1 + 2*x_2 15.15/5.63 POL(S) = 0 15.15/5.63 POL(j(x_1)) = x_1 15.15/5.63 POL(plus(x_1, x_2)) = x_1 + x_2 15.15/5.63 15.15/5.63 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (43) 15.15/5.63 Obligation: 15.15/5.63 The TRS P consists of the following rules: 15.15/5.63 15.15/5.63 PLUS(plus(0(x), 0(y)), ext) -> PLUS(0(plus(x, y)), ext) 15.15/5.63 PLUS(plus(1(x), j(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(plus(j(x), j(y)), ext) -> PLUS(j(S), plus(x, y)) 15.15/5.63 PLUS(1(x), 1(y)) -> PLUS(x, y) 15.15/5.63 PLUS(0(x), 1(y)) -> PLUS(x, y) 15.15/5.63 PLUS(plus(0(x), 1(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(j(x), j(y)) -> PLUS(x, y) 15.15/5.63 PLUS(plus(1(x), j(y)), ext) -> PLUS(0(plus(x, y)), ext) 15.15/5.63 PLUS(plus(1(x), 1(y)), ext) -> PLUS(1(S), plus(x, y)) 15.15/5.63 PLUS(plus(j(x), j(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(0(x), 0(y)) -> PLUS(x, y) 15.15/5.63 PLUS(plus(0(x), 0(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(plus(1(x), 1(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(plus(j(x), j(y)), ext) -> PLUS(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 PLUS(plus(0(x), 1(y)), ext) -> PLUS(1(plus(x, y)), ext) 15.15/5.63 PLUS(j(x), j(y)) -> PLUS(j(S), plus(x, y)) 15.15/5.63 PLUS(plus(1(x), 1(y)), ext) -> PLUS(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 PLUS(1(x), 1(y)) -> PLUS(1(S), plus(x, y)) 15.15/5.63 PLUS(plus(0(x), j(y)), ext) -> PLUS(j(plus(x, y)), ext) 15.15/5.63 PLUS(0(x), j(y)) -> PLUS(x, y) 15.15/5.63 PLUS(1(x), j(y)) -> PLUS(x, y) 15.15/5.63 PLUS(plus(0(x), j(y)), ext) -> PLUS(x, y) 15.15/5.63 15.15/5.63 The TRS R consists of the following rules: 15.15/5.63 15.15/5.63 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.63 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.63 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.63 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.63 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.63 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.63 plus(S, x) -> x 15.15/5.63 0(S) -> S 15.15/5.63 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.63 15.15/5.63 The set E consists of the following equations: 15.15/5.63 15.15/5.63 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.63 plus(x, y) == plus(y, x) 15.15/5.63 15.15/5.63 The set E# consists of the following equations: 15.15/5.63 15.15/5.63 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.63 PLUS(x, y) == PLUS(y, x) 15.15/5.63 15.15/5.63 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (44) ERuleRemovalProof (EQUIVALENT) 15.15/5.63 By using the rule removal processor [DA_STEIN] with the following polynomial ordering [POLO], at least one Dependency Pair or term rewrite system rule of this EDP problem can be strictly oriented. 15.15/5.63 15.15/5.63 Strictly oriented dependency pairs: 15.15/5.63 15.15/5.63 PLUS(plus(0(x), 0(y)), ext) -> PLUS(0(plus(x, y)), ext) 15.15/5.63 PLUS(plus(1(x), j(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(plus(j(x), j(y)), ext) -> PLUS(j(S), plus(x, y)) 15.15/5.63 PLUS(1(x), 1(y)) -> PLUS(x, y) 15.15/5.63 PLUS(0(x), 1(y)) -> PLUS(x, y) 15.15/5.63 PLUS(plus(0(x), 1(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(j(x), j(y)) -> PLUS(x, y) 15.15/5.63 PLUS(plus(1(x), j(y)), ext) -> PLUS(0(plus(x, y)), ext) 15.15/5.63 PLUS(plus(1(x), 1(y)), ext) -> PLUS(1(S), plus(x, y)) 15.15/5.63 PLUS(plus(j(x), j(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(0(x), 0(y)) -> PLUS(x, y) 15.15/5.63 PLUS(plus(0(x), 0(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(plus(1(x), 1(y)), ext) -> PLUS(x, y) 15.15/5.63 PLUS(plus(0(x), 1(y)), ext) -> PLUS(1(plus(x, y)), ext) 15.15/5.63 PLUS(j(x), j(y)) -> PLUS(j(S), plus(x, y)) 15.15/5.63 PLUS(1(x), 1(y)) -> PLUS(1(S), plus(x, y)) 15.15/5.63 PLUS(plus(0(x), j(y)), ext) -> PLUS(j(plus(x, y)), ext) 15.15/5.63 PLUS(0(x), j(y)) -> PLUS(x, y) 15.15/5.63 PLUS(1(x), j(y)) -> PLUS(x, y) 15.15/5.63 PLUS(plus(0(x), j(y)), ext) -> PLUS(x, y) 15.15/5.63 15.15/5.63 Strictly oriented rules of the TRS R: 15.15/5.63 15.15/5.63 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.63 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.63 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.63 0(S) -> S 15.15/5.63 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.63 15.15/5.63 Used ordering: POLO with Polynomial interpretation [POLO]: 15.15/5.63 15.15/5.63 POL(0(x_1)) = 1 + x_1 15.15/5.63 POL(1(x_1)) = 2 + x_1 15.15/5.63 POL(PLUS(x_1, x_2)) = x_1 + x_2 15.15/5.63 POL(S) = 0 15.15/5.63 POL(j(x_1)) = 2 + x_1 15.15/5.63 POL(plus(x_1, x_2)) = x_1 + x_2 15.15/5.63 15.15/5.63 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (45) 15.15/5.63 Obligation: 15.15/5.63 The TRS P consists of the following rules: 15.15/5.63 15.15/5.63 PLUS(plus(j(x), j(y)), ext) -> PLUS(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 PLUS(plus(1(x), 1(y)), ext) -> PLUS(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 15.15/5.63 The TRS R consists of the following rules: 15.15/5.63 15.15/5.63 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.63 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.63 plus(S, x) -> x 15.15/5.63 15.15/5.63 The set E consists of the following equations: 15.15/5.63 15.15/5.63 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.63 plus(x, y) == plus(y, x) 15.15/5.63 15.15/5.63 The set E# consists of the following equations: 15.15/5.63 15.15/5.63 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.63 PLUS(x, y) == PLUS(y, x) 15.15/5.63 15.15/5.63 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (46) EDPPoloProof (EQUIVALENT) 15.15/5.63 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. 15.15/5.63 15.15/5.63 15.15/5.63 PLUS(plus(j(x), j(y)), ext) -> PLUS(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 PLUS(plus(1(x), 1(y)), ext) -> PLUS(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 15.15/5.63 15.15/5.63 15.15/5.63 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.63 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.63 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 plus(S, x) -> x 15.15/5.63 We had to orient the following equations of E# equivalently. 15.15/5.63 15.15/5.63 15.15/5.63 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.63 PLUS(x, y) == PLUS(y, x) 15.15/5.63 With the implicit AFS we had to orient the following usable equations of E equivalently. 15.15/5.63 15.15/5.63 15.15/5.63 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.63 plus(x, y) == plus(y, x) 15.15/5.63 Used ordering: POLO with Polynomial interpretation [POLO]: 15.15/5.63 15.15/5.63 POL(1(x_1)) = 0 15.15/5.63 POL(PLUS(x_1, x_2)) = x_1 + x_2 15.15/5.63 POL(S) = 0 15.15/5.63 POL(j(x_1)) = 0 15.15/5.63 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 15.15/5.63 15.15/5.63 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (47) 15.15/5.63 Obligation: 15.15/5.63 P is empty. 15.15/5.63 The TRS R consists of the following rules: 15.15/5.63 15.15/5.63 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.63 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.63 plus(S, x) -> x 15.15/5.63 15.15/5.63 The set E consists of the following equations: 15.15/5.63 15.15/5.63 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.63 plus(x, y) == plus(y, x) 15.15/5.63 15.15/5.63 The set E# consists of the following equations: 15.15/5.63 15.15/5.63 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.63 PLUS(x, y) == PLUS(y, x) 15.15/5.63 15.15/5.63 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (48) PisEmptyProof (EQUIVALENT) 15.15/5.63 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (49) 15.15/5.63 YES 15.15/5.63 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (50) 15.15/5.63 Obligation: 15.15/5.63 The TRS P consists of the following rules: 15.15/5.63 15.15/5.63 TIMES(times(0(x), y), ext) -> TIMES(x, y) 15.15/5.63 TIMES(0(x), y) -> TIMES(x, y) 15.15/5.63 TIMES(times(j(x), y), ext) -> TIMES(x, y) 15.15/5.63 TIMES(times(j(x), y), ext) -> TIMES(minus(0(times(x, y)), y), ext) 15.15/5.63 TIMES(times(S, x), ext) -> TIMES(S, ext) 15.15/5.63 TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) 15.15/5.63 TIMES(times(1(x), y), ext) -> TIMES(plus(0(times(x, y)), y), ext) 15.15/5.63 TIMES(1(x), y) -> TIMES(x, y) 15.15/5.63 TIMES(j(x), y) -> TIMES(x, y) 15.15/5.63 TIMES(times(1(x), y), ext) -> TIMES(x, y) 15.15/5.63 15.15/5.63 The TRS R consists of the following rules: 15.15/5.63 15.15/5.63 0(S) -> S 15.15/5.63 plus(S, x) -> x 15.15/5.63 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.63 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.63 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.63 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.63 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.63 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.63 opp(S) -> S 15.15/5.63 opp(0(x)) -> 0(opp(x)) 15.15/5.63 opp(1(x)) -> j(opp(x)) 15.15/5.63 opp(j(x)) -> 1(opp(x)) 15.15/5.63 minus(x, y) -> plus(opp(y), x) 15.15/5.63 times(S, x) -> S 15.15/5.63 times(0(x), y) -> 0(times(x, y)) 15.15/5.63 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.63 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.63 sign(x) -> if_sign(x, S) 15.15/5.63 if_sign(S, x) -> x 15.15/5.63 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.63 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.63 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.63 abs(x) -> if_abs(x, x, S) 15.15/5.63 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.63 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.63 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.63 if_abs(S, x, S) -> S 15.15/5.63 if_abs(S, x, 1(S)) -> x 15.15/5.63 if_abs(S, x, j(S)) -> opp(x) 15.15/5.63 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.63 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.63 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.63 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.63 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.63 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.63 if_min(S, x, y, S) -> x 15.15/5.63 if_min(S, x, y, 1(S)) -> x 15.15/5.63 if_min(S, x, y, j(S)) -> y 15.15/5.63 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.63 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 times(times(S, x), ext) -> times(S, ext) 15.15/5.63 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.63 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.63 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.63 15.15/5.63 The set E consists of the following equations: 15.15/5.63 15.15/5.63 plus(x, y) == plus(y, x) 15.15/5.63 times(x, y) == times(y, x) 15.15/5.63 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.63 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.63 15.15/5.63 The set E# consists of the following equations: 15.15/5.63 15.15/5.63 PLUS(x, y) == PLUS(y, x) 15.15/5.63 TIMES(x, y) == TIMES(y, x) 15.15/5.63 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.63 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.63 15.15/5.63 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (51) ESharpUsableEquationsProof (EQUIVALENT) 15.15/5.63 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 15.15/5.63 PLUS(x, y) == PLUS(y, x) 15.15/5.63 PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) 15.15/5.63 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (52) 15.15/5.63 Obligation: 15.15/5.63 The TRS P consists of the following rules: 15.15/5.63 15.15/5.63 TIMES(times(0(x), y), ext) -> TIMES(x, y) 15.15/5.63 TIMES(0(x), y) -> TIMES(x, y) 15.15/5.63 TIMES(times(j(x), y), ext) -> TIMES(x, y) 15.15/5.63 TIMES(times(j(x), y), ext) -> TIMES(minus(0(times(x, y)), y), ext) 15.15/5.63 TIMES(times(S, x), ext) -> TIMES(S, ext) 15.15/5.63 TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) 15.15/5.63 TIMES(times(1(x), y), ext) -> TIMES(plus(0(times(x, y)), y), ext) 15.15/5.63 TIMES(1(x), y) -> TIMES(x, y) 15.15/5.63 TIMES(j(x), y) -> TIMES(x, y) 15.15/5.63 TIMES(times(1(x), y), ext) -> TIMES(x, y) 15.15/5.63 15.15/5.63 The TRS R consists of the following rules: 15.15/5.63 15.15/5.63 0(S) -> S 15.15/5.63 plus(S, x) -> x 15.15/5.63 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.63 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.63 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.63 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.63 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.63 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.63 opp(S) -> S 15.15/5.63 opp(0(x)) -> 0(opp(x)) 15.15/5.63 opp(1(x)) -> j(opp(x)) 15.15/5.63 opp(j(x)) -> 1(opp(x)) 15.15/5.63 minus(x, y) -> plus(opp(y), x) 15.15/5.63 times(S, x) -> S 15.15/5.63 times(0(x), y) -> 0(times(x, y)) 15.15/5.63 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.63 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.63 sign(x) -> if_sign(x, S) 15.15/5.63 if_sign(S, x) -> x 15.15/5.63 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.63 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.63 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.63 abs(x) -> if_abs(x, x, S) 15.15/5.63 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.63 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.63 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.63 if_abs(S, x, S) -> S 15.15/5.63 if_abs(S, x, 1(S)) -> x 15.15/5.63 if_abs(S, x, j(S)) -> opp(x) 15.15/5.63 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.63 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.63 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.63 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.63 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.63 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.63 if_min(S, x, y, S) -> x 15.15/5.63 if_min(S, x, y, 1(S)) -> x 15.15/5.63 if_min(S, x, y, j(S)) -> y 15.15/5.63 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.63 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 times(times(S, x), ext) -> times(S, ext) 15.15/5.63 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.63 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.63 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.63 15.15/5.63 The set E consists of the following equations: 15.15/5.63 15.15/5.63 plus(x, y) == plus(y, x) 15.15/5.63 times(x, y) == times(y, x) 15.15/5.63 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.63 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.63 15.15/5.63 The set E# consists of the following equations: 15.15/5.63 15.15/5.63 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.63 TIMES(x, y) == TIMES(y, x) 15.15/5.63 15.15/5.63 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (53) EDPPoloProof (EQUIVALENT) 15.15/5.63 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented. 15.15/5.63 15.15/5.63 15.15/5.63 TIMES(times(j(x), y), ext) -> TIMES(x, y) 15.15/5.63 TIMES(times(1(x), y), ext) -> TIMES(plus(0(times(x, y)), y), ext) 15.15/5.63 TIMES(1(x), y) -> TIMES(x, y) 15.15/5.63 TIMES(j(x), y) -> TIMES(x, y) 15.15/5.63 TIMES(times(1(x), y), ext) -> TIMES(x, y) 15.15/5.63 The remaining Dependency Pairs were at least non-strictly oriented. 15.15/5.63 15.15/5.63 15.15/5.63 TIMES(times(0(x), y), ext) -> TIMES(x, y) 15.15/5.63 TIMES(0(x), y) -> TIMES(x, y) 15.15/5.63 TIMES(times(j(x), y), ext) -> TIMES(minus(0(times(x, y)), y), ext) 15.15/5.63 TIMES(times(S, x), ext) -> TIMES(S, ext) 15.15/5.63 TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) 15.15/5.63 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 15.15/5.63 15.15/5.63 15.15/5.63 minus(x, y) -> plus(opp(y), x) 15.15/5.63 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.63 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.63 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.63 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.63 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.63 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.63 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.63 plus(S, x) -> x 15.15/5.63 opp(1(x)) -> j(opp(x)) 15.15/5.63 opp(0(x)) -> 0(opp(x)) 15.15/5.63 opp(S) -> S 15.15/5.63 opp(j(x)) -> 1(opp(x)) 15.15/5.63 0(S) -> S 15.15/5.63 times(S, x) -> S 15.15/5.63 times(times(S, x), ext) -> times(S, ext) 15.15/5.63 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.63 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.63 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.63 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.63 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.63 times(0(x), y) -> 0(times(x, y)) 15.15/5.63 We had to orient the following equations of E# equivalently. 15.15/5.63 15.15/5.63 15.15/5.63 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.63 TIMES(x, y) == TIMES(y, x) 15.15/5.63 With the implicit AFS we had to orient the following usable equations of E equivalently. 15.15/5.63 15.15/5.63 15.15/5.63 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.63 plus(x, y) == plus(y, x) 15.15/5.63 times(x, y) == times(y, x) 15.15/5.63 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.63 Used ordering: POLO with Polynomial interpretation [POLO]: 15.15/5.63 15.15/5.63 POL(0(x_1)) = x_1 15.15/5.63 POL(1(x_1)) = 1 + x_1 15.15/5.63 POL(S) = 0 15.15/5.63 POL(TIMES(x_1, x_2)) = x_1 + x_1*x_2 + x_2 15.15/5.63 POL(j(x_1)) = 1 + x_1 15.15/5.63 POL(minus(x_1, x_2)) = 1 + x_1 + x_2 15.15/5.63 POL(opp(x_1)) = 1 + x_1 15.15/5.63 POL(plus(x_1, x_2)) = x_1 + x_2 15.15/5.63 POL(times(x_1, x_2)) = x_1 + x_1*x_2 + x_2 15.15/5.63 15.15/5.63 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (54) 15.15/5.63 Obligation: 15.15/5.63 The TRS P consists of the following rules: 15.15/5.63 15.15/5.63 TIMES(times(0(x), y), ext) -> TIMES(x, y) 15.15/5.63 TIMES(0(x), y) -> TIMES(x, y) 15.15/5.63 TIMES(times(j(x), y), ext) -> TIMES(minus(0(times(x, y)), y), ext) 15.15/5.63 TIMES(times(S, x), ext) -> TIMES(S, ext) 15.15/5.63 TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) 15.15/5.63 15.15/5.63 The TRS R consists of the following rules: 15.15/5.63 15.15/5.63 0(S) -> S 15.15/5.63 plus(S, x) -> x 15.15/5.63 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.63 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.63 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.63 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.63 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.63 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.63 opp(S) -> S 15.15/5.63 opp(0(x)) -> 0(opp(x)) 15.15/5.63 opp(1(x)) -> j(opp(x)) 15.15/5.63 opp(j(x)) -> 1(opp(x)) 15.15/5.63 minus(x, y) -> plus(opp(y), x) 15.15/5.63 times(S, x) -> S 15.15/5.63 times(0(x), y) -> 0(times(x, y)) 15.15/5.63 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.63 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.63 sign(x) -> if_sign(x, S) 15.15/5.63 if_sign(S, x) -> x 15.15/5.63 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.63 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.63 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.63 abs(x) -> if_abs(x, x, S) 15.15/5.63 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.63 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.63 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.63 if_abs(S, x, S) -> S 15.15/5.63 if_abs(S, x, 1(S)) -> x 15.15/5.63 if_abs(S, x, j(S)) -> opp(x) 15.15/5.63 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.63 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.63 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.63 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.63 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.63 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.63 if_min(S, x, y, S) -> x 15.15/5.63 if_min(S, x, y, 1(S)) -> x 15.15/5.63 if_min(S, x, y, j(S)) -> y 15.15/5.63 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.63 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 times(times(S, x), ext) -> times(S, ext) 15.15/5.63 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.63 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.63 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.63 15.15/5.63 The set E consists of the following equations: 15.15/5.63 15.15/5.63 plus(x, y) == plus(y, x) 15.15/5.63 times(x, y) == times(y, x) 15.15/5.63 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.63 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.63 15.15/5.63 The set E# consists of the following equations: 15.15/5.63 15.15/5.63 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.63 TIMES(x, y) == TIMES(y, x) 15.15/5.63 15.15/5.63 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (55) EDPPoloProof (EQUIVALENT) 15.15/5.63 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented. 15.15/5.63 15.15/5.63 15.15/5.63 TIMES(times(j(x), y), ext) -> TIMES(minus(0(times(x, y)), y), ext) 15.15/5.63 The remaining Dependency Pairs were at least non-strictly oriented. 15.15/5.63 15.15/5.63 15.15/5.63 TIMES(times(0(x), y), ext) -> TIMES(x, y) 15.15/5.63 TIMES(0(x), y) -> TIMES(x, y) 15.15/5.63 TIMES(times(S, x), ext) -> TIMES(S, ext) 15.15/5.63 TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) 15.15/5.63 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 15.15/5.63 15.15/5.63 15.15/5.63 minus(x, y) -> plus(opp(y), x) 15.15/5.63 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.63 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.63 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.63 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.63 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.63 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.63 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.63 plus(S, x) -> x 15.15/5.63 opp(1(x)) -> j(opp(x)) 15.15/5.63 opp(0(x)) -> 0(opp(x)) 15.15/5.63 opp(S) -> S 15.15/5.63 opp(j(x)) -> 1(opp(x)) 15.15/5.63 times(S, x) -> S 15.15/5.63 times(times(S, x), ext) -> times(S, ext) 15.15/5.63 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.63 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.63 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.63 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.63 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.63 times(0(x), y) -> 0(times(x, y)) 15.15/5.63 0(S) -> S 15.15/5.63 We had to orient the following equations of E# equivalently. 15.15/5.63 15.15/5.63 15.15/5.63 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.63 TIMES(x, y) == TIMES(y, x) 15.15/5.63 With the implicit AFS we had to orient the following usable equations of E equivalently. 15.15/5.63 15.15/5.63 15.15/5.63 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.63 plus(x, y) == plus(y, x) 15.15/5.63 times(x, y) == times(y, x) 15.15/5.63 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.63 Used ordering: POLO with Polynomial interpretation [POLO]: 15.15/5.63 15.15/5.63 POL(0(x_1)) = x_1 15.15/5.63 POL(1(x_1)) = 1 + x_1 15.15/5.63 POL(S) = 0 15.15/5.63 POL(TIMES(x_1, x_2)) = x_1 + x_1*x_2 + x_2 15.15/5.63 POL(j(x_1)) = 1 + x_1 15.15/5.63 POL(minus(x_1, x_2)) = x_1 + x_2 15.15/5.63 POL(opp(x_1)) = x_1 15.15/5.63 POL(plus(x_1, x_2)) = x_1 + x_2 15.15/5.63 POL(times(x_1, x_2)) = x_1 + x_1*x_2 + x_2 15.15/5.63 15.15/5.63 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (56) 15.15/5.63 Obligation: 15.15/5.63 The TRS P consists of the following rules: 15.15/5.63 15.15/5.63 TIMES(times(0(x), y), ext) -> TIMES(x, y) 15.15/5.63 TIMES(0(x), y) -> TIMES(x, y) 15.15/5.63 TIMES(times(S, x), ext) -> TIMES(S, ext) 15.15/5.63 TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) 15.15/5.63 15.15/5.63 The TRS R consists of the following rules: 15.15/5.63 15.15/5.63 0(S) -> S 15.15/5.63 plus(S, x) -> x 15.15/5.63 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.63 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.63 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.63 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.63 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.63 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.63 opp(S) -> S 15.15/5.63 opp(0(x)) -> 0(opp(x)) 15.15/5.63 opp(1(x)) -> j(opp(x)) 15.15/5.63 opp(j(x)) -> 1(opp(x)) 15.15/5.63 minus(x, y) -> plus(opp(y), x) 15.15/5.63 times(S, x) -> S 15.15/5.63 times(0(x), y) -> 0(times(x, y)) 15.15/5.63 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.63 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.63 sign(x) -> if_sign(x, S) 15.15/5.63 if_sign(S, x) -> x 15.15/5.63 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.63 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.63 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.63 abs(x) -> if_abs(x, x, S) 15.15/5.63 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.63 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.63 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.63 if_abs(S, x, S) -> S 15.15/5.63 if_abs(S, x, 1(S)) -> x 15.15/5.63 if_abs(S, x, j(S)) -> opp(x) 15.15/5.63 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.63 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.63 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.63 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.63 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.63 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.63 if_min(S, x, y, S) -> x 15.15/5.63 if_min(S, x, y, 1(S)) -> x 15.15/5.63 if_min(S, x, y, j(S)) -> y 15.15/5.63 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.63 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 times(times(S, x), ext) -> times(S, ext) 15.15/5.63 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.63 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.63 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.63 15.15/5.63 The set E consists of the following equations: 15.15/5.63 15.15/5.63 plus(x, y) == plus(y, x) 15.15/5.63 times(x, y) == times(y, x) 15.15/5.63 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.63 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.63 15.15/5.63 The set E# consists of the following equations: 15.15/5.63 15.15/5.63 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.63 TIMES(x, y) == TIMES(y, x) 15.15/5.63 15.15/5.63 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (57) EDPPoloProof (EQUIVALENT) 15.15/5.63 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented. 15.15/5.63 15.15/5.63 15.15/5.63 TIMES(times(0(x), y), ext) -> TIMES(x, y) 15.15/5.63 TIMES(0(x), y) -> TIMES(x, y) 15.15/5.63 The remaining Dependency Pairs were at least non-strictly oriented. 15.15/5.63 15.15/5.63 15.15/5.63 TIMES(times(S, x), ext) -> TIMES(S, ext) 15.15/5.63 TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) 15.15/5.63 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 15.15/5.63 15.15/5.63 15.15/5.63 times(S, x) -> S 15.15/5.63 times(times(S, x), ext) -> times(S, ext) 15.15/5.63 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.63 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.63 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.63 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.63 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.63 times(0(x), y) -> 0(times(x, y)) 15.15/5.63 0(S) -> S 15.15/5.63 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.63 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.63 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.63 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.63 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.63 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.63 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.63 plus(S, x) -> x 15.15/5.63 opp(1(x)) -> j(opp(x)) 15.15/5.63 opp(0(x)) -> 0(opp(x)) 15.15/5.63 opp(S) -> S 15.15/5.63 opp(j(x)) -> 1(opp(x)) 15.15/5.63 minus(x, y) -> plus(opp(y), x) 15.15/5.63 We had to orient the following equations of E# equivalently. 15.15/5.63 15.15/5.63 15.15/5.63 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.63 TIMES(x, y) == TIMES(y, x) 15.15/5.63 With the implicit AFS we had to orient the following usable equations of E equivalently. 15.15/5.63 15.15/5.63 15.15/5.63 times(x, y) == times(y, x) 15.15/5.63 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.63 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.63 plus(x, y) == plus(y, x) 15.15/5.63 Used ordering: POLO with Polynomial interpretation [POLO]: 15.15/5.63 15.15/5.63 POL(0(x_1)) = 1 + x_1 15.15/5.63 POL(1(x_1)) = 1 + x_1 15.15/5.63 POL(S) = 0 15.15/5.63 POL(TIMES(x_1, x_2)) = x_1 + x_1*x_2 + x_2 15.15/5.63 POL(j(x_1)) = 1 + x_1 15.15/5.63 POL(minus(x_1, x_2)) = x_1 + x_2 15.15/5.63 POL(opp(x_1)) = x_1 15.15/5.63 POL(plus(x_1, x_2)) = x_1 + x_2 15.15/5.63 POL(times(x_1, x_2)) = x_1 + x_1*x_2 + x_2 15.15/5.63 15.15/5.63 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (58) 15.15/5.63 Obligation: 15.15/5.63 The TRS P consists of the following rules: 15.15/5.63 15.15/5.63 TIMES(times(S, x), ext) -> TIMES(S, ext) 15.15/5.63 TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) 15.15/5.63 15.15/5.63 The TRS R consists of the following rules: 15.15/5.63 15.15/5.63 0(S) -> S 15.15/5.63 plus(S, x) -> x 15.15/5.63 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.63 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.63 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.63 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.63 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.63 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.63 opp(S) -> S 15.15/5.63 opp(0(x)) -> 0(opp(x)) 15.15/5.63 opp(1(x)) -> j(opp(x)) 15.15/5.63 opp(j(x)) -> 1(opp(x)) 15.15/5.63 minus(x, y) -> plus(opp(y), x) 15.15/5.63 times(S, x) -> S 15.15/5.63 times(0(x), y) -> 0(times(x, y)) 15.15/5.63 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.63 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.63 sign(x) -> if_sign(x, S) 15.15/5.63 if_sign(S, x) -> x 15.15/5.63 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.63 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.63 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.63 abs(x) -> if_abs(x, x, S) 15.15/5.63 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.63 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.63 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.63 if_abs(S, x, S) -> S 15.15/5.63 if_abs(S, x, 1(S)) -> x 15.15/5.63 if_abs(S, x, j(S)) -> opp(x) 15.15/5.63 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.63 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.63 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.63 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.63 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.63 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.63 if_min(S, x, y, S) -> x 15.15/5.63 if_min(S, x, y, 1(S)) -> x 15.15/5.63 if_min(S, x, y, j(S)) -> y 15.15/5.63 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.63 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 times(times(S, x), ext) -> times(S, ext) 15.15/5.63 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.63 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.63 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.63 15.15/5.63 The set E consists of the following equations: 15.15/5.63 15.15/5.63 plus(x, y) == plus(y, x) 15.15/5.63 times(x, y) == times(y, x) 15.15/5.63 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.63 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.63 15.15/5.63 The set E# consists of the following equations: 15.15/5.63 15.15/5.63 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.63 TIMES(x, y) == TIMES(y, x) 15.15/5.63 15.15/5.63 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (59) EDPPoloProof (EQUIVALENT) 15.15/5.63 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. 15.15/5.63 15.15/5.63 15.15/5.63 TIMES(times(S, x), ext) -> TIMES(S, ext) 15.15/5.63 TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) 15.15/5.63 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 15.15/5.63 15.15/5.63 15.15/5.63 0(S) -> S 15.15/5.63 times(S, x) -> S 15.15/5.63 times(times(S, x), ext) -> times(S, ext) 15.15/5.63 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.63 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.63 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.63 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.63 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.63 times(0(x), y) -> 0(times(x, y)) 15.15/5.63 minus(x, y) -> plus(opp(y), x) 15.15/5.63 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.63 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.63 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.63 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.63 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.63 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.63 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.63 plus(S, x) -> x 15.15/5.63 opp(1(x)) -> j(opp(x)) 15.15/5.63 opp(0(x)) -> 0(opp(x)) 15.15/5.63 opp(S) -> S 15.15/5.63 opp(j(x)) -> 1(opp(x)) 15.15/5.63 We had to orient the following equations of E# equivalently. 15.15/5.63 15.15/5.63 15.15/5.63 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.63 TIMES(x, y) == TIMES(y, x) 15.15/5.63 With the implicit AFS we had to orient the following usable equations of E equivalently. 15.15/5.63 15.15/5.63 15.15/5.63 times(x, y) == times(y, x) 15.15/5.63 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.63 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.63 plus(x, y) == plus(y, x) 15.15/5.63 Used ordering: POLO with Polynomial interpretation [POLO]: 15.15/5.63 15.15/5.63 POL(0(x_1)) = 3 15.15/5.63 POL(1(x_1)) = 2 15.15/5.63 POL(S) = 3 15.15/5.63 POL(TIMES(x_1, x_2)) = 3*x_1 + 3*x_2 15.15/5.63 POL(j(x_1)) = 2 15.15/5.63 POL(minus(x_1, x_2)) = 2 + x_1 + x_2 15.15/5.63 POL(opp(x_1)) = 2 + x_1 15.15/5.63 POL(plus(x_1, x_2)) = x_1 + x_2 15.15/5.63 POL(times(x_1, x_2)) = 3 + x_1 + x_2 15.15/5.63 15.15/5.63 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (60) 15.15/5.63 Obligation: 15.15/5.63 P is empty. 15.15/5.63 The TRS R consists of the following rules: 15.15/5.63 15.15/5.63 0(S) -> S 15.15/5.63 plus(S, x) -> x 15.15/5.63 plus(0(x), 0(y)) -> 0(plus(x, y)) 15.15/5.63 plus(0(x), 1(y)) -> 1(plus(x, y)) 15.15/5.63 plus(0(x), j(y)) -> j(plus(x, y)) 15.15/5.63 plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) 15.15/5.63 plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) 15.15/5.63 plus(1(x), j(y)) -> 0(plus(x, y)) 15.15/5.63 opp(S) -> S 15.15/5.63 opp(0(x)) -> 0(opp(x)) 15.15/5.63 opp(1(x)) -> j(opp(x)) 15.15/5.63 opp(j(x)) -> 1(opp(x)) 15.15/5.63 minus(x, y) -> plus(opp(y), x) 15.15/5.63 times(S, x) -> S 15.15/5.63 times(0(x), y) -> 0(times(x, y)) 15.15/5.63 times(1(x), y) -> plus(0(times(x, y)), y) 15.15/5.63 times(j(x), y) -> minus(0(times(x, y)), y) 15.15/5.63 sign(x) -> if_sign(x, S) 15.15/5.63 if_sign(S, x) -> x 15.15/5.63 if_sign(0(x), y) -> if_sign(x, y) 15.15/5.63 if_sign(1(x), y) -> if_sign(x, 1(S)) 15.15/5.63 if_sign(j(x), y) -> if_sign(x, j(S)) 15.15/5.63 abs(x) -> if_abs(x, x, S) 15.15/5.63 if_abs(0(x), y, z) -> if_abs(x, y, z) 15.15/5.63 if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) 15.15/5.63 if_abs(j(x), y, z) -> if_abs(x, y, j(S)) 15.15/5.63 if_abs(S, x, S) -> S 15.15/5.63 if_abs(S, x, 1(S)) -> x 15.15/5.63 if_abs(S, x, j(S)) -> opp(x) 15.15/5.63 min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) 15.15/5.63 min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) 15.15/5.63 min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) 15.15/5.63 if_min(0(x), y, z, u) -> if_min(x, y, z, u) 15.15/5.63 if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) 15.15/5.63 if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) 15.15/5.63 if_min(S, x, y, S) -> x 15.15/5.63 if_min(S, x, y, 1(S)) -> x 15.15/5.63 if_min(S, x, y, j(S)) -> y 15.15/5.63 plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) 15.15/5.63 plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) 15.15/5.63 plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) 15.15/5.63 plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) 15.15/5.63 plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) 15.15/5.63 times(times(S, x), ext) -> times(S, ext) 15.15/5.63 times(times(0(x), y), ext) -> times(0(times(x, y)), ext) 15.15/5.63 times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) 15.15/5.63 times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) 15.15/5.63 15.15/5.63 The set E consists of the following equations: 15.15/5.63 15.15/5.63 plus(x, y) == plus(y, x) 15.15/5.63 times(x, y) == times(y, x) 15.15/5.63 plus(plus(x, y), z) == plus(x, plus(y, z)) 15.15/5.63 times(times(x, y), z) == times(x, times(y, z)) 15.15/5.63 15.15/5.63 The set E# consists of the following equations: 15.15/5.63 15.15/5.63 TIMES(times(x, y), z) == TIMES(x, times(y, z)) 15.15/5.63 TIMES(x, y) == TIMES(y, x) 15.15/5.63 15.15/5.63 We have to consider all minimal (P,E#,R,E)-chains 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (61) PisEmptyProof (EQUIVALENT) 15.15/5.63 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 15.15/5.63 ---------------------------------------- 15.15/5.63 15.15/5.63 (62) 15.15/5.63 YES 15.38/5.74 EOF