YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination of the given ETRS could be proven: (0) ETRS (1) EquationalDependencyPairsProof [EQUIVALENT, 335 ms] (2) EDP (3) EDependencyGraphProof [EQUIVALENT, 0 ms] (4) AND (5) EDP (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] (7) EDP (8) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (9) EDP (10) EDPProblemToQDPProblemProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) EDP (15) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] (16) EDP (17) EUsableRulesReductionPairsProof [EQUIVALENT, 5 ms] (18) EDP (19) EDPProblemToQDPProblemProof [EQUIVALENT, 0 ms] (20) QDP (21) QDPSizeChangeProof [EQUIVALENT, 0 ms] (22) YES (23) EDP (24) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] (25) EDP (26) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (27) EDP (28) PisEmptyProof [EQUIVALENT, 0 ms] (29) YES (30) EDP (31) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] (32) EDP (33) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (34) EDP (35) EDPProblemToQDPProblemProof [EQUIVALENT, 0 ms] (36) QDP (37) QDPSizeChangeProof [EQUIVALENT, 0 ms] (38) YES (39) EDP (40) ESharpUsableEquationsProof [EQUIVALENT, 158 ms] (41) EDP (42) EUsableRulesReductionPairsProof [EQUIVALENT, 201 ms] (43) EDP (44) ERuleRemovalProof [EQUIVALENT, 33 ms] (45) EDP (46) EDPPoloProof [EQUIVALENT, 0 ms] (47) EDP (48) PisEmptyProof [EQUIVALENT, 0 ms] (49) YES (50) EDP (51) ESharpUsableEquationsProof [EQUIVALENT, 35 ms] (52) EDP (53) EDPPoloProof [EQUIVALENT, 238 ms] (54) EDP (55) EDPPoloProof [EQUIVALENT, 226 ms] (56) EDP (57) EDPPoloProof [EQUIVALENT, 211 ms] (58) EDP (59) EDPPoloProof [EQUIVALENT, 26 ms] (60) EDP (61) PisEmptyProof [EQUIVALENT, 0 ms] (62) YES ---------------------------------------- (0) Obligation: Equational rewrite system: The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) ---------------------------------------- (1) EquationalDependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: The TRS P consists of the following rules: PLUS(0(x), 0(y)) -> 0^1(plus(x, y)) PLUS(0(x), 0(y)) -> PLUS(x, y) PLUS(0(x), 1(y)) -> PLUS(x, y) PLUS(0(x), j(y)) -> PLUS(x, y) PLUS(1(x), 1(y)) -> PLUS(1(S), plus(x, y)) PLUS(1(x), 1(y)) -> PLUS(x, y) PLUS(j(x), j(y)) -> PLUS(j(S), plus(x, y)) PLUS(j(x), j(y)) -> PLUS(x, y) PLUS(1(x), j(y)) -> 0^1(plus(x, y)) PLUS(1(x), j(y)) -> PLUS(x, y) OPP(0(x)) -> 0^1(opp(x)) OPP(0(x)) -> OPP(x) OPP(1(x)) -> OPP(x) OPP(j(x)) -> OPP(x) MINUS(x, y) -> PLUS(opp(y), x) MINUS(x, y) -> OPP(y) TIMES(0(x), y) -> 0^1(times(x, y)) TIMES(0(x), y) -> TIMES(x, y) TIMES(1(x), y) -> PLUS(0(times(x, y)), y) TIMES(1(x), y) -> 0^1(times(x, y)) TIMES(1(x), y) -> TIMES(x, y) TIMES(j(x), y) -> MINUS(0(times(x, y)), y) TIMES(j(x), y) -> 0^1(times(x, y)) TIMES(j(x), y) -> TIMES(x, y) SIGN(x) -> IF_SIGN(x, S) IF_SIGN(0(x), y) -> IF_SIGN(x, y) IF_SIGN(1(x), y) -> IF_SIGN(x, 1(S)) IF_SIGN(j(x), y) -> IF_SIGN(x, j(S)) ABS(x) -> IF_ABS(x, x, S) IF_ABS(0(x), y, z) -> IF_ABS(x, y, z) IF_ABS(1(x), y, z) -> IF_ABS(x, y, 1(S)) IF_ABS(j(x), y, z) -> IF_ABS(x, y, j(S)) IF_ABS(S, x, j(S)) -> OPP(x) MIN(x, y) -> IF_MIN(minus(abs(y), abs(x)), x, y, S) MIN(x, y) -> MINUS(abs(y), abs(x)) MIN(x, y) -> ABS(y) MIN(x, y) -> ABS(x) MIN'(x, y) -> IF_MIN(minus(abs(1(y)), abs(1(x))), x, y, S) MIN'(x, y) -> MINUS(abs(1(y)), abs(1(x))) MIN'(x, y) -> ABS(1(y)) MIN'(x, y) -> ABS(1(x)) MIN''(x, y) -> IF_MIN(minus(abs(j(y)), abs(j(x))), x, y, S) MIN''(x, y) -> MINUS(abs(j(y)), abs(j(x))) MIN''(x, y) -> ABS(j(y)) MIN''(x, y) -> ABS(j(x)) IF_MIN(0(x), y, z, u) -> IF_MIN(x, y, z, u) IF_MIN(1(x), y, z, u) -> IF_MIN(x, y, z, 1(S)) IF_MIN(j(x), y, z, u) -> IF_MIN(x, y, z, j(S)) PLUS(plus(0(x), 0(y)), ext) -> PLUS(0(plus(x, y)), ext) PLUS(plus(0(x), 0(y)), ext) -> 0^1(plus(x, y)) PLUS(plus(0(x), 0(y)), ext) -> PLUS(x, y) PLUS(plus(0(x), 1(y)), ext) -> PLUS(1(plus(x, y)), ext) PLUS(plus(0(x), 1(y)), ext) -> PLUS(x, y) PLUS(plus(0(x), j(y)), ext) -> PLUS(j(plus(x, y)), ext) PLUS(plus(0(x), j(y)), ext) -> PLUS(x, y) PLUS(plus(1(x), 1(y)), ext) -> PLUS(j(plus(1(S), plus(x, y))), ext) PLUS(plus(1(x), 1(y)), ext) -> PLUS(1(S), plus(x, y)) PLUS(plus(1(x), 1(y)), ext) -> PLUS(x, y) PLUS(plus(j(x), j(y)), ext) -> PLUS(1(plus(j(S), plus(x, y))), ext) PLUS(plus(j(x), j(y)), ext) -> PLUS(j(S), plus(x, y)) PLUS(plus(j(x), j(y)), ext) -> PLUS(x, y) PLUS(plus(1(x), j(y)), ext) -> PLUS(0(plus(x, y)), ext) PLUS(plus(1(x), j(y)), ext) -> 0^1(plus(x, y)) PLUS(plus(1(x), j(y)), ext) -> PLUS(x, y) TIMES(times(S, x), ext) -> TIMES(S, ext) TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) TIMES(times(0(x), y), ext) -> 0^1(times(x, y)) TIMES(times(0(x), y), ext) -> TIMES(x, y) TIMES(times(1(x), y), ext) -> TIMES(plus(0(times(x, y)), y), ext) TIMES(times(1(x), y), ext) -> PLUS(0(times(x, y)), y) TIMES(times(1(x), y), ext) -> 0^1(times(x, y)) TIMES(times(1(x), y), ext) -> TIMES(x, y) TIMES(times(j(x), y), ext) -> TIMES(minus(0(times(x, y)), y), ext) TIMES(times(j(x), y), ext) -> MINUS(0(times(x, y)), y) TIMES(times(j(x), y), ext) -> 0^1(times(x, y)) TIMES(times(j(x), y), ext) -> TIMES(x, y) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) TIMES(x, y) == TIMES(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) TIMES(times(x, y), z) == TIMES(x, times(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (2) Obligation: The TRS P consists of the following rules: PLUS(0(x), 0(y)) -> 0^1(plus(x, y)) PLUS(0(x), 0(y)) -> PLUS(x, y) PLUS(0(x), 1(y)) -> PLUS(x, y) PLUS(0(x), j(y)) -> PLUS(x, y) PLUS(1(x), 1(y)) -> PLUS(1(S), plus(x, y)) PLUS(1(x), 1(y)) -> PLUS(x, y) PLUS(j(x), j(y)) -> PLUS(j(S), plus(x, y)) PLUS(j(x), j(y)) -> PLUS(x, y) PLUS(1(x), j(y)) -> 0^1(plus(x, y)) PLUS(1(x), j(y)) -> PLUS(x, y) OPP(0(x)) -> 0^1(opp(x)) OPP(0(x)) -> OPP(x) OPP(1(x)) -> OPP(x) OPP(j(x)) -> OPP(x) MINUS(x, y) -> PLUS(opp(y), x) MINUS(x, y) -> OPP(y) TIMES(0(x), y) -> 0^1(times(x, y)) TIMES(0(x), y) -> TIMES(x, y) TIMES(1(x), y) -> PLUS(0(times(x, y)), y) TIMES(1(x), y) -> 0^1(times(x, y)) TIMES(1(x), y) -> TIMES(x, y) TIMES(j(x), y) -> MINUS(0(times(x, y)), y) TIMES(j(x), y) -> 0^1(times(x, y)) TIMES(j(x), y) -> TIMES(x, y) SIGN(x) -> IF_SIGN(x, S) IF_SIGN(0(x), y) -> IF_SIGN(x, y) IF_SIGN(1(x), y) -> IF_SIGN(x, 1(S)) IF_SIGN(j(x), y) -> IF_SIGN(x, j(S)) ABS(x) -> IF_ABS(x, x, S) IF_ABS(0(x), y, z) -> IF_ABS(x, y, z) IF_ABS(1(x), y, z) -> IF_ABS(x, y, 1(S)) IF_ABS(j(x), y, z) -> IF_ABS(x, y, j(S)) IF_ABS(S, x, j(S)) -> OPP(x) MIN(x, y) -> IF_MIN(minus(abs(y), abs(x)), x, y, S) MIN(x, y) -> MINUS(abs(y), abs(x)) MIN(x, y) -> ABS(y) MIN(x, y) -> ABS(x) MIN'(x, y) -> IF_MIN(minus(abs(1(y)), abs(1(x))), x, y, S) MIN'(x, y) -> MINUS(abs(1(y)), abs(1(x))) MIN'(x, y) -> ABS(1(y)) MIN'(x, y) -> ABS(1(x)) MIN''(x, y) -> IF_MIN(minus(abs(j(y)), abs(j(x))), x, y, S) MIN''(x, y) -> MINUS(abs(j(y)), abs(j(x))) MIN''(x, y) -> ABS(j(y)) MIN''(x, y) -> ABS(j(x)) IF_MIN(0(x), y, z, u) -> IF_MIN(x, y, z, u) IF_MIN(1(x), y, z, u) -> IF_MIN(x, y, z, 1(S)) IF_MIN(j(x), y, z, u) -> IF_MIN(x, y, z, j(S)) PLUS(plus(0(x), 0(y)), ext) -> PLUS(0(plus(x, y)), ext) PLUS(plus(0(x), 0(y)), ext) -> 0^1(plus(x, y)) PLUS(plus(0(x), 0(y)), ext) -> PLUS(x, y) PLUS(plus(0(x), 1(y)), ext) -> PLUS(1(plus(x, y)), ext) PLUS(plus(0(x), 1(y)), ext) -> PLUS(x, y) PLUS(plus(0(x), j(y)), ext) -> PLUS(j(plus(x, y)), ext) PLUS(plus(0(x), j(y)), ext) -> PLUS(x, y) PLUS(plus(1(x), 1(y)), ext) -> PLUS(j(plus(1(S), plus(x, y))), ext) PLUS(plus(1(x), 1(y)), ext) -> PLUS(1(S), plus(x, y)) PLUS(plus(1(x), 1(y)), ext) -> PLUS(x, y) PLUS(plus(j(x), j(y)), ext) -> PLUS(1(plus(j(S), plus(x, y))), ext) PLUS(plus(j(x), j(y)), ext) -> PLUS(j(S), plus(x, y)) PLUS(plus(j(x), j(y)), ext) -> PLUS(x, y) PLUS(plus(1(x), j(y)), ext) -> PLUS(0(plus(x, y)), ext) PLUS(plus(1(x), j(y)), ext) -> 0^1(plus(x, y)) PLUS(plus(1(x), j(y)), ext) -> PLUS(x, y) TIMES(times(S, x), ext) -> TIMES(S, ext) TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) TIMES(times(0(x), y), ext) -> 0^1(times(x, y)) TIMES(times(0(x), y), ext) -> TIMES(x, y) TIMES(times(1(x), y), ext) -> TIMES(plus(0(times(x, y)), y), ext) TIMES(times(1(x), y), ext) -> PLUS(0(times(x, y)), y) TIMES(times(1(x), y), ext) -> 0^1(times(x, y)) TIMES(times(1(x), y), ext) -> TIMES(x, y) TIMES(times(j(x), y), ext) -> TIMES(minus(0(times(x, y)), y), ext) TIMES(times(j(x), y), ext) -> MINUS(0(times(x, y)), y) TIMES(times(j(x), y), ext) -> 0^1(times(x, y)) TIMES(times(j(x), y), ext) -> TIMES(x, y) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) TIMES(x, y) == TIMES(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) TIMES(times(x, y), z) == TIMES(x, times(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (3) EDependencyGraphProof (EQUIVALENT) The approximation of the Equational Dependency Graph [DA_STEIN] contains 6 SCCs with 32 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: The TRS P consists of the following rules: IF_MIN(1(x), y, z, u) -> IF_MIN(x, y, z, 1(S)) IF_MIN(j(x), y, z, u) -> IF_MIN(x, y, z, j(S)) IF_MIN(0(x), y, z, u) -> IF_MIN(x, y, z, u) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) TIMES(x, y) == TIMES(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) TIMES(times(x, y), z) == TIMES(x, times(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (6) ESharpUsableEquationsProof (EQUIVALENT) We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: PLUS(x, y) == PLUS(y, x) TIMES(x, y) == TIMES(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) TIMES(times(x, y), z) == TIMES(x, times(y, z)) ---------------------------------------- (7) Obligation: The TRS P consists of the following rules: IF_MIN(1(x), y, z, u) -> IF_MIN(x, y, z, 1(S)) IF_MIN(j(x), y, z, u) -> IF_MIN(x, y, z, j(S)) IF_MIN(0(x), y, z, u) -> IF_MIN(x, y, z, u) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (8) EUsableRulesReductionPairsProof (EQUIVALENT) 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. The following dependency pairs can be deleted: IF_MIN(0(x), y, z, u) -> IF_MIN(x, y, z, u) The following rules are removed from R: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The following equations are removed from E: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0(x_1)) = 3*x_1 POL(1(x_1)) = x_1 POL(IF_MIN(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 POL(S) = 0 POL(j(x_1)) = x_1 ---------------------------------------- (9) Obligation: The TRS P consists of the following rules: IF_MIN(1(x), y, z, u) -> IF_MIN(x, y, z, 1(S)) IF_MIN(j(x), y, z, u) -> IF_MIN(x, y, z, j(S)) R is empty. E is empty. E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (10) EDPProblemToQDPProblemProof (EQUIVALENT) 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. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: IF_MIN(1(x), y, z, u) -> IF_MIN(x, y, z, 1(S)) IF_MIN(j(x), y, z, u) -> IF_MIN(x, y, z, j(S)) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *IF_MIN(1(x), y, z, u) -> IF_MIN(x, y, z, 1(S)) The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 *IF_MIN(j(x), y, z, u) -> IF_MIN(x, y, z, j(S)) The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: The TRS P consists of the following rules: IF_SIGN(0(x), y) -> IF_SIGN(x, y) IF_SIGN(1(x), y) -> IF_SIGN(x, 1(S)) IF_SIGN(j(x), y) -> IF_SIGN(x, j(S)) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) TIMES(x, y) == TIMES(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) TIMES(times(x, y), z) == TIMES(x, times(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (15) ESharpUsableEquationsProof (EQUIVALENT) We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: PLUS(x, y) == PLUS(y, x) TIMES(x, y) == TIMES(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) TIMES(times(x, y), z) == TIMES(x, times(y, z)) ---------------------------------------- (16) Obligation: The TRS P consists of the following rules: IF_SIGN(0(x), y) -> IF_SIGN(x, y) IF_SIGN(1(x), y) -> IF_SIGN(x, 1(S)) IF_SIGN(j(x), y) -> IF_SIGN(x, j(S)) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (17) EUsableRulesReductionPairsProof (EQUIVALENT) 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. The following dependency pairs can be deleted: IF_SIGN(0(x), y) -> IF_SIGN(x, y) The following rules are removed from R: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The following equations are removed from E: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0(x_1)) = 3*x_1 POL(1(x_1)) = x_1 POL(IF_SIGN(x_1, x_2)) = x_1 + x_2 POL(S) = 0 POL(j(x_1)) = x_1 ---------------------------------------- (18) Obligation: The TRS P consists of the following rules: IF_SIGN(1(x), y) -> IF_SIGN(x, 1(S)) IF_SIGN(j(x), y) -> IF_SIGN(x, j(S)) R is empty. E is empty. E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (19) EDPProblemToQDPProblemProof (EQUIVALENT) 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. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: IF_SIGN(1(x), y) -> IF_SIGN(x, 1(S)) IF_SIGN(j(x), y) -> IF_SIGN(x, j(S)) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *IF_SIGN(1(x), y) -> IF_SIGN(x, 1(S)) The graph contains the following edges 1 > 1 *IF_SIGN(j(x), y) -> IF_SIGN(x, j(S)) The graph contains the following edges 1 > 1 ---------------------------------------- (22) YES ---------------------------------------- (23) Obligation: The TRS P consists of the following rules: OPP(j(x)) -> OPP(x) OPP(0(x)) -> OPP(x) OPP(1(x)) -> OPP(x) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) TIMES(x, y) == TIMES(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) TIMES(times(x, y), z) == TIMES(x, times(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (24) ESharpUsableEquationsProof (EQUIVALENT) We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: PLUS(x, y) == PLUS(y, x) TIMES(x, y) == TIMES(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) TIMES(times(x, y), z) == TIMES(x, times(y, z)) ---------------------------------------- (25) Obligation: The TRS P consists of the following rules: OPP(j(x)) -> OPP(x) OPP(0(x)) -> OPP(x) OPP(1(x)) -> OPP(x) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (26) EUsableRulesReductionPairsProof (EQUIVALENT) 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. The following dependency pairs can be deleted: OPP(j(x)) -> OPP(x) OPP(0(x)) -> OPP(x) OPP(1(x)) -> OPP(x) The following rules are removed from R: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The following equations are removed from E: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0(x_1)) = 3*x_1 POL(1(x_1)) = x_1 POL(OPP(x_1)) = 2*x_1 POL(j(x_1)) = 3*x_1 ---------------------------------------- (27) Obligation: P is empty. R is empty. E is empty. E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (28) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,E#,R,E) chain. ---------------------------------------- (29) YES ---------------------------------------- (30) Obligation: The TRS P consists of the following rules: IF_ABS(1(x), y, z) -> IF_ABS(x, y, 1(S)) IF_ABS(j(x), y, z) -> IF_ABS(x, y, j(S)) IF_ABS(0(x), y, z) -> IF_ABS(x, y, z) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) TIMES(x, y) == TIMES(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) TIMES(times(x, y), z) == TIMES(x, times(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (31) ESharpUsableEquationsProof (EQUIVALENT) We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: PLUS(x, y) == PLUS(y, x) TIMES(x, y) == TIMES(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) TIMES(times(x, y), z) == TIMES(x, times(y, z)) ---------------------------------------- (32) Obligation: The TRS P consists of the following rules: IF_ABS(1(x), y, z) -> IF_ABS(x, y, 1(S)) IF_ABS(j(x), y, z) -> IF_ABS(x, y, j(S)) IF_ABS(0(x), y, z) -> IF_ABS(x, y, z) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (33) EUsableRulesReductionPairsProof (EQUIVALENT) 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. The following dependency pairs can be deleted: IF_ABS(0(x), y, z) -> IF_ABS(x, y, z) The following rules are removed from R: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The following equations are removed from E: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0(x_1)) = 3*x_1 POL(1(x_1)) = x_1 POL(IF_ABS(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(S) = 0 POL(j(x_1)) = 2*x_1 ---------------------------------------- (34) Obligation: The TRS P consists of the following rules: IF_ABS(1(x), y, z) -> IF_ABS(x, y, 1(S)) IF_ABS(j(x), y, z) -> IF_ABS(x, y, j(S)) R is empty. E is empty. E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (35) EDPProblemToQDPProblemProof (EQUIVALENT) 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. ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: IF_ABS(1(x), y, z) -> IF_ABS(x, y, 1(S)) IF_ABS(j(x), y, z) -> IF_ABS(x, y, j(S)) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) QDPSizeChangeProof (EQUIVALENT) 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. From the DPs we obtained the following set of size-change graphs: *IF_ABS(1(x), y, z) -> IF_ABS(x, y, 1(S)) The graph contains the following edges 1 > 1, 2 >= 2 *IF_ABS(j(x), y, z) -> IF_ABS(x, y, j(S)) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (38) YES ---------------------------------------- (39) Obligation: The TRS P consists of the following rules: PLUS(plus(0(x), 0(y)), ext) -> PLUS(0(plus(x, y)), ext) PLUS(plus(1(x), j(y)), ext) -> PLUS(x, y) PLUS(plus(j(x), j(y)), ext) -> PLUS(j(S), plus(x, y)) PLUS(1(x), 1(y)) -> PLUS(x, y) PLUS(0(x), 1(y)) -> PLUS(x, y) PLUS(plus(0(x), 1(y)), ext) -> PLUS(x, y) PLUS(j(x), j(y)) -> PLUS(x, y) PLUS(plus(1(x), j(y)), ext) -> PLUS(0(plus(x, y)), ext) PLUS(plus(1(x), 1(y)), ext) -> PLUS(1(S), plus(x, y)) PLUS(plus(j(x), j(y)), ext) -> PLUS(x, y) PLUS(0(x), 0(y)) -> PLUS(x, y) PLUS(plus(0(x), 0(y)), ext) -> PLUS(x, y) PLUS(plus(1(x), 1(y)), ext) -> PLUS(x, y) PLUS(plus(j(x), j(y)), ext) -> PLUS(1(plus(j(S), plus(x, y))), ext) PLUS(plus(0(x), 1(y)), ext) -> PLUS(1(plus(x, y)), ext) PLUS(j(x), j(y)) -> PLUS(j(S), plus(x, y)) PLUS(plus(1(x), 1(y)), ext) -> PLUS(j(plus(1(S), plus(x, y))), ext) PLUS(1(x), 1(y)) -> PLUS(1(S), plus(x, y)) PLUS(plus(0(x), j(y)), ext) -> PLUS(j(plus(x, y)), ext) PLUS(0(x), j(y)) -> PLUS(x, y) PLUS(1(x), j(y)) -> PLUS(x, y) PLUS(plus(0(x), j(y)), ext) -> PLUS(x, y) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) TIMES(x, y) == TIMES(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) TIMES(times(x, y), z) == TIMES(x, times(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (40) ESharpUsableEquationsProof (EQUIVALENT) We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: TIMES(x, y) == TIMES(y, x) TIMES(times(x, y), z) == TIMES(x, times(y, z)) ---------------------------------------- (41) Obligation: The TRS P consists of the following rules: PLUS(plus(0(x), 0(y)), ext) -> PLUS(0(plus(x, y)), ext) PLUS(plus(1(x), j(y)), ext) -> PLUS(x, y) PLUS(plus(j(x), j(y)), ext) -> PLUS(j(S), plus(x, y)) PLUS(1(x), 1(y)) -> PLUS(x, y) PLUS(0(x), 1(y)) -> PLUS(x, y) PLUS(plus(0(x), 1(y)), ext) -> PLUS(x, y) PLUS(j(x), j(y)) -> PLUS(x, y) PLUS(plus(1(x), j(y)), ext) -> PLUS(0(plus(x, y)), ext) PLUS(plus(1(x), 1(y)), ext) -> PLUS(1(S), plus(x, y)) PLUS(plus(j(x), j(y)), ext) -> PLUS(x, y) PLUS(0(x), 0(y)) -> PLUS(x, y) PLUS(plus(0(x), 0(y)), ext) -> PLUS(x, y) PLUS(plus(1(x), 1(y)), ext) -> PLUS(x, y) PLUS(plus(j(x), j(y)), ext) -> PLUS(1(plus(j(S), plus(x, y))), ext) PLUS(plus(0(x), 1(y)), ext) -> PLUS(1(plus(x, y)), ext) PLUS(j(x), j(y)) -> PLUS(j(S), plus(x, y)) PLUS(plus(1(x), 1(y)), ext) -> PLUS(j(plus(1(S), plus(x, y))), ext) PLUS(1(x), 1(y)) -> PLUS(1(S), plus(x, y)) PLUS(plus(0(x), j(y)), ext) -> PLUS(j(plus(x, y)), ext) PLUS(0(x), j(y)) -> PLUS(x, y) PLUS(1(x), j(y)) -> PLUS(x, y) PLUS(plus(0(x), j(y)), ext) -> PLUS(x, y) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) The set E# consists of the following equations: PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) PLUS(x, y) == PLUS(y, x) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (42) EUsableRulesReductionPairsProof (EQUIVALENT) 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. No dependency pairs are removed. The following rules are removed from R: opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The following equations are removed from E: times(x, y) == times(y, x) times(times(x, y), z) == times(x, times(y, z)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0(x_1)) = x_1 POL(1(x_1)) = x_1 POL(PLUS(x_1, x_2)) = 2*x_1 + 2*x_2 POL(S) = 0 POL(j(x_1)) = x_1 POL(plus(x_1, x_2)) = x_1 + x_2 ---------------------------------------- (43) Obligation: The TRS P consists of the following rules: PLUS(plus(0(x), 0(y)), ext) -> PLUS(0(plus(x, y)), ext) PLUS(plus(1(x), j(y)), ext) -> PLUS(x, y) PLUS(plus(j(x), j(y)), ext) -> PLUS(j(S), plus(x, y)) PLUS(1(x), 1(y)) -> PLUS(x, y) PLUS(0(x), 1(y)) -> PLUS(x, y) PLUS(plus(0(x), 1(y)), ext) -> PLUS(x, y) PLUS(j(x), j(y)) -> PLUS(x, y) PLUS(plus(1(x), j(y)), ext) -> PLUS(0(plus(x, y)), ext) PLUS(plus(1(x), 1(y)), ext) -> PLUS(1(S), plus(x, y)) PLUS(plus(j(x), j(y)), ext) -> PLUS(x, y) PLUS(0(x), 0(y)) -> PLUS(x, y) PLUS(plus(0(x), 0(y)), ext) -> PLUS(x, y) PLUS(plus(1(x), 1(y)), ext) -> PLUS(x, y) PLUS(plus(j(x), j(y)), ext) -> PLUS(1(plus(j(S), plus(x, y))), ext) PLUS(plus(0(x), 1(y)), ext) -> PLUS(1(plus(x, y)), ext) PLUS(j(x), j(y)) -> PLUS(j(S), plus(x, y)) PLUS(plus(1(x), 1(y)), ext) -> PLUS(j(plus(1(S), plus(x, y))), ext) PLUS(1(x), 1(y)) -> PLUS(1(S), plus(x, y)) PLUS(plus(0(x), j(y)), ext) -> PLUS(j(plus(x, y)), ext) PLUS(0(x), j(y)) -> PLUS(x, y) PLUS(1(x), j(y)) -> PLUS(x, y) PLUS(plus(0(x), j(y)), ext) -> PLUS(x, y) The TRS R consists of the following rules: plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(1(x), j(y)) -> 0(plus(x, y)) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(S, x) -> x 0(S) -> S plus(0(x), 0(y)) -> 0(plus(x, y)) The set E consists of the following equations: plus(plus(x, y), z) == plus(x, plus(y, z)) plus(x, y) == plus(y, x) The set E# consists of the following equations: PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) PLUS(x, y) == PLUS(y, x) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (44) ERuleRemovalProof (EQUIVALENT) 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. Strictly oriented dependency pairs: PLUS(plus(0(x), 0(y)), ext) -> PLUS(0(plus(x, y)), ext) PLUS(plus(1(x), j(y)), ext) -> PLUS(x, y) PLUS(plus(j(x), j(y)), ext) -> PLUS(j(S), plus(x, y)) PLUS(1(x), 1(y)) -> PLUS(x, y) PLUS(0(x), 1(y)) -> PLUS(x, y) PLUS(plus(0(x), 1(y)), ext) -> PLUS(x, y) PLUS(j(x), j(y)) -> PLUS(x, y) PLUS(plus(1(x), j(y)), ext) -> PLUS(0(plus(x, y)), ext) PLUS(plus(1(x), 1(y)), ext) -> PLUS(1(S), plus(x, y)) PLUS(plus(j(x), j(y)), ext) -> PLUS(x, y) PLUS(0(x), 0(y)) -> PLUS(x, y) PLUS(plus(0(x), 0(y)), ext) -> PLUS(x, y) PLUS(plus(1(x), 1(y)), ext) -> PLUS(x, y) PLUS(plus(0(x), 1(y)), ext) -> PLUS(1(plus(x, y)), ext) PLUS(j(x), j(y)) -> PLUS(j(S), plus(x, y)) PLUS(1(x), 1(y)) -> PLUS(1(S), plus(x, y)) PLUS(plus(0(x), j(y)), ext) -> PLUS(j(plus(x, y)), ext) PLUS(0(x), j(y)) -> PLUS(x, y) PLUS(1(x), j(y)) -> PLUS(x, y) PLUS(plus(0(x), j(y)), ext) -> PLUS(x, y) Strictly oriented rules of the TRS R: plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(1(x), j(y)) -> 0(plus(x, y)) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) plus(0(x), j(y)) -> j(plus(x, y)) 0(S) -> S plus(0(x), 0(y)) -> 0(plus(x, y)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0(x_1)) = 1 + x_1 POL(1(x_1)) = 2 + x_1 POL(PLUS(x_1, x_2)) = x_1 + x_2 POL(S) = 0 POL(j(x_1)) = 2 + x_1 POL(plus(x_1, x_2)) = x_1 + x_2 ---------------------------------------- (45) Obligation: The TRS P consists of the following rules: PLUS(plus(j(x), j(y)), ext) -> PLUS(1(plus(j(S), plus(x, y))), ext) PLUS(plus(1(x), 1(y)), ext) -> PLUS(j(plus(1(S), plus(x, y))), ext) The TRS R consists of the following rules: plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(S, x) -> x The set E consists of the following equations: plus(plus(x, y), z) == plus(x, plus(y, z)) plus(x, y) == plus(y, x) The set E# consists of the following equations: PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) PLUS(x, y) == PLUS(y, x) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (46) EDPPoloProof (EQUIVALENT) We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. PLUS(plus(j(x), j(y)), ext) -> PLUS(1(plus(j(S), plus(x, y))), ext) PLUS(plus(1(x), 1(y)), ext) -> PLUS(j(plus(1(S), plus(x, y))), ext) With the implicit AFS we had to orient the following set of usable rules of R non-strictly. plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(S, x) -> x We had to orient the following equations of E# equivalently. PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) PLUS(x, y) == PLUS(y, x) With the implicit AFS we had to orient the following usable equations of E equivalently. plus(plus(x, y), z) == plus(x, plus(y, z)) plus(x, y) == plus(y, x) Used ordering: POLO with Polynomial interpretation [POLO]: POL(1(x_1)) = 0 POL(PLUS(x_1, x_2)) = x_1 + x_2 POL(S) = 0 POL(j(x_1)) = 0 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 ---------------------------------------- (47) Obligation: P is empty. The TRS R consists of the following rules: plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(S, x) -> x The set E consists of the following equations: plus(plus(x, y), z) == plus(x, plus(y, z)) plus(x, y) == plus(y, x) The set E# consists of the following equations: PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) PLUS(x, y) == PLUS(y, x) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (48) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,E#,R,E) chain. ---------------------------------------- (49) YES ---------------------------------------- (50) Obligation: The TRS P consists of the following rules: TIMES(times(0(x), y), ext) -> TIMES(x, y) TIMES(0(x), y) -> TIMES(x, y) TIMES(times(j(x), y), ext) -> TIMES(x, y) TIMES(times(j(x), y), ext) -> TIMES(minus(0(times(x, y)), y), ext) TIMES(times(S, x), ext) -> TIMES(S, ext) TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) TIMES(times(1(x), y), ext) -> TIMES(plus(0(times(x, y)), y), ext) TIMES(1(x), y) -> TIMES(x, y) TIMES(j(x), y) -> TIMES(x, y) TIMES(times(1(x), y), ext) -> TIMES(x, y) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) TIMES(x, y) == TIMES(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) TIMES(times(x, y), z) == TIMES(x, times(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (51) ESharpUsableEquationsProof (EQUIVALENT) We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) ---------------------------------------- (52) Obligation: The TRS P consists of the following rules: TIMES(times(0(x), y), ext) -> TIMES(x, y) TIMES(0(x), y) -> TIMES(x, y) TIMES(times(j(x), y), ext) -> TIMES(x, y) TIMES(times(j(x), y), ext) -> TIMES(minus(0(times(x, y)), y), ext) TIMES(times(S, x), ext) -> TIMES(S, ext) TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) TIMES(times(1(x), y), ext) -> TIMES(plus(0(times(x, y)), y), ext) TIMES(1(x), y) -> TIMES(x, y) TIMES(j(x), y) -> TIMES(x, y) TIMES(times(1(x), y), ext) -> TIMES(x, y) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) The set E# consists of the following equations: TIMES(times(x, y), z) == TIMES(x, times(y, z)) TIMES(x, y) == TIMES(y, x) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (53) EDPPoloProof (EQUIVALENT) 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. TIMES(times(j(x), y), ext) -> TIMES(x, y) TIMES(times(1(x), y), ext) -> TIMES(plus(0(times(x, y)), y), ext) TIMES(1(x), y) -> TIMES(x, y) TIMES(j(x), y) -> TIMES(x, y) TIMES(times(1(x), y), ext) -> TIMES(x, y) The remaining Dependency Pairs were at least non-strictly oriented. TIMES(times(0(x), y), ext) -> TIMES(x, y) TIMES(0(x), y) -> TIMES(x, y) TIMES(times(j(x), y), ext) -> TIMES(minus(0(times(x, y)), y), ext) TIMES(times(S, x), ext) -> TIMES(S, ext) TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) With the implicit AFS we had to orient the following set of usable rules of R non-strictly. minus(x, y) -> plus(opp(y), x) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(0(x), 0(y)) -> 0(plus(x, y)) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(1(x), j(y)) -> 0(plus(x, y)) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(S, x) -> x opp(1(x)) -> j(opp(x)) opp(0(x)) -> 0(opp(x)) opp(S) -> S opp(j(x)) -> 1(opp(x)) 0(S) -> S times(S, x) -> S times(times(S, x), ext) -> times(S, ext) times(1(x), y) -> plus(0(times(x, y)), y) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(j(x), y) -> minus(0(times(x, y)), y) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) times(0(x), y) -> 0(times(x, y)) We had to orient the following equations of E# equivalently. TIMES(times(x, y), z) == TIMES(x, times(y, z)) TIMES(x, y) == TIMES(y, x) With the implicit AFS we had to orient the following usable equations of E equivalently. plus(plus(x, y), z) == plus(x, plus(y, z)) plus(x, y) == plus(y, x) times(x, y) == times(y, x) times(times(x, y), z) == times(x, times(y, z)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0(x_1)) = x_1 POL(1(x_1)) = 1 + x_1 POL(S) = 0 POL(TIMES(x_1, x_2)) = x_1 + x_1*x_2 + x_2 POL(j(x_1)) = 1 + x_1 POL(minus(x_1, x_2)) = 1 + x_1 + x_2 POL(opp(x_1)) = 1 + x_1 POL(plus(x_1, x_2)) = x_1 + x_2 POL(times(x_1, x_2)) = x_1 + x_1*x_2 + x_2 ---------------------------------------- (54) Obligation: The TRS P consists of the following rules: TIMES(times(0(x), y), ext) -> TIMES(x, y) TIMES(0(x), y) -> TIMES(x, y) TIMES(times(j(x), y), ext) -> TIMES(minus(0(times(x, y)), y), ext) TIMES(times(S, x), ext) -> TIMES(S, ext) TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) The set E# consists of the following equations: TIMES(times(x, y), z) == TIMES(x, times(y, z)) TIMES(x, y) == TIMES(y, x) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (55) EDPPoloProof (EQUIVALENT) 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. TIMES(times(j(x), y), ext) -> TIMES(minus(0(times(x, y)), y), ext) The remaining Dependency Pairs were at least non-strictly oriented. TIMES(times(0(x), y), ext) -> TIMES(x, y) TIMES(0(x), y) -> TIMES(x, y) TIMES(times(S, x), ext) -> TIMES(S, ext) TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) With the implicit AFS we had to orient the following set of usable rules of R non-strictly. minus(x, y) -> plus(opp(y), x) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(0(x), 0(y)) -> 0(plus(x, y)) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(1(x), j(y)) -> 0(plus(x, y)) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(S, x) -> x opp(1(x)) -> j(opp(x)) opp(0(x)) -> 0(opp(x)) opp(S) -> S opp(j(x)) -> 1(opp(x)) times(S, x) -> S times(times(S, x), ext) -> times(S, ext) times(1(x), y) -> plus(0(times(x, y)), y) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(j(x), y) -> minus(0(times(x, y)), y) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) times(0(x), y) -> 0(times(x, y)) 0(S) -> S We had to orient the following equations of E# equivalently. TIMES(times(x, y), z) == TIMES(x, times(y, z)) TIMES(x, y) == TIMES(y, x) With the implicit AFS we had to orient the following usable equations of E equivalently. plus(plus(x, y), z) == plus(x, plus(y, z)) plus(x, y) == plus(y, x) times(x, y) == times(y, x) times(times(x, y), z) == times(x, times(y, z)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0(x_1)) = x_1 POL(1(x_1)) = 1 + x_1 POL(S) = 0 POL(TIMES(x_1, x_2)) = x_1 + x_1*x_2 + x_2 POL(j(x_1)) = 1 + x_1 POL(minus(x_1, x_2)) = x_1 + x_2 POL(opp(x_1)) = x_1 POL(plus(x_1, x_2)) = x_1 + x_2 POL(times(x_1, x_2)) = x_1 + x_1*x_2 + x_2 ---------------------------------------- (56) Obligation: The TRS P consists of the following rules: TIMES(times(0(x), y), ext) -> TIMES(x, y) TIMES(0(x), y) -> TIMES(x, y) TIMES(times(S, x), ext) -> TIMES(S, ext) TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) The set E# consists of the following equations: TIMES(times(x, y), z) == TIMES(x, times(y, z)) TIMES(x, y) == TIMES(y, x) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (57) EDPPoloProof (EQUIVALENT) 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. TIMES(times(0(x), y), ext) -> TIMES(x, y) TIMES(0(x), y) -> TIMES(x, y) The remaining Dependency Pairs were at least non-strictly oriented. TIMES(times(S, x), ext) -> TIMES(S, ext) TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) With the implicit AFS we had to orient the following set of usable rules of R non-strictly. times(S, x) -> S times(times(S, x), ext) -> times(S, ext) times(1(x), y) -> plus(0(times(x, y)), y) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(j(x), y) -> minus(0(times(x, y)), y) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) times(0(x), y) -> 0(times(x, y)) 0(S) -> S plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(0(x), 0(y)) -> 0(plus(x, y)) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(1(x), j(y)) -> 0(plus(x, y)) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(S, x) -> x opp(1(x)) -> j(opp(x)) opp(0(x)) -> 0(opp(x)) opp(S) -> S opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) We had to orient the following equations of E# equivalently. TIMES(times(x, y), z) == TIMES(x, times(y, z)) TIMES(x, y) == TIMES(y, x) With the implicit AFS we had to orient the following usable equations of E equivalently. times(x, y) == times(y, x) times(times(x, y), z) == times(x, times(y, z)) plus(plus(x, y), z) == plus(x, plus(y, z)) plus(x, y) == plus(y, x) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0(x_1)) = 1 + x_1 POL(1(x_1)) = 1 + x_1 POL(S) = 0 POL(TIMES(x_1, x_2)) = x_1 + x_1*x_2 + x_2 POL(j(x_1)) = 1 + x_1 POL(minus(x_1, x_2)) = x_1 + x_2 POL(opp(x_1)) = x_1 POL(plus(x_1, x_2)) = x_1 + x_2 POL(times(x_1, x_2)) = x_1 + x_1*x_2 + x_2 ---------------------------------------- (58) Obligation: The TRS P consists of the following rules: TIMES(times(S, x), ext) -> TIMES(S, ext) TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) The set E# consists of the following equations: TIMES(times(x, y), z) == TIMES(x, times(y, z)) TIMES(x, y) == TIMES(y, x) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (59) EDPPoloProof (EQUIVALENT) We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. TIMES(times(S, x), ext) -> TIMES(S, ext) TIMES(times(0(x), y), ext) -> TIMES(0(times(x, y)), ext) With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 0(S) -> S times(S, x) -> S times(times(S, x), ext) -> times(S, ext) times(1(x), y) -> plus(0(times(x, y)), y) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(j(x), y) -> minus(0(times(x, y)), y) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) times(0(x), y) -> 0(times(x, y)) minus(x, y) -> plus(opp(y), x) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(0(x), 0(y)) -> 0(plus(x, y)) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(1(x), j(y)) -> 0(plus(x, y)) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(S, x) -> x opp(1(x)) -> j(opp(x)) opp(0(x)) -> 0(opp(x)) opp(S) -> S opp(j(x)) -> 1(opp(x)) We had to orient the following equations of E# equivalently. TIMES(times(x, y), z) == TIMES(x, times(y, z)) TIMES(x, y) == TIMES(y, x) With the implicit AFS we had to orient the following usable equations of E equivalently. times(x, y) == times(y, x) times(times(x, y), z) == times(x, times(y, z)) plus(plus(x, y), z) == plus(x, plus(y, z)) plus(x, y) == plus(y, x) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0(x_1)) = 3 POL(1(x_1)) = 2 POL(S) = 3 POL(TIMES(x_1, x_2)) = 3*x_1 + 3*x_2 POL(j(x_1)) = 2 POL(minus(x_1, x_2)) = 2 + x_1 + x_2 POL(opp(x_1)) = 2 + x_1 POL(plus(x_1, x_2)) = x_1 + x_2 POL(times(x_1, x_2)) = 3 + x_1 + x_2 ---------------------------------------- (60) Obligation: P is empty. The TRS R consists of the following rules: 0(S) -> S plus(S, x) -> x plus(0(x), 0(y)) -> 0(plus(x, y)) plus(0(x), 1(y)) -> 1(plus(x, y)) plus(0(x), j(y)) -> j(plus(x, y)) plus(1(x), 1(y)) -> j(plus(1(S), plus(x, y))) plus(j(x), j(y)) -> 1(plus(j(S), plus(x, y))) plus(1(x), j(y)) -> 0(plus(x, y)) opp(S) -> S opp(0(x)) -> 0(opp(x)) opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) minus(x, y) -> plus(opp(y), x) times(S, x) -> S times(0(x), y) -> 0(times(x, y)) times(1(x), y) -> plus(0(times(x, y)), y) times(j(x), y) -> minus(0(times(x, y)), y) sign(x) -> if_sign(x, S) if_sign(S, x) -> x if_sign(0(x), y) -> if_sign(x, y) if_sign(1(x), y) -> if_sign(x, 1(S)) if_sign(j(x), y) -> if_sign(x, j(S)) abs(x) -> if_abs(x, x, S) if_abs(0(x), y, z) -> if_abs(x, y, z) if_abs(1(x), y, z) -> if_abs(x, y, 1(S)) if_abs(j(x), y, z) -> if_abs(x, y, j(S)) if_abs(S, x, S) -> S if_abs(S, x, 1(S)) -> x if_abs(S, x, j(S)) -> opp(x) min(x, y) -> if_min(minus(abs(y), abs(x)), x, y, S) min'(x, y) -> if_min(minus(abs(1(y)), abs(1(x))), x, y, S) min''(x, y) -> if_min(minus(abs(j(y)), abs(j(x))), x, y, S) if_min(0(x), y, z, u) -> if_min(x, y, z, u) if_min(1(x), y, z, u) -> if_min(x, y, z, 1(S)) if_min(j(x), y, z, u) -> if_min(x, y, z, j(S)) if_min(S, x, y, S) -> x if_min(S, x, y, 1(S)) -> x if_min(S, x, y, j(S)) -> y plus(plus(0(x), 0(y)), ext) -> plus(0(plus(x, y)), ext) plus(plus(0(x), 1(y)), ext) -> plus(1(plus(x, y)), ext) plus(plus(0(x), j(y)), ext) -> plus(j(plus(x, y)), ext) plus(plus(1(x), 1(y)), ext) -> plus(j(plus(1(S), plus(x, y))), ext) plus(plus(j(x), j(y)), ext) -> plus(1(plus(j(S), plus(x, y))), ext) plus(plus(1(x), j(y)), ext) -> plus(0(plus(x, y)), ext) times(times(S, x), ext) -> times(S, ext) times(times(0(x), y), ext) -> times(0(times(x, y)), ext) times(times(1(x), y), ext) -> times(plus(0(times(x, y)), y), ext) times(times(j(x), y), ext) -> times(minus(0(times(x, y)), y), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) times(x, y) == times(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) times(times(x, y), z) == times(x, times(y, z)) The set E# consists of the following equations: TIMES(times(x, y), z) == TIMES(x, times(y, z)) TIMES(x, y) == TIMES(y, x) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (61) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,E#,R,E) chain. ---------------------------------------- (62) YES