YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern myis(a,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 33 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) PiDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) PiDP (10) PiDPToQDPProof [SOUND, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) PiDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) PiDP (17) PiDPToQDPProof [SOUND, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) PiDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) PiDP (24) PiDPToQDPProof [SOUND, 0 ms] (25) QDP (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] (27) YES (28) PiDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) PiDP (31) PiDPToQDPProof [EQUIVALENT, 0 ms] (32) QDP (33) QDPSizeChangeProof [EQUIVALENT, 0 ms] (34) YES (35) PiDP (36) PiDPToQDPProof [SOUND, 0 ms] (37) QDP (38) QDPSizeChangeProof [EQUIVALENT, 0 ms] (39) YES ---------------------------------------- (0) Obligation: Clauses: myis(Z, X) :- evaluate(X, Z). evaluate(+(X, Y), Z) :- ','(evaluate(X, X1), ','(evaluate(Y, Y1), add(X1, Y1, Z))). evaluate(-(X, Y), Z) :- ','(evaluate(X, X1), ','(evaluate(Y, Y1), sub(X1, Y1, Z))). evaluate(*(X, Y), Z) :- ','(evaluate(X, X1), ','(evaluate(Y, Y1), mult(X1, Y1, Z))). evaluate(X, X) :- myinteger(X). myinteger(s(X)) :- myinteger(X). myinteger(0). add(s(X), Y, s(Z)) :- add(X, Y, Z). add(0, X, X). sub(s(X), s(Y), Z) :- sub(X, Y, Z). sub(X, 0, X). mult(s(X), Y, R) :- ','(mult(X, Y, Z), add(Y, Z, R)). mult(0, Y, 0). notEq(s(X), s(Y)) :- notEq(X, Y). notEq(s(X), 0). notEq(0, s(X)). lt(s(X), s(Y)) :- lt(X, Y). lt(0, s(Y)). gt(s(X), s(Y)) :- gt(X, Y). gt(s(X), 0). le(s(X), s(Y)) :- le(X, Y). le(0, s(Y)). le(0, 0). Query: myis(a,g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(myis Z X)", "(evaluate X Z)" ], [ "(evaluate (+ X Y) Z)", "(',' (evaluate X X1) (',' (evaluate Y Y1) (add X1 Y1 Z)))" ], [ "(evaluate (- X Y) Z)", "(',' (evaluate X X1) (',' (evaluate Y Y1) (sub X1 Y1 Z)))" ], [ "(evaluate (* X Y) Z)", "(',' (evaluate X X1) (',' (evaluate Y Y1) (mult X1 Y1 Z)))" ], [ "(evaluate X X)", "(myinteger X)" ], [ "(myinteger (s X))", "(myinteger X)" ], [ "(myinteger (0))", null ], [ "(add (s X) Y (s Z))", "(add X Y Z)" ], [ "(add (0) X X)", null ], [ "(sub (s X) (s Y) Z)", "(sub X Y Z)" ], [ "(sub X (0) X)", null ], [ "(mult (s X) Y R)", "(',' (mult X Y Z) (add Y Z R))" ], [ "(mult (0) Y (0))", null ], [ "(notEq (s X) (s Y))", "(notEq X Y)" ], [ "(notEq (s X) (0))", null ], [ "(notEq (0) (s X))", null ], [ "(lt (s X) (s Y))", "(lt X Y)" ], [ "(lt (0) (s Y))", null ], [ "(gt (s X) (s Y))", "(gt X Y)" ], [ "(gt (s X) (0))", null ], [ "(le (s X) (s Y))", "(le X Y)" ], [ "(le (0) (s Y))", null ], [ "(le (0) (0))", null ] ] }, "graph": { "nodes": { "type": "Nodes", "790": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (evaluate T123 X164) (mult T128 X164 T125))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T123", "T128" ], "free": ["X164"], "exprvars": [] } }, "750": { "goal": [{ "clause": 2, "scope": 2, "term": "(evaluate T6 T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "630": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (evaluate T20 X25) (',' (evaluate T21 X26) (add X25 X26 T23)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21" ], "free": [ "X25", "X26" ], "exprvars": [] } }, "751": { "goal": [ { "clause": 3, "scope": 2, "term": "(evaluate T6 T7)" }, { "clause": 4, "scope": 2, "term": "(evaluate T6 T7)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "950": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "951": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "952": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "755": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (evaluate T71 X94) (',' (evaluate T72 X95) (sub X94 X95 T74)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T71", "T72" ], "free": [ "X94", "X95" ], "exprvars": [] } }, "832": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (mult T151 T152 X210) (add T152 X210 T154))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T151", "T152" ], "free": ["X210"], "exprvars": [] } }, "953": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "756": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "833": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "834": { "goal": [{ "clause": -1, "scope": -1, "term": "(mult T151 T152 X210)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T151", "T152" ], "free": ["X210"], "exprvars": [] } }, "835": { "goal": [{ "clause": -1, "scope": -1, "term": "(add T152 T157 T154)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T152", "T157" ], "free": [], "exprvars": [] } }, "759": { "goal": [{ "clause": -1, "scope": -1, "term": "(evaluate T71 X94)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T71"], "free": ["X94"], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(myis T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "760": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (evaluate T72 X95) (sub T77 X95 T74))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T72", "T77" ], "free": ["X95"], "exprvars": [] } }, "763": { "goal": [{ "clause": -1, "scope": -1, "term": "(evaluate T72 X95)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T72"], "free": ["X95"], "exprvars": [] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(myis T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T2"], "free": [], "exprvars": [] } }, "765": { "goal": [{ "clause": -1, "scope": -1, "term": "(sub T77 T82 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T77", "T82" ], "free": [], "exprvars": [] } }, "842": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "7": { "goal": [{ "clause": -1, "scope": -1, "term": "(evaluate T6 T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "843": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "723": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "800": { "goal": [{ "clause": -1, "scope": -1, "term": "(evaluate T123 X164)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T123"], "free": ["X164"], "exprvars": [] } }, "844": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "9": { "goal": [ { "clause": 1, "scope": 2, "term": "(evaluate T6 T7)" }, { "clause": 2, "scope": 2, "term": "(evaluate T6 T7)" }, { "clause": 3, "scope": 2, "term": "(evaluate T6 T7)" }, { "clause": 4, "scope": 2, "term": "(evaluate T6 T7)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "801": { "goal": [{ "clause": -1, "scope": -1, "term": "(mult T128 T133 T125)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T128", "T133" ], "free": [], "exprvars": [] } }, "769": { "goal": [ { "clause": 9, "scope": 4, "term": "(sub T77 T82 T74)" }, { "clause": 10, "scope": 4, "term": "(sub T77 T82 T74)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T77", "T82" ], "free": [], "exprvars": [] } }, "726": { "goal": [{ "clause": -1, "scope": -1, "term": "(evaluate T20 X25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T20"], "free": ["X25"], "exprvars": [] } }, "727": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (evaluate T21 X26) (add T26 X26 T23))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T21", "T26" ], "free": ["X26"], "exprvars": [] } }, "806": { "goal": [ { "clause": 11, "scope": 5, "term": "(mult T128 T133 T125)" }, { "clause": 12, "scope": 5, "term": "(mult T128 T133 T125)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T128", "T133" ], "free": [], "exprvars": [] } }, "770": { "goal": [{ "clause": 9, "scope": 4, "term": "(sub T77 T82 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T77", "T82" ], "free": [], "exprvars": [] } }, "771": { "goal": [{ "clause": 10, "scope": 4, "term": "(sub T77 T82 T74)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T77", "T82" ], "free": [], "exprvars": [] } }, "730": { "goal": [{ "clause": -1, "scope": -1, "term": "(evaluate T21 X26)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T21"], "free": ["X26"], "exprvars": [] } }, "774": { "goal": [{ "clause": -1, "scope": -1, "term": "(sub T100 T101 T103)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T100", "T101" ], "free": [], "exprvars": [] } }, "731": { "goal": [{ "clause": -1, "scope": -1, "term": "(add T26 T31 T23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T26", "T31" ], "free": [], "exprvars": [] } }, "775": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "776": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "777": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "734": { "goal": [ { "clause": 7, "scope": 3, "term": "(add T26 T31 T23)" }, { "clause": 8, "scope": 3, "term": "(add T26 T31 T23)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T26", "T31" ], "free": [], "exprvars": [] } }, "778": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "811": { "goal": [{ "clause": 11, "scope": 5, "term": "(mult T128 T133 T125)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T128", "T133" ], "free": [], "exprvars": [] } }, "779": { "goal": [{ "clause": 3, "scope": 2, "term": "(evaluate T6 T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "812": { "goal": [{ "clause": 12, "scope": 5, "term": "(mult T128 T133 T125)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T128", "T133" ], "free": [], "exprvars": [] } }, "736": { "goal": [{ "clause": 7, "scope": 3, "term": "(add T26 T31 T23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T26", "T31" ], "free": [], "exprvars": [] } }, "737": { "goal": [{ "clause": 8, "scope": 3, "term": "(add T26 T31 T23)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T26", "T31" ], "free": [], "exprvars": [] } }, "780": { "goal": [{ "clause": 4, "scope": 2, "term": "(evaluate T6 T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "782": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (evaluate T122 X163) (',' (evaluate T123 X164) (mult X163 X164 T125)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T122", "T123" ], "free": [ "X163", "X164" ], "exprvars": [] } }, "783": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "102": { "goal": [{ "clause": 1, "scope": 2, "term": "(evaluate T6 T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "740": { "goal": [{ "clause": -1, "scope": -1, "term": "(add T49 T50 T52)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T49", "T50" ], "free": [], "exprvars": [] } }, "103": { "goal": [ { "clause": 2, "scope": 2, "term": "(evaluate T6 T7)" }, { "clause": 3, "scope": 2, "term": "(evaluate T6 T7)" }, { "clause": 4, "scope": 2, "term": "(evaluate T6 T7)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "741": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "941": { "goal": [{ "clause": -1, "scope": -1, "term": "(myinteger T168)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T168"], "free": [], "exprvars": [] } }, "744": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "942": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "745": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "789": { "goal": [{ "clause": -1, "scope": -1, "term": "(evaluate T122 X163)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T122"], "free": ["X163"], "exprvars": [] } }, "943": { "goal": [ { "clause": 5, "scope": 6, "term": "(myinteger T168)" }, { "clause": 6, "scope": 6, "term": "(myinteger T168)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T168"], "free": [], "exprvars": [] } }, "746": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "944": { "goal": [{ "clause": 5, "scope": 6, "term": "(myinteger T168)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T168"], "free": [], "exprvars": [] } }, "945": { "goal": [{ "clause": 6, "scope": 6, "term": "(myinteger T168)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T168"], "free": [], "exprvars": [] } }, "949": { "goal": [{ "clause": -1, "scope": -1, "term": "(myinteger T174)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T174"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 6, "label": "CASE" }, { "from": 6, "to": 7, "label": "ONLY EVAL with clause\nmyis(X4, X5) :- evaluate(X5, X4).\nand substitutionT1 -> T7,\nX4 -> T7,\nT2 -> T6,\nX5 -> T6,\nT5 -> T7" }, { "from": 7, "to": 9, "label": "CASE" }, { "from": 9, "to": 102, "label": "PARALLEL" }, { "from": 9, "to": 103, "label": "PARALLEL" }, { "from": 102, "to": 630, "label": "EVAL with clause\nevaluate(+(X22, X23), X24) :- ','(evaluate(X22, X25), ','(evaluate(X23, X26), add(X25, X26, X24))).\nand substitutionX22 -> T20,\nX23 -> T21,\nT6 -> +(T20, T21),\nT7 -> T23,\nX24 -> T23,\nT22 -> T23" }, { "from": 102, "to": 723, "label": "EVAL-BACKTRACK" }, { "from": 103, "to": 750, "label": "PARALLEL" }, { "from": 103, "to": 751, "label": "PARALLEL" }, { "from": 630, "to": 726, "label": "SPLIT 1" }, { "from": 630, "to": 727, "label": "SPLIT 2\nnew knowledge:\nT20 is ground\nT26 is ground\nreplacements:X25 -> T26" }, { "from": 726, "to": 7, "label": "INSTANCE with matching:\nT6 -> T20\nT7 -> X25" }, { "from": 727, "to": 730, "label": "SPLIT 1" }, { "from": 727, "to": 731, "label": "SPLIT 2\nnew knowledge:\nT21 is ground\nT31 is ground\nreplacements:X26 -> T31" }, { "from": 730, "to": 7, "label": "INSTANCE with matching:\nT6 -> T21\nT7 -> X26" }, { "from": 731, "to": 734, "label": "CASE" }, { "from": 734, "to": 736, "label": "PARALLEL" }, { "from": 734, "to": 737, "label": "PARALLEL" }, { "from": 736, "to": 740, "label": "EVAL with clause\nadd(s(X66), X67, s(X68)) :- add(X66, X67, X68).\nand substitutionX66 -> T49,\nT26 -> s(T49),\nT31 -> T50,\nX67 -> T50,\nX68 -> T52,\nT23 -> s(T52),\nT51 -> T52" }, { "from": 736, "to": 741, "label": "EVAL-BACKTRACK" }, { "from": 737, "to": 744, "label": "EVAL with clause\nadd(0, X74, X74).\nand substitutionT26 -> 0,\nT31 -> T58,\nX74 -> T58,\nT23 -> T58" }, { "from": 737, "to": 745, "label": "EVAL-BACKTRACK" }, { "from": 740, "to": 731, "label": "INSTANCE with matching:\nT26 -> T49\nT31 -> T50\nT23 -> T52" }, { "from": 744, "to": 746, "label": "SUCCESS" }, { "from": 750, "to": 755, "label": "EVAL with clause\nevaluate(-(X91, X92), X93) :- ','(evaluate(X91, X94), ','(evaluate(X92, X95), sub(X94, X95, X93))).\nand substitutionX91 -> T71,\nX92 -> T72,\nT6 -> -(T71, T72),\nT7 -> T74,\nX93 -> T74,\nT73 -> T74" }, { "from": 750, "to": 756, "label": "EVAL-BACKTRACK" }, { "from": 751, "to": 779, "label": "PARALLEL" }, { "from": 751, "to": 780, "label": "PARALLEL" }, { "from": 755, "to": 759, "label": "SPLIT 1" }, { "from": 755, "to": 760, "label": "SPLIT 2\nnew knowledge:\nT71 is ground\nT77 is ground\nreplacements:X94 -> T77" }, { "from": 759, "to": 7, "label": "INSTANCE with matching:\nT6 -> T71\nT7 -> X94" }, { "from": 760, "to": 763, "label": "SPLIT 1" }, { "from": 760, "to": 765, "label": "SPLIT 2\nnew knowledge:\nT72 is ground\nT82 is ground\nreplacements:X95 -> T82" }, { "from": 763, "to": 7, "label": "INSTANCE with matching:\nT6 -> T72\nT7 -> X95" }, { "from": 765, "to": 769, "label": "CASE" }, { "from": 769, "to": 770, "label": "PARALLEL" }, { "from": 769, "to": 771, "label": "PARALLEL" }, { "from": 770, "to": 774, "label": "EVAL with clause\nsub(s(X135), s(X136), X137) :- sub(X135, X136, X137).\nand substitutionX135 -> T100,\nT77 -> s(T100),\nX136 -> T101,\nT82 -> s(T101),\nT74 -> T103,\nX137 -> T103,\nT102 -> T103" }, { "from": 770, "to": 775, "label": "EVAL-BACKTRACK" }, { "from": 771, "to": 776, "label": "EVAL with clause\nsub(X143, 0, X143).\nand substitutionT77 -> T109,\nX143 -> T109,\nT82 -> 0,\nT74 -> T109" }, { "from": 771, "to": 777, "label": "EVAL-BACKTRACK" }, { "from": 774, "to": 765, "label": "INSTANCE with matching:\nT77 -> T100\nT82 -> T101\nT74 -> T103" }, { "from": 776, "to": 778, "label": "SUCCESS" }, { "from": 779, "to": 782, "label": "EVAL with clause\nevaluate(*(X160, X161), X162) :- ','(evaluate(X160, X163), ','(evaluate(X161, X164), mult(X163, X164, X162))).\nand substitutionX160 -> T122,\nX161 -> T123,\nT6 -> *(T122, T123),\nT7 -> T125,\nX162 -> T125,\nT124 -> T125" }, { "from": 779, "to": 783, "label": "EVAL-BACKTRACK" }, { "from": 780, "to": 941, "label": "EVAL with clause\nevaluate(X229, X229) :- myinteger(X229).\nand substitutionT6 -> T168,\nX229 -> T168,\nT7 -> T168" }, { "from": 780, "to": 942, "label": "EVAL-BACKTRACK" }, { "from": 782, "to": 789, "label": "SPLIT 1" }, { "from": 782, "to": 790, "label": "SPLIT 2\nnew knowledge:\nT122 is ground\nT128 is ground\nreplacements:X163 -> T128" }, { "from": 789, "to": 7, "label": "INSTANCE with matching:\nT6 -> T122\nT7 -> X163" }, { "from": 790, "to": 800, "label": "SPLIT 1" }, { "from": 790, "to": 801, "label": "SPLIT 2\nnew knowledge:\nT123 is ground\nT133 is ground\nreplacements:X164 -> T133" }, { "from": 800, "to": 7, "label": "INSTANCE with matching:\nT6 -> T123\nT7 -> X164" }, { "from": 801, "to": 806, "label": "CASE" }, { "from": 806, "to": 811, "label": "PARALLEL" }, { "from": 806, "to": 812, "label": "PARALLEL" }, { "from": 811, "to": 832, "label": "EVAL with clause\nmult(s(X207), X208, X209) :- ','(mult(X207, X208, X210), add(X208, X210, X209)).\nand substitutionX207 -> T151,\nT128 -> s(T151),\nT133 -> T152,\nX208 -> T152,\nT125 -> T154,\nX209 -> T154,\nT153 -> T154" }, { "from": 811, "to": 833, "label": "EVAL-BACKTRACK" }, { "from": 812, "to": 842, "label": "EVAL with clause\nmult(0, X226, 0).\nand substitutionT128 -> 0,\nT133 -> T165,\nX226 -> T165,\nT125 -> 0" }, { "from": 812, "to": 843, "label": "EVAL-BACKTRACK" }, { "from": 832, "to": 834, "label": "SPLIT 1" }, { "from": 832, "to": 835, "label": "SPLIT 2\nnew knowledge:\nT151 is ground\nT152 is ground\nT157 is ground\nreplacements:X210 -> T157" }, { "from": 834, "to": 801, "label": "INSTANCE with matching:\nT128 -> T151\nT133 -> T152\nT125 -> X210" }, { "from": 835, "to": 731, "label": "INSTANCE with matching:\nT26 -> T152\nT31 -> T157\nT23 -> T154" }, { "from": 842, "to": 844, "label": "SUCCESS" }, { "from": 941, "to": 943, "label": "CASE" }, { "from": 943, "to": 944, "label": "PARALLEL" }, { "from": 943, "to": 945, "label": "PARALLEL" }, { "from": 944, "to": 949, "label": "EVAL with clause\nmyinteger(s(X235)) :- myinteger(X235).\nand substitutionX235 -> T174,\nT168 -> s(T174)" }, { "from": 944, "to": 950, "label": "EVAL-BACKTRACK" }, { "from": 945, "to": 951, "label": "EVAL with clause\nmyinteger(0).\nand substitutionT168 -> 0" }, { "from": 945, "to": 952, "label": "EVAL-BACKTRACK" }, { "from": 949, "to": 941, "label": "INSTANCE with matching:\nT168 -> T174" }, { "from": 951, "to": 953, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: evaluateA(+(X1, X2), X3) :- evaluateA(X1, X4). evaluateA(+(X1, X2), X3) :- ','(evaluatecA(X1, X4), evaluateA(X2, X5)). evaluateA(+(X1, X2), X3) :- ','(evaluatecA(X1, X4), ','(evaluatecA(X2, X5), addB(X4, X5, X3))). evaluateA(-(X1, X2), X3) :- evaluateA(X1, X4). evaluateA(-(X1, X2), X3) :- ','(evaluatecA(X1, X4), evaluateA(X2, X5)). evaluateA(-(X1, X2), X3) :- ','(evaluatecA(X1, X4), ','(evaluatecA(X2, X5), subC(X4, X5, X3))). evaluateA(*(X1, X2), X3) :- evaluateA(X1, X4). evaluateA(*(X1, X2), X3) :- ','(evaluatecA(X1, X4), evaluateA(X2, X5)). evaluateA(*(X1, X2), X3) :- ','(evaluatecA(X1, X4), ','(evaluatecA(X2, X5), multD(X4, X5, X3))). evaluateA(X1, X1) :- myintegerE(X1). addB(s(X1), X2, s(X3)) :- addB(X1, X2, X3). subC(s(X1), s(X2), X3) :- subC(X1, X2, X3). multD(s(X1), X2, X3) :- multD(X1, X2, X4). multD(s(X1), X2, X3) :- ','(multcD(X1, X2, X4), addB(X2, X4, X3)). myintegerE(s(X1)) :- myintegerE(X1). myisF(X1, X2) :- evaluateA(X2, X1). Clauses: evaluatecA(+(X1, X2), X3) :- ','(evaluatecA(X1, X4), ','(evaluatecA(X2, X5), addcB(X4, X5, X3))). evaluatecA(-(X1, X2), X3) :- ','(evaluatecA(X1, X4), ','(evaluatecA(X2, X5), subcC(X4, X5, X3))). evaluatecA(*(X1, X2), X3) :- ','(evaluatecA(X1, X4), ','(evaluatecA(X2, X5), multcD(X4, X5, X3))). evaluatecA(X1, X1) :- myintegercE(X1). addcB(s(X1), X2, s(X3)) :- addcB(X1, X2, X3). addcB(0, X1, X1). subcC(s(X1), s(X2), X3) :- subcC(X1, X2, X3). subcC(X1, 0, X1). multcD(s(X1), X2, X3) :- ','(multcD(X1, X2, X4), addcB(X2, X4, X3)). multcD(0, X1, 0). myintegercE(s(X1)) :- myintegercE(X1). myintegercE(0). Afs: myisF(x1, x2) = myisF(x2) ---------------------------------------- (3) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: myisF_in_2: (f,b) evaluateA_in_2: (b,f) evaluatecA_in_2: (b,f) myintegercE_in_1: (b) multcD_in_3: (b,b,f) addcB_in_3: (b,b,f) subcC_in_3: (b,b,f) myintegerE_in_1: (b) multD_in_3: (b,b,f) addB_in_3: (b,b,f) subC_in_3: (b,b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: MYISF_IN_AG(X1, X2) -> U23_AG(X1, X2, evaluateA_in_ga(X2, X1)) MYISF_IN_AG(X1, X2) -> EVALUATEA_IN_GA(X2, X1) EVALUATEA_IN_GA(+(X1, X2), X3) -> U1_GA(X1, X2, X3, evaluateA_in_ga(X1, X4)) EVALUATEA_IN_GA(+(X1, X2), X3) -> EVALUATEA_IN_GA(X1, X4) EVALUATEA_IN_GA(+(X1, X2), X3) -> U2_GA(X1, X2, X3, evaluatecA_in_ga(X1, X4)) U2_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U3_GA(X1, X2, X3, evaluateA_in_ga(X2, X5)) U2_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> EVALUATEA_IN_GA(X2, X5) EVALUATEA_IN_GA(-(X1, X2), X3) -> U6_GA(X1, X2, X3, evaluateA_in_ga(X1, X4)) EVALUATEA_IN_GA(-(X1, X2), X3) -> EVALUATEA_IN_GA(X1, X4) EVALUATEA_IN_GA(-(X1, X2), X3) -> U7_GA(X1, X2, X3, evaluatecA_in_ga(X1, X4)) U7_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U8_GA(X1, X2, X3, evaluateA_in_ga(X2, X5)) U7_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> EVALUATEA_IN_GA(X2, X5) EVALUATEA_IN_GA(*(X1, X2), X3) -> U11_GA(X1, X2, X3, evaluateA_in_ga(X1, X4)) EVALUATEA_IN_GA(*(X1, X2), X3) -> EVALUATEA_IN_GA(X1, X4) EVALUATEA_IN_GA(*(X1, X2), X3) -> U12_GA(X1, X2, X3, evaluatecA_in_ga(X1, X4)) U12_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U13_GA(X1, X2, X3, evaluateA_in_ga(X2, X5)) U12_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> EVALUATEA_IN_GA(X2, X5) EVALUATEA_IN_GA(X1, X1) -> U16_GA(X1, myintegerE_in_g(X1)) EVALUATEA_IN_GA(X1, X1) -> MYINTEGERE_IN_G(X1) MYINTEGERE_IN_G(s(X1)) -> U22_G(X1, myintegerE_in_g(X1)) MYINTEGERE_IN_G(s(X1)) -> MYINTEGERE_IN_G(X1) U12_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U14_GA(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U14_GA(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U15_GA(X1, X2, X3, multD_in_gga(X4, X5, X3)) U14_GA(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> MULTD_IN_GGA(X4, X5, X3) MULTD_IN_GGA(s(X1), X2, X3) -> U19_GGA(X1, X2, X3, multD_in_gga(X1, X2, X4)) MULTD_IN_GGA(s(X1), X2, X3) -> MULTD_IN_GGA(X1, X2, X4) MULTD_IN_GGA(s(X1), X2, X3) -> U20_GGA(X1, X2, X3, multcD_in_gga(X1, X2, X4)) U20_GGA(X1, X2, X3, multcD_out_gga(X1, X2, X4)) -> U21_GGA(X1, X2, X3, addB_in_gga(X2, X4, X3)) U20_GGA(X1, X2, X3, multcD_out_gga(X1, X2, X4)) -> ADDB_IN_GGA(X2, X4, X3) ADDB_IN_GGA(s(X1), X2, s(X3)) -> U17_GGA(X1, X2, X3, addB_in_gga(X1, X2, X3)) ADDB_IN_GGA(s(X1), X2, s(X3)) -> ADDB_IN_GGA(X1, X2, X3) U7_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U9_GA(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U9_GA(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U10_GA(X1, X2, X3, subC_in_gga(X4, X5, X3)) U9_GA(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> SUBC_IN_GGA(X4, X5, X3) SUBC_IN_GGA(s(X1), s(X2), X3) -> U18_GGA(X1, X2, X3, subC_in_gga(X1, X2, X3)) SUBC_IN_GGA(s(X1), s(X2), X3) -> SUBC_IN_GGA(X1, X2, X3) U2_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U4_GA(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U4_GA(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U5_GA(X1, X2, X3, addB_in_gga(X4, X5, X3)) U4_GA(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> ADDB_IN_GGA(X4, X5, X3) The TRS R consists of the following rules: evaluatecA_in_ga(+(X1, X2), X3) -> U25_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(-(X1, X2), X3) -> U28_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(*(X1, X2), X3) -> U31_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(X1, X1) -> U34_ga(X1, myintegercE_in_g(X1)) myintegercE_in_g(s(X1)) -> U39_g(X1, myintegercE_in_g(X1)) myintegercE_in_g(0) -> myintegercE_out_g(0) U39_g(X1, myintegercE_out_g(X1)) -> myintegercE_out_g(s(X1)) U34_ga(X1, myintegercE_out_g(X1)) -> evaluatecA_out_ga(X1, X1) U31_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U32_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U32_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U33_ga(X1, X2, X3, multcD_in_gga(X4, X5, X3)) multcD_in_gga(s(X1), X2, X3) -> U37_gga(X1, X2, X3, multcD_in_gga(X1, X2, X4)) multcD_in_gga(0, X1, 0) -> multcD_out_gga(0, X1, 0) U37_gga(X1, X2, X3, multcD_out_gga(X1, X2, X4)) -> U38_gga(X1, X2, X3, addcB_in_gga(X2, X4, X3)) addcB_in_gga(s(X1), X2, s(X3)) -> U35_gga(X1, X2, X3, addcB_in_gga(X1, X2, X3)) addcB_in_gga(0, X1, X1) -> addcB_out_gga(0, X1, X1) U35_gga(X1, X2, X3, addcB_out_gga(X1, X2, X3)) -> addcB_out_gga(s(X1), X2, s(X3)) U38_gga(X1, X2, X3, addcB_out_gga(X2, X4, X3)) -> multcD_out_gga(s(X1), X2, X3) U33_ga(X1, X2, X3, multcD_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(*(X1, X2), X3) U28_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U29_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U29_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U30_ga(X1, X2, X3, subcC_in_gga(X4, X5, X3)) subcC_in_gga(s(X1), s(X2), X3) -> U36_gga(X1, X2, X3, subcC_in_gga(X1, X2, X3)) subcC_in_gga(X1, 0, X1) -> subcC_out_gga(X1, 0, X1) U36_gga(X1, X2, X3, subcC_out_gga(X1, X2, X3)) -> subcC_out_gga(s(X1), s(X2), X3) U30_ga(X1, X2, X3, subcC_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(-(X1, X2), X3) U25_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U26_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U26_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U27_ga(X1, X2, X3, addcB_in_gga(X4, X5, X3)) U27_ga(X1, X2, X3, addcB_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(+(X1, X2), X3) The argument filtering Pi contains the following mapping: evaluateA_in_ga(x1, x2) = evaluateA_in_ga(x1) +(x1, x2) = +(x1, x2) evaluatecA_in_ga(x1, x2) = evaluatecA_in_ga(x1) U25_ga(x1, x2, x3, x4) = U25_ga(x1, x2, x4) -(x1, x2) = -(x1, x2) U28_ga(x1, x2, x3, x4) = U28_ga(x1, x2, x4) *(x1, x2) = *(x1, x2) U31_ga(x1, x2, x3, x4) = U31_ga(x1, x2, x4) U34_ga(x1, x2) = U34_ga(x1, x2) myintegercE_in_g(x1) = myintegercE_in_g(x1) s(x1) = s(x1) U39_g(x1, x2) = U39_g(x1, x2) 0 = 0 myintegercE_out_g(x1) = myintegercE_out_g(x1) evaluatecA_out_ga(x1, x2) = evaluatecA_out_ga(x1, x2) U32_ga(x1, x2, x3, x4, x5) = U32_ga(x1, x2, x4, x5) U33_ga(x1, x2, x3, x4) = U33_ga(x1, x2, x4) multcD_in_gga(x1, x2, x3) = multcD_in_gga(x1, x2) U37_gga(x1, x2, x3, x4) = U37_gga(x1, x2, x4) multcD_out_gga(x1, x2, x3) = multcD_out_gga(x1, x2, x3) U38_gga(x1, x2, x3, x4) = U38_gga(x1, x2, x4) addcB_in_gga(x1, x2, x3) = addcB_in_gga(x1, x2) U35_gga(x1, x2, x3, x4) = U35_gga(x1, x2, x4) addcB_out_gga(x1, x2, x3) = addcB_out_gga(x1, x2, x3) U29_ga(x1, x2, x3, x4, x5) = U29_ga(x1, x2, x4, x5) U30_ga(x1, x2, x3, x4) = U30_ga(x1, x2, x4) subcC_in_gga(x1, x2, x3) = subcC_in_gga(x1, x2) U36_gga(x1, x2, x3, x4) = U36_gga(x1, x2, x4) subcC_out_gga(x1, x2, x3) = subcC_out_gga(x1, x2, x3) U26_ga(x1, x2, x3, x4, x5) = U26_ga(x1, x2, x4, x5) U27_ga(x1, x2, x3, x4) = U27_ga(x1, x2, x4) myintegerE_in_g(x1) = myintegerE_in_g(x1) multD_in_gga(x1, x2, x3) = multD_in_gga(x1, x2) addB_in_gga(x1, x2, x3) = addB_in_gga(x1, x2) subC_in_gga(x1, x2, x3) = subC_in_gga(x1, x2) MYISF_IN_AG(x1, x2) = MYISF_IN_AG(x2) U23_AG(x1, x2, x3) = U23_AG(x2, x3) EVALUATEA_IN_GA(x1, x2) = EVALUATEA_IN_GA(x1) U1_GA(x1, x2, x3, x4) = U1_GA(x1, x2, x4) U2_GA(x1, x2, x3, x4) = U2_GA(x1, x2, x4) U3_GA(x1, x2, x3, x4) = U3_GA(x1, x2, x4) U6_GA(x1, x2, x3, x4) = U6_GA(x1, x2, x4) U7_GA(x1, x2, x3, x4) = U7_GA(x1, x2, x4) U8_GA(x1, x2, x3, x4) = U8_GA(x1, x2, x4) U11_GA(x1, x2, x3, x4) = U11_GA(x1, x2, x4) U12_GA(x1, x2, x3, x4) = U12_GA(x1, x2, x4) U13_GA(x1, x2, x3, x4) = U13_GA(x1, x2, x4) U16_GA(x1, x2) = U16_GA(x1, x2) MYINTEGERE_IN_G(x1) = MYINTEGERE_IN_G(x1) U22_G(x1, x2) = U22_G(x1, x2) U14_GA(x1, x2, x3, x4, x5) = U14_GA(x1, x2, x4, x5) U15_GA(x1, x2, x3, x4) = U15_GA(x1, x2, x4) MULTD_IN_GGA(x1, x2, x3) = MULTD_IN_GGA(x1, x2) U19_GGA(x1, x2, x3, x4) = U19_GGA(x1, x2, x4) U20_GGA(x1, x2, x3, x4) = U20_GGA(x1, x2, x4) U21_GGA(x1, x2, x3, x4) = U21_GGA(x1, x2, x4) ADDB_IN_GGA(x1, x2, x3) = ADDB_IN_GGA(x1, x2) U17_GGA(x1, x2, x3, x4) = U17_GGA(x1, x2, x4) U9_GA(x1, x2, x3, x4, x5) = U9_GA(x1, x2, x4, x5) U10_GA(x1, x2, x3, x4) = U10_GA(x1, x2, x4) SUBC_IN_GGA(x1, x2, x3) = SUBC_IN_GGA(x1, x2) U18_GGA(x1, x2, x3, x4) = U18_GGA(x1, x2, x4) U4_GA(x1, x2, x3, x4, x5) = U4_GA(x1, x2, x4, x5) U5_GA(x1, x2, x3, x4) = U5_GA(x1, x2, x4) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: MYISF_IN_AG(X1, X2) -> U23_AG(X1, X2, evaluateA_in_ga(X2, X1)) MYISF_IN_AG(X1, X2) -> EVALUATEA_IN_GA(X2, X1) EVALUATEA_IN_GA(+(X1, X2), X3) -> U1_GA(X1, X2, X3, evaluateA_in_ga(X1, X4)) EVALUATEA_IN_GA(+(X1, X2), X3) -> EVALUATEA_IN_GA(X1, X4) EVALUATEA_IN_GA(+(X1, X2), X3) -> U2_GA(X1, X2, X3, evaluatecA_in_ga(X1, X4)) U2_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U3_GA(X1, X2, X3, evaluateA_in_ga(X2, X5)) U2_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> EVALUATEA_IN_GA(X2, X5) EVALUATEA_IN_GA(-(X1, X2), X3) -> U6_GA(X1, X2, X3, evaluateA_in_ga(X1, X4)) EVALUATEA_IN_GA(-(X1, X2), X3) -> EVALUATEA_IN_GA(X1, X4) EVALUATEA_IN_GA(-(X1, X2), X3) -> U7_GA(X1, X2, X3, evaluatecA_in_ga(X1, X4)) U7_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U8_GA(X1, X2, X3, evaluateA_in_ga(X2, X5)) U7_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> EVALUATEA_IN_GA(X2, X5) EVALUATEA_IN_GA(*(X1, X2), X3) -> U11_GA(X1, X2, X3, evaluateA_in_ga(X1, X4)) EVALUATEA_IN_GA(*(X1, X2), X3) -> EVALUATEA_IN_GA(X1, X4) EVALUATEA_IN_GA(*(X1, X2), X3) -> U12_GA(X1, X2, X3, evaluatecA_in_ga(X1, X4)) U12_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U13_GA(X1, X2, X3, evaluateA_in_ga(X2, X5)) U12_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> EVALUATEA_IN_GA(X2, X5) EVALUATEA_IN_GA(X1, X1) -> U16_GA(X1, myintegerE_in_g(X1)) EVALUATEA_IN_GA(X1, X1) -> MYINTEGERE_IN_G(X1) MYINTEGERE_IN_G(s(X1)) -> U22_G(X1, myintegerE_in_g(X1)) MYINTEGERE_IN_G(s(X1)) -> MYINTEGERE_IN_G(X1) U12_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U14_GA(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U14_GA(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U15_GA(X1, X2, X3, multD_in_gga(X4, X5, X3)) U14_GA(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> MULTD_IN_GGA(X4, X5, X3) MULTD_IN_GGA(s(X1), X2, X3) -> U19_GGA(X1, X2, X3, multD_in_gga(X1, X2, X4)) MULTD_IN_GGA(s(X1), X2, X3) -> MULTD_IN_GGA(X1, X2, X4) MULTD_IN_GGA(s(X1), X2, X3) -> U20_GGA(X1, X2, X3, multcD_in_gga(X1, X2, X4)) U20_GGA(X1, X2, X3, multcD_out_gga(X1, X2, X4)) -> U21_GGA(X1, X2, X3, addB_in_gga(X2, X4, X3)) U20_GGA(X1, X2, X3, multcD_out_gga(X1, X2, X4)) -> ADDB_IN_GGA(X2, X4, X3) ADDB_IN_GGA(s(X1), X2, s(X3)) -> U17_GGA(X1, X2, X3, addB_in_gga(X1, X2, X3)) ADDB_IN_GGA(s(X1), X2, s(X3)) -> ADDB_IN_GGA(X1, X2, X3) U7_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U9_GA(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U9_GA(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U10_GA(X1, X2, X3, subC_in_gga(X4, X5, X3)) U9_GA(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> SUBC_IN_GGA(X4, X5, X3) SUBC_IN_GGA(s(X1), s(X2), X3) -> U18_GGA(X1, X2, X3, subC_in_gga(X1, X2, X3)) SUBC_IN_GGA(s(X1), s(X2), X3) -> SUBC_IN_GGA(X1, X2, X3) U2_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U4_GA(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U4_GA(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U5_GA(X1, X2, X3, addB_in_gga(X4, X5, X3)) U4_GA(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> ADDB_IN_GGA(X4, X5, X3) The TRS R consists of the following rules: evaluatecA_in_ga(+(X1, X2), X3) -> U25_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(-(X1, X2), X3) -> U28_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(*(X1, X2), X3) -> U31_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(X1, X1) -> U34_ga(X1, myintegercE_in_g(X1)) myintegercE_in_g(s(X1)) -> U39_g(X1, myintegercE_in_g(X1)) myintegercE_in_g(0) -> myintegercE_out_g(0) U39_g(X1, myintegercE_out_g(X1)) -> myintegercE_out_g(s(X1)) U34_ga(X1, myintegercE_out_g(X1)) -> evaluatecA_out_ga(X1, X1) U31_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U32_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U32_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U33_ga(X1, X2, X3, multcD_in_gga(X4, X5, X3)) multcD_in_gga(s(X1), X2, X3) -> U37_gga(X1, X2, X3, multcD_in_gga(X1, X2, X4)) multcD_in_gga(0, X1, 0) -> multcD_out_gga(0, X1, 0) U37_gga(X1, X2, X3, multcD_out_gga(X1, X2, X4)) -> U38_gga(X1, X2, X3, addcB_in_gga(X2, X4, X3)) addcB_in_gga(s(X1), X2, s(X3)) -> U35_gga(X1, X2, X3, addcB_in_gga(X1, X2, X3)) addcB_in_gga(0, X1, X1) -> addcB_out_gga(0, X1, X1) U35_gga(X1, X2, X3, addcB_out_gga(X1, X2, X3)) -> addcB_out_gga(s(X1), X2, s(X3)) U38_gga(X1, X2, X3, addcB_out_gga(X2, X4, X3)) -> multcD_out_gga(s(X1), X2, X3) U33_ga(X1, X2, X3, multcD_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(*(X1, X2), X3) U28_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U29_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U29_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U30_ga(X1, X2, X3, subcC_in_gga(X4, X5, X3)) subcC_in_gga(s(X1), s(X2), X3) -> U36_gga(X1, X2, X3, subcC_in_gga(X1, X2, X3)) subcC_in_gga(X1, 0, X1) -> subcC_out_gga(X1, 0, X1) U36_gga(X1, X2, X3, subcC_out_gga(X1, X2, X3)) -> subcC_out_gga(s(X1), s(X2), X3) U30_ga(X1, X2, X3, subcC_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(-(X1, X2), X3) U25_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U26_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U26_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U27_ga(X1, X2, X3, addcB_in_gga(X4, X5, X3)) U27_ga(X1, X2, X3, addcB_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(+(X1, X2), X3) The argument filtering Pi contains the following mapping: evaluateA_in_ga(x1, x2) = evaluateA_in_ga(x1) +(x1, x2) = +(x1, x2) evaluatecA_in_ga(x1, x2) = evaluatecA_in_ga(x1) U25_ga(x1, x2, x3, x4) = U25_ga(x1, x2, x4) -(x1, x2) = -(x1, x2) U28_ga(x1, x2, x3, x4) = U28_ga(x1, x2, x4) *(x1, x2) = *(x1, x2) U31_ga(x1, x2, x3, x4) = U31_ga(x1, x2, x4) U34_ga(x1, x2) = U34_ga(x1, x2) myintegercE_in_g(x1) = myintegercE_in_g(x1) s(x1) = s(x1) U39_g(x1, x2) = U39_g(x1, x2) 0 = 0 myintegercE_out_g(x1) = myintegercE_out_g(x1) evaluatecA_out_ga(x1, x2) = evaluatecA_out_ga(x1, x2) U32_ga(x1, x2, x3, x4, x5) = U32_ga(x1, x2, x4, x5) U33_ga(x1, x2, x3, x4) = U33_ga(x1, x2, x4) multcD_in_gga(x1, x2, x3) = multcD_in_gga(x1, x2) U37_gga(x1, x2, x3, x4) = U37_gga(x1, x2, x4) multcD_out_gga(x1, x2, x3) = multcD_out_gga(x1, x2, x3) U38_gga(x1, x2, x3, x4) = U38_gga(x1, x2, x4) addcB_in_gga(x1, x2, x3) = addcB_in_gga(x1, x2) U35_gga(x1, x2, x3, x4) = U35_gga(x1, x2, x4) addcB_out_gga(x1, x2, x3) = addcB_out_gga(x1, x2, x3) U29_ga(x1, x2, x3, x4, x5) = U29_ga(x1, x2, x4, x5) U30_ga(x1, x2, x3, x4) = U30_ga(x1, x2, x4) subcC_in_gga(x1, x2, x3) = subcC_in_gga(x1, x2) U36_gga(x1, x2, x3, x4) = U36_gga(x1, x2, x4) subcC_out_gga(x1, x2, x3) = subcC_out_gga(x1, x2, x3) U26_ga(x1, x2, x3, x4, x5) = U26_ga(x1, x2, x4, x5) U27_ga(x1, x2, x3, x4) = U27_ga(x1, x2, x4) myintegerE_in_g(x1) = myintegerE_in_g(x1) multD_in_gga(x1, x2, x3) = multD_in_gga(x1, x2) addB_in_gga(x1, x2, x3) = addB_in_gga(x1, x2) subC_in_gga(x1, x2, x3) = subC_in_gga(x1, x2) MYISF_IN_AG(x1, x2) = MYISF_IN_AG(x2) U23_AG(x1, x2, x3) = U23_AG(x2, x3) EVALUATEA_IN_GA(x1, x2) = EVALUATEA_IN_GA(x1) U1_GA(x1, x2, x3, x4) = U1_GA(x1, x2, x4) U2_GA(x1, x2, x3, x4) = U2_GA(x1, x2, x4) U3_GA(x1, x2, x3, x4) = U3_GA(x1, x2, x4) U6_GA(x1, x2, x3, x4) = U6_GA(x1, x2, x4) U7_GA(x1, x2, x3, x4) = U7_GA(x1, x2, x4) U8_GA(x1, x2, x3, x4) = U8_GA(x1, x2, x4) U11_GA(x1, x2, x3, x4) = U11_GA(x1, x2, x4) U12_GA(x1, x2, x3, x4) = U12_GA(x1, x2, x4) U13_GA(x1, x2, x3, x4) = U13_GA(x1, x2, x4) U16_GA(x1, x2) = U16_GA(x1, x2) MYINTEGERE_IN_G(x1) = MYINTEGERE_IN_G(x1) U22_G(x1, x2) = U22_G(x1, x2) U14_GA(x1, x2, x3, x4, x5) = U14_GA(x1, x2, x4, x5) U15_GA(x1, x2, x3, x4) = U15_GA(x1, x2, x4) MULTD_IN_GGA(x1, x2, x3) = MULTD_IN_GGA(x1, x2) U19_GGA(x1, x2, x3, x4) = U19_GGA(x1, x2, x4) U20_GGA(x1, x2, x3, x4) = U20_GGA(x1, x2, x4) U21_GGA(x1, x2, x3, x4) = U21_GGA(x1, x2, x4) ADDB_IN_GGA(x1, x2, x3) = ADDB_IN_GGA(x1, x2) U17_GGA(x1, x2, x3, x4) = U17_GGA(x1, x2, x4) U9_GA(x1, x2, x3, x4, x5) = U9_GA(x1, x2, x4, x5) U10_GA(x1, x2, x3, x4) = U10_GA(x1, x2, x4) SUBC_IN_GGA(x1, x2, x3) = SUBC_IN_GGA(x1, x2) U18_GGA(x1, x2, x3, x4) = U18_GGA(x1, x2, x4) U4_GA(x1, x2, x3, x4, x5) = U4_GA(x1, x2, x4, x5) U5_GA(x1, x2, x3, x4) = U5_GA(x1, x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 5 SCCs with 26 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: SUBC_IN_GGA(s(X1), s(X2), X3) -> SUBC_IN_GGA(X1, X2, X3) The TRS R consists of the following rules: evaluatecA_in_ga(+(X1, X2), X3) -> U25_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(-(X1, X2), X3) -> U28_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(*(X1, X2), X3) -> U31_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(X1, X1) -> U34_ga(X1, myintegercE_in_g(X1)) myintegercE_in_g(s(X1)) -> U39_g(X1, myintegercE_in_g(X1)) myintegercE_in_g(0) -> myintegercE_out_g(0) U39_g(X1, myintegercE_out_g(X1)) -> myintegercE_out_g(s(X1)) U34_ga(X1, myintegercE_out_g(X1)) -> evaluatecA_out_ga(X1, X1) U31_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U32_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U32_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U33_ga(X1, X2, X3, multcD_in_gga(X4, X5, X3)) multcD_in_gga(s(X1), X2, X3) -> U37_gga(X1, X2, X3, multcD_in_gga(X1, X2, X4)) multcD_in_gga(0, X1, 0) -> multcD_out_gga(0, X1, 0) U37_gga(X1, X2, X3, multcD_out_gga(X1, X2, X4)) -> U38_gga(X1, X2, X3, addcB_in_gga(X2, X4, X3)) addcB_in_gga(s(X1), X2, s(X3)) -> U35_gga(X1, X2, X3, addcB_in_gga(X1, X2, X3)) addcB_in_gga(0, X1, X1) -> addcB_out_gga(0, X1, X1) U35_gga(X1, X2, X3, addcB_out_gga(X1, X2, X3)) -> addcB_out_gga(s(X1), X2, s(X3)) U38_gga(X1, X2, X3, addcB_out_gga(X2, X4, X3)) -> multcD_out_gga(s(X1), X2, X3) U33_ga(X1, X2, X3, multcD_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(*(X1, X2), X3) U28_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U29_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U29_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U30_ga(X1, X2, X3, subcC_in_gga(X4, X5, X3)) subcC_in_gga(s(X1), s(X2), X3) -> U36_gga(X1, X2, X3, subcC_in_gga(X1, X2, X3)) subcC_in_gga(X1, 0, X1) -> subcC_out_gga(X1, 0, X1) U36_gga(X1, X2, X3, subcC_out_gga(X1, X2, X3)) -> subcC_out_gga(s(X1), s(X2), X3) U30_ga(X1, X2, X3, subcC_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(-(X1, X2), X3) U25_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U26_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U26_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U27_ga(X1, X2, X3, addcB_in_gga(X4, X5, X3)) U27_ga(X1, X2, X3, addcB_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(+(X1, X2), X3) The argument filtering Pi contains the following mapping: +(x1, x2) = +(x1, x2) evaluatecA_in_ga(x1, x2) = evaluatecA_in_ga(x1) U25_ga(x1, x2, x3, x4) = U25_ga(x1, x2, x4) -(x1, x2) = -(x1, x2) U28_ga(x1, x2, x3, x4) = U28_ga(x1, x2, x4) *(x1, x2) = *(x1, x2) U31_ga(x1, x2, x3, x4) = U31_ga(x1, x2, x4) U34_ga(x1, x2) = U34_ga(x1, x2) myintegercE_in_g(x1) = myintegercE_in_g(x1) s(x1) = s(x1) U39_g(x1, x2) = U39_g(x1, x2) 0 = 0 myintegercE_out_g(x1) = myintegercE_out_g(x1) evaluatecA_out_ga(x1, x2) = evaluatecA_out_ga(x1, x2) U32_ga(x1, x2, x3, x4, x5) = U32_ga(x1, x2, x4, x5) U33_ga(x1, x2, x3, x4) = U33_ga(x1, x2, x4) multcD_in_gga(x1, x2, x3) = multcD_in_gga(x1, x2) U37_gga(x1, x2, x3, x4) = U37_gga(x1, x2, x4) multcD_out_gga(x1, x2, x3) = multcD_out_gga(x1, x2, x3) U38_gga(x1, x2, x3, x4) = U38_gga(x1, x2, x4) addcB_in_gga(x1, x2, x3) = addcB_in_gga(x1, x2) U35_gga(x1, x2, x3, x4) = U35_gga(x1, x2, x4) addcB_out_gga(x1, x2, x3) = addcB_out_gga(x1, x2, x3) U29_ga(x1, x2, x3, x4, x5) = U29_ga(x1, x2, x4, x5) U30_ga(x1, x2, x3, x4) = U30_ga(x1, x2, x4) subcC_in_gga(x1, x2, x3) = subcC_in_gga(x1, x2) U36_gga(x1, x2, x3, x4) = U36_gga(x1, x2, x4) subcC_out_gga(x1, x2, x3) = subcC_out_gga(x1, x2, x3) U26_ga(x1, x2, x3, x4, x5) = U26_ga(x1, x2, x4, x5) U27_ga(x1, x2, x3, x4) = U27_ga(x1, x2, x4) SUBC_IN_GGA(x1, x2, x3) = SUBC_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (9) Obligation: Pi DP problem: The TRS P consists of the following rules: SUBC_IN_GGA(s(X1), s(X2), X3) -> SUBC_IN_GGA(X1, X2, X3) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) SUBC_IN_GGA(x1, x2, x3) = SUBC_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (10) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: SUBC_IN_GGA(s(X1), s(X2)) -> SUBC_IN_GGA(X1, X2) R is empty. Q is empty. We have to consider all (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: *SUBC_IN_GGA(s(X1), s(X2)) -> SUBC_IN_GGA(X1, X2) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: ADDB_IN_GGA(s(X1), X2, s(X3)) -> ADDB_IN_GGA(X1, X2, X3) The TRS R consists of the following rules: evaluatecA_in_ga(+(X1, X2), X3) -> U25_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(-(X1, X2), X3) -> U28_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(*(X1, X2), X3) -> U31_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(X1, X1) -> U34_ga(X1, myintegercE_in_g(X1)) myintegercE_in_g(s(X1)) -> U39_g(X1, myintegercE_in_g(X1)) myintegercE_in_g(0) -> myintegercE_out_g(0) U39_g(X1, myintegercE_out_g(X1)) -> myintegercE_out_g(s(X1)) U34_ga(X1, myintegercE_out_g(X1)) -> evaluatecA_out_ga(X1, X1) U31_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U32_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U32_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U33_ga(X1, X2, X3, multcD_in_gga(X4, X5, X3)) multcD_in_gga(s(X1), X2, X3) -> U37_gga(X1, X2, X3, multcD_in_gga(X1, X2, X4)) multcD_in_gga(0, X1, 0) -> multcD_out_gga(0, X1, 0) U37_gga(X1, X2, X3, multcD_out_gga(X1, X2, X4)) -> U38_gga(X1, X2, X3, addcB_in_gga(X2, X4, X3)) addcB_in_gga(s(X1), X2, s(X3)) -> U35_gga(X1, X2, X3, addcB_in_gga(X1, X2, X3)) addcB_in_gga(0, X1, X1) -> addcB_out_gga(0, X1, X1) U35_gga(X1, X2, X3, addcB_out_gga(X1, X2, X3)) -> addcB_out_gga(s(X1), X2, s(X3)) U38_gga(X1, X2, X3, addcB_out_gga(X2, X4, X3)) -> multcD_out_gga(s(X1), X2, X3) U33_ga(X1, X2, X3, multcD_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(*(X1, X2), X3) U28_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U29_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U29_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U30_ga(X1, X2, X3, subcC_in_gga(X4, X5, X3)) subcC_in_gga(s(X1), s(X2), X3) -> U36_gga(X1, X2, X3, subcC_in_gga(X1, X2, X3)) subcC_in_gga(X1, 0, X1) -> subcC_out_gga(X1, 0, X1) U36_gga(X1, X2, X3, subcC_out_gga(X1, X2, X3)) -> subcC_out_gga(s(X1), s(X2), X3) U30_ga(X1, X2, X3, subcC_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(-(X1, X2), X3) U25_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U26_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U26_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U27_ga(X1, X2, X3, addcB_in_gga(X4, X5, X3)) U27_ga(X1, X2, X3, addcB_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(+(X1, X2), X3) The argument filtering Pi contains the following mapping: +(x1, x2) = +(x1, x2) evaluatecA_in_ga(x1, x2) = evaluatecA_in_ga(x1) U25_ga(x1, x2, x3, x4) = U25_ga(x1, x2, x4) -(x1, x2) = -(x1, x2) U28_ga(x1, x2, x3, x4) = U28_ga(x1, x2, x4) *(x1, x2) = *(x1, x2) U31_ga(x1, x2, x3, x4) = U31_ga(x1, x2, x4) U34_ga(x1, x2) = U34_ga(x1, x2) myintegercE_in_g(x1) = myintegercE_in_g(x1) s(x1) = s(x1) U39_g(x1, x2) = U39_g(x1, x2) 0 = 0 myintegercE_out_g(x1) = myintegercE_out_g(x1) evaluatecA_out_ga(x1, x2) = evaluatecA_out_ga(x1, x2) U32_ga(x1, x2, x3, x4, x5) = U32_ga(x1, x2, x4, x5) U33_ga(x1, x2, x3, x4) = U33_ga(x1, x2, x4) multcD_in_gga(x1, x2, x3) = multcD_in_gga(x1, x2) U37_gga(x1, x2, x3, x4) = U37_gga(x1, x2, x4) multcD_out_gga(x1, x2, x3) = multcD_out_gga(x1, x2, x3) U38_gga(x1, x2, x3, x4) = U38_gga(x1, x2, x4) addcB_in_gga(x1, x2, x3) = addcB_in_gga(x1, x2) U35_gga(x1, x2, x3, x4) = U35_gga(x1, x2, x4) addcB_out_gga(x1, x2, x3) = addcB_out_gga(x1, x2, x3) U29_ga(x1, x2, x3, x4, x5) = U29_ga(x1, x2, x4, x5) U30_ga(x1, x2, x3, x4) = U30_ga(x1, x2, x4) subcC_in_gga(x1, x2, x3) = subcC_in_gga(x1, x2) U36_gga(x1, x2, x3, x4) = U36_gga(x1, x2, x4) subcC_out_gga(x1, x2, x3) = subcC_out_gga(x1, x2, x3) U26_ga(x1, x2, x3, x4, x5) = U26_ga(x1, x2, x4, x5) U27_ga(x1, x2, x3, x4) = U27_ga(x1, x2, x4) ADDB_IN_GGA(x1, x2, x3) = ADDB_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (16) Obligation: Pi DP problem: The TRS P consists of the following rules: ADDB_IN_GGA(s(X1), X2, s(X3)) -> ADDB_IN_GGA(X1, X2, X3) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) ADDB_IN_GGA(x1, x2, x3) = ADDB_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (17) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: ADDB_IN_GGA(s(X1), X2) -> ADDB_IN_GGA(X1, X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) 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: *ADDB_IN_GGA(s(X1), X2) -> ADDB_IN_GGA(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: MULTD_IN_GGA(s(X1), X2, X3) -> MULTD_IN_GGA(X1, X2, X4) The TRS R consists of the following rules: evaluatecA_in_ga(+(X1, X2), X3) -> U25_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(-(X1, X2), X3) -> U28_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(*(X1, X2), X3) -> U31_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(X1, X1) -> U34_ga(X1, myintegercE_in_g(X1)) myintegercE_in_g(s(X1)) -> U39_g(X1, myintegercE_in_g(X1)) myintegercE_in_g(0) -> myintegercE_out_g(0) U39_g(X1, myintegercE_out_g(X1)) -> myintegercE_out_g(s(X1)) U34_ga(X1, myintegercE_out_g(X1)) -> evaluatecA_out_ga(X1, X1) U31_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U32_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U32_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U33_ga(X1, X2, X3, multcD_in_gga(X4, X5, X3)) multcD_in_gga(s(X1), X2, X3) -> U37_gga(X1, X2, X3, multcD_in_gga(X1, X2, X4)) multcD_in_gga(0, X1, 0) -> multcD_out_gga(0, X1, 0) U37_gga(X1, X2, X3, multcD_out_gga(X1, X2, X4)) -> U38_gga(X1, X2, X3, addcB_in_gga(X2, X4, X3)) addcB_in_gga(s(X1), X2, s(X3)) -> U35_gga(X1, X2, X3, addcB_in_gga(X1, X2, X3)) addcB_in_gga(0, X1, X1) -> addcB_out_gga(0, X1, X1) U35_gga(X1, X2, X3, addcB_out_gga(X1, X2, X3)) -> addcB_out_gga(s(X1), X2, s(X3)) U38_gga(X1, X2, X3, addcB_out_gga(X2, X4, X3)) -> multcD_out_gga(s(X1), X2, X3) U33_ga(X1, X2, X3, multcD_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(*(X1, X2), X3) U28_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U29_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U29_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U30_ga(X1, X2, X3, subcC_in_gga(X4, X5, X3)) subcC_in_gga(s(X1), s(X2), X3) -> U36_gga(X1, X2, X3, subcC_in_gga(X1, X2, X3)) subcC_in_gga(X1, 0, X1) -> subcC_out_gga(X1, 0, X1) U36_gga(X1, X2, X3, subcC_out_gga(X1, X2, X3)) -> subcC_out_gga(s(X1), s(X2), X3) U30_ga(X1, X2, X3, subcC_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(-(X1, X2), X3) U25_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U26_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U26_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U27_ga(X1, X2, X3, addcB_in_gga(X4, X5, X3)) U27_ga(X1, X2, X3, addcB_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(+(X1, X2), X3) The argument filtering Pi contains the following mapping: +(x1, x2) = +(x1, x2) evaluatecA_in_ga(x1, x2) = evaluatecA_in_ga(x1) U25_ga(x1, x2, x3, x4) = U25_ga(x1, x2, x4) -(x1, x2) = -(x1, x2) U28_ga(x1, x2, x3, x4) = U28_ga(x1, x2, x4) *(x1, x2) = *(x1, x2) U31_ga(x1, x2, x3, x4) = U31_ga(x1, x2, x4) U34_ga(x1, x2) = U34_ga(x1, x2) myintegercE_in_g(x1) = myintegercE_in_g(x1) s(x1) = s(x1) U39_g(x1, x2) = U39_g(x1, x2) 0 = 0 myintegercE_out_g(x1) = myintegercE_out_g(x1) evaluatecA_out_ga(x1, x2) = evaluatecA_out_ga(x1, x2) U32_ga(x1, x2, x3, x4, x5) = U32_ga(x1, x2, x4, x5) U33_ga(x1, x2, x3, x4) = U33_ga(x1, x2, x4) multcD_in_gga(x1, x2, x3) = multcD_in_gga(x1, x2) U37_gga(x1, x2, x3, x4) = U37_gga(x1, x2, x4) multcD_out_gga(x1, x2, x3) = multcD_out_gga(x1, x2, x3) U38_gga(x1, x2, x3, x4) = U38_gga(x1, x2, x4) addcB_in_gga(x1, x2, x3) = addcB_in_gga(x1, x2) U35_gga(x1, x2, x3, x4) = U35_gga(x1, x2, x4) addcB_out_gga(x1, x2, x3) = addcB_out_gga(x1, x2, x3) U29_ga(x1, x2, x3, x4, x5) = U29_ga(x1, x2, x4, x5) U30_ga(x1, x2, x3, x4) = U30_ga(x1, x2, x4) subcC_in_gga(x1, x2, x3) = subcC_in_gga(x1, x2) U36_gga(x1, x2, x3, x4) = U36_gga(x1, x2, x4) subcC_out_gga(x1, x2, x3) = subcC_out_gga(x1, x2, x3) U26_ga(x1, x2, x3, x4, x5) = U26_ga(x1, x2, x4, x5) U27_ga(x1, x2, x3, x4) = U27_ga(x1, x2, x4) MULTD_IN_GGA(x1, x2, x3) = MULTD_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (22) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (23) Obligation: Pi DP problem: The TRS P consists of the following rules: MULTD_IN_GGA(s(X1), X2, X3) -> MULTD_IN_GGA(X1, X2, X4) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) MULTD_IN_GGA(x1, x2, x3) = MULTD_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (24) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: MULTD_IN_GGA(s(X1), X2) -> MULTD_IN_GGA(X1, X2) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (26) 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: *MULTD_IN_GGA(s(X1), X2) -> MULTD_IN_GGA(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (27) YES ---------------------------------------- (28) Obligation: Pi DP problem: The TRS P consists of the following rules: MYINTEGERE_IN_G(s(X1)) -> MYINTEGERE_IN_G(X1) The TRS R consists of the following rules: evaluatecA_in_ga(+(X1, X2), X3) -> U25_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(-(X1, X2), X3) -> U28_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(*(X1, X2), X3) -> U31_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(X1, X1) -> U34_ga(X1, myintegercE_in_g(X1)) myintegercE_in_g(s(X1)) -> U39_g(X1, myintegercE_in_g(X1)) myintegercE_in_g(0) -> myintegercE_out_g(0) U39_g(X1, myintegercE_out_g(X1)) -> myintegercE_out_g(s(X1)) U34_ga(X1, myintegercE_out_g(X1)) -> evaluatecA_out_ga(X1, X1) U31_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U32_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U32_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U33_ga(X1, X2, X3, multcD_in_gga(X4, X5, X3)) multcD_in_gga(s(X1), X2, X3) -> U37_gga(X1, X2, X3, multcD_in_gga(X1, X2, X4)) multcD_in_gga(0, X1, 0) -> multcD_out_gga(0, X1, 0) U37_gga(X1, X2, X3, multcD_out_gga(X1, X2, X4)) -> U38_gga(X1, X2, X3, addcB_in_gga(X2, X4, X3)) addcB_in_gga(s(X1), X2, s(X3)) -> U35_gga(X1, X2, X3, addcB_in_gga(X1, X2, X3)) addcB_in_gga(0, X1, X1) -> addcB_out_gga(0, X1, X1) U35_gga(X1, X2, X3, addcB_out_gga(X1, X2, X3)) -> addcB_out_gga(s(X1), X2, s(X3)) U38_gga(X1, X2, X3, addcB_out_gga(X2, X4, X3)) -> multcD_out_gga(s(X1), X2, X3) U33_ga(X1, X2, X3, multcD_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(*(X1, X2), X3) U28_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U29_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U29_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U30_ga(X1, X2, X3, subcC_in_gga(X4, X5, X3)) subcC_in_gga(s(X1), s(X2), X3) -> U36_gga(X1, X2, X3, subcC_in_gga(X1, X2, X3)) subcC_in_gga(X1, 0, X1) -> subcC_out_gga(X1, 0, X1) U36_gga(X1, X2, X3, subcC_out_gga(X1, X2, X3)) -> subcC_out_gga(s(X1), s(X2), X3) U30_ga(X1, X2, X3, subcC_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(-(X1, X2), X3) U25_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U26_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U26_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U27_ga(X1, X2, X3, addcB_in_gga(X4, X5, X3)) U27_ga(X1, X2, X3, addcB_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(+(X1, X2), X3) The argument filtering Pi contains the following mapping: +(x1, x2) = +(x1, x2) evaluatecA_in_ga(x1, x2) = evaluatecA_in_ga(x1) U25_ga(x1, x2, x3, x4) = U25_ga(x1, x2, x4) -(x1, x2) = -(x1, x2) U28_ga(x1, x2, x3, x4) = U28_ga(x1, x2, x4) *(x1, x2) = *(x1, x2) U31_ga(x1, x2, x3, x4) = U31_ga(x1, x2, x4) U34_ga(x1, x2) = U34_ga(x1, x2) myintegercE_in_g(x1) = myintegercE_in_g(x1) s(x1) = s(x1) U39_g(x1, x2) = U39_g(x1, x2) 0 = 0 myintegercE_out_g(x1) = myintegercE_out_g(x1) evaluatecA_out_ga(x1, x2) = evaluatecA_out_ga(x1, x2) U32_ga(x1, x2, x3, x4, x5) = U32_ga(x1, x2, x4, x5) U33_ga(x1, x2, x3, x4) = U33_ga(x1, x2, x4) multcD_in_gga(x1, x2, x3) = multcD_in_gga(x1, x2) U37_gga(x1, x2, x3, x4) = U37_gga(x1, x2, x4) multcD_out_gga(x1, x2, x3) = multcD_out_gga(x1, x2, x3) U38_gga(x1, x2, x3, x4) = U38_gga(x1, x2, x4) addcB_in_gga(x1, x2, x3) = addcB_in_gga(x1, x2) U35_gga(x1, x2, x3, x4) = U35_gga(x1, x2, x4) addcB_out_gga(x1, x2, x3) = addcB_out_gga(x1, x2, x3) U29_ga(x1, x2, x3, x4, x5) = U29_ga(x1, x2, x4, x5) U30_ga(x1, x2, x3, x4) = U30_ga(x1, x2, x4) subcC_in_gga(x1, x2, x3) = subcC_in_gga(x1, x2) U36_gga(x1, x2, x3, x4) = U36_gga(x1, x2, x4) subcC_out_gga(x1, x2, x3) = subcC_out_gga(x1, x2, x3) U26_ga(x1, x2, x3, x4, x5) = U26_ga(x1, x2, x4, x5) U27_ga(x1, x2, x3, x4) = U27_ga(x1, x2, x4) MYINTEGERE_IN_G(x1) = MYINTEGERE_IN_G(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (29) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (30) Obligation: Pi DP problem: The TRS P consists of the following rules: MYINTEGERE_IN_G(s(X1)) -> MYINTEGERE_IN_G(X1) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (31) PiDPToQDPProof (EQUIVALENT) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: MYINTEGERE_IN_G(s(X1)) -> MYINTEGERE_IN_G(X1) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (33) 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: *MYINTEGERE_IN_G(s(X1)) -> MYINTEGERE_IN_G(X1) The graph contains the following edges 1 > 1 ---------------------------------------- (34) YES ---------------------------------------- (35) Obligation: Pi DP problem: The TRS P consists of the following rules: EVALUATEA_IN_GA(+(X1, X2), X3) -> U2_GA(X1, X2, X3, evaluatecA_in_ga(X1, X4)) U2_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> EVALUATEA_IN_GA(X2, X5) EVALUATEA_IN_GA(+(X1, X2), X3) -> EVALUATEA_IN_GA(X1, X4) EVALUATEA_IN_GA(-(X1, X2), X3) -> EVALUATEA_IN_GA(X1, X4) EVALUATEA_IN_GA(-(X1, X2), X3) -> U7_GA(X1, X2, X3, evaluatecA_in_ga(X1, X4)) U7_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> EVALUATEA_IN_GA(X2, X5) EVALUATEA_IN_GA(*(X1, X2), X3) -> EVALUATEA_IN_GA(X1, X4) EVALUATEA_IN_GA(*(X1, X2), X3) -> U12_GA(X1, X2, X3, evaluatecA_in_ga(X1, X4)) U12_GA(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> EVALUATEA_IN_GA(X2, X5) The TRS R consists of the following rules: evaluatecA_in_ga(+(X1, X2), X3) -> U25_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(-(X1, X2), X3) -> U28_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(*(X1, X2), X3) -> U31_ga(X1, X2, X3, evaluatecA_in_ga(X1, X4)) evaluatecA_in_ga(X1, X1) -> U34_ga(X1, myintegercE_in_g(X1)) myintegercE_in_g(s(X1)) -> U39_g(X1, myintegercE_in_g(X1)) myintegercE_in_g(0) -> myintegercE_out_g(0) U39_g(X1, myintegercE_out_g(X1)) -> myintegercE_out_g(s(X1)) U34_ga(X1, myintegercE_out_g(X1)) -> evaluatecA_out_ga(X1, X1) U31_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U32_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U32_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U33_ga(X1, X2, X3, multcD_in_gga(X4, X5, X3)) multcD_in_gga(s(X1), X2, X3) -> U37_gga(X1, X2, X3, multcD_in_gga(X1, X2, X4)) multcD_in_gga(0, X1, 0) -> multcD_out_gga(0, X1, 0) U37_gga(X1, X2, X3, multcD_out_gga(X1, X2, X4)) -> U38_gga(X1, X2, X3, addcB_in_gga(X2, X4, X3)) addcB_in_gga(s(X1), X2, s(X3)) -> U35_gga(X1, X2, X3, addcB_in_gga(X1, X2, X3)) addcB_in_gga(0, X1, X1) -> addcB_out_gga(0, X1, X1) U35_gga(X1, X2, X3, addcB_out_gga(X1, X2, X3)) -> addcB_out_gga(s(X1), X2, s(X3)) U38_gga(X1, X2, X3, addcB_out_gga(X2, X4, X3)) -> multcD_out_gga(s(X1), X2, X3) U33_ga(X1, X2, X3, multcD_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(*(X1, X2), X3) U28_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U29_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U29_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U30_ga(X1, X2, X3, subcC_in_gga(X4, X5, X3)) subcC_in_gga(s(X1), s(X2), X3) -> U36_gga(X1, X2, X3, subcC_in_gga(X1, X2, X3)) subcC_in_gga(X1, 0, X1) -> subcC_out_gga(X1, 0, X1) U36_gga(X1, X2, X3, subcC_out_gga(X1, X2, X3)) -> subcC_out_gga(s(X1), s(X2), X3) U30_ga(X1, X2, X3, subcC_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(-(X1, X2), X3) U25_ga(X1, X2, X3, evaluatecA_out_ga(X1, X4)) -> U26_ga(X1, X2, X3, X4, evaluatecA_in_ga(X2, X5)) U26_ga(X1, X2, X3, X4, evaluatecA_out_ga(X2, X5)) -> U27_ga(X1, X2, X3, addcB_in_gga(X4, X5, X3)) U27_ga(X1, X2, X3, addcB_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(+(X1, X2), X3) The argument filtering Pi contains the following mapping: +(x1, x2) = +(x1, x2) evaluatecA_in_ga(x1, x2) = evaluatecA_in_ga(x1) U25_ga(x1, x2, x3, x4) = U25_ga(x1, x2, x4) -(x1, x2) = -(x1, x2) U28_ga(x1, x2, x3, x4) = U28_ga(x1, x2, x4) *(x1, x2) = *(x1, x2) U31_ga(x1, x2, x3, x4) = U31_ga(x1, x2, x4) U34_ga(x1, x2) = U34_ga(x1, x2) myintegercE_in_g(x1) = myintegercE_in_g(x1) s(x1) = s(x1) U39_g(x1, x2) = U39_g(x1, x2) 0 = 0 myintegercE_out_g(x1) = myintegercE_out_g(x1) evaluatecA_out_ga(x1, x2) = evaluatecA_out_ga(x1, x2) U32_ga(x1, x2, x3, x4, x5) = U32_ga(x1, x2, x4, x5) U33_ga(x1, x2, x3, x4) = U33_ga(x1, x2, x4) multcD_in_gga(x1, x2, x3) = multcD_in_gga(x1, x2) U37_gga(x1, x2, x3, x4) = U37_gga(x1, x2, x4) multcD_out_gga(x1, x2, x3) = multcD_out_gga(x1, x2, x3) U38_gga(x1, x2, x3, x4) = U38_gga(x1, x2, x4) addcB_in_gga(x1, x2, x3) = addcB_in_gga(x1, x2) U35_gga(x1, x2, x3, x4) = U35_gga(x1, x2, x4) addcB_out_gga(x1, x2, x3) = addcB_out_gga(x1, x2, x3) U29_ga(x1, x2, x3, x4, x5) = U29_ga(x1, x2, x4, x5) U30_ga(x1, x2, x3, x4) = U30_ga(x1, x2, x4) subcC_in_gga(x1, x2, x3) = subcC_in_gga(x1, x2) U36_gga(x1, x2, x3, x4) = U36_gga(x1, x2, x4) subcC_out_gga(x1, x2, x3) = subcC_out_gga(x1, x2, x3) U26_ga(x1, x2, x3, x4, x5) = U26_ga(x1, x2, x4, x5) U27_ga(x1, x2, x3, x4) = U27_ga(x1, x2, x4) EVALUATEA_IN_GA(x1, x2) = EVALUATEA_IN_GA(x1) U2_GA(x1, x2, x3, x4) = U2_GA(x1, x2, x4) U7_GA(x1, x2, x3, x4) = U7_GA(x1, x2, x4) U12_GA(x1, x2, x3, x4) = U12_GA(x1, x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (36) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: EVALUATEA_IN_GA(+(X1, X2)) -> U2_GA(X1, X2, evaluatecA_in_ga(X1)) U2_GA(X1, X2, evaluatecA_out_ga(X1, X4)) -> EVALUATEA_IN_GA(X2) EVALUATEA_IN_GA(+(X1, X2)) -> EVALUATEA_IN_GA(X1) EVALUATEA_IN_GA(-(X1, X2)) -> EVALUATEA_IN_GA(X1) EVALUATEA_IN_GA(-(X1, X2)) -> U7_GA(X1, X2, evaluatecA_in_ga(X1)) U7_GA(X1, X2, evaluatecA_out_ga(X1, X4)) -> EVALUATEA_IN_GA(X2) EVALUATEA_IN_GA(*(X1, X2)) -> EVALUATEA_IN_GA(X1) EVALUATEA_IN_GA(*(X1, X2)) -> U12_GA(X1, X2, evaluatecA_in_ga(X1)) U12_GA(X1, X2, evaluatecA_out_ga(X1, X4)) -> EVALUATEA_IN_GA(X2) The TRS R consists of the following rules: evaluatecA_in_ga(+(X1, X2)) -> U25_ga(X1, X2, evaluatecA_in_ga(X1)) evaluatecA_in_ga(-(X1, X2)) -> U28_ga(X1, X2, evaluatecA_in_ga(X1)) evaluatecA_in_ga(*(X1, X2)) -> U31_ga(X1, X2, evaluatecA_in_ga(X1)) evaluatecA_in_ga(X1) -> U34_ga(X1, myintegercE_in_g(X1)) myintegercE_in_g(s(X1)) -> U39_g(X1, myintegercE_in_g(X1)) myintegercE_in_g(0) -> myintegercE_out_g(0) U39_g(X1, myintegercE_out_g(X1)) -> myintegercE_out_g(s(X1)) U34_ga(X1, myintegercE_out_g(X1)) -> evaluatecA_out_ga(X1, X1) U31_ga(X1, X2, evaluatecA_out_ga(X1, X4)) -> U32_ga(X1, X2, X4, evaluatecA_in_ga(X2)) U32_ga(X1, X2, X4, evaluatecA_out_ga(X2, X5)) -> U33_ga(X1, X2, multcD_in_gga(X4, X5)) multcD_in_gga(s(X1), X2) -> U37_gga(X1, X2, multcD_in_gga(X1, X2)) multcD_in_gga(0, X1) -> multcD_out_gga(0, X1, 0) U37_gga(X1, X2, multcD_out_gga(X1, X2, X4)) -> U38_gga(X1, X2, addcB_in_gga(X2, X4)) addcB_in_gga(s(X1), X2) -> U35_gga(X1, X2, addcB_in_gga(X1, X2)) addcB_in_gga(0, X1) -> addcB_out_gga(0, X1, X1) U35_gga(X1, X2, addcB_out_gga(X1, X2, X3)) -> addcB_out_gga(s(X1), X2, s(X3)) U38_gga(X1, X2, addcB_out_gga(X2, X4, X3)) -> multcD_out_gga(s(X1), X2, X3) U33_ga(X1, X2, multcD_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(*(X1, X2), X3) U28_ga(X1, X2, evaluatecA_out_ga(X1, X4)) -> U29_ga(X1, X2, X4, evaluatecA_in_ga(X2)) U29_ga(X1, X2, X4, evaluatecA_out_ga(X2, X5)) -> U30_ga(X1, X2, subcC_in_gga(X4, X5)) subcC_in_gga(s(X1), s(X2)) -> U36_gga(X1, X2, subcC_in_gga(X1, X2)) subcC_in_gga(X1, 0) -> subcC_out_gga(X1, 0, X1) U36_gga(X1, X2, subcC_out_gga(X1, X2, X3)) -> subcC_out_gga(s(X1), s(X2), X3) U30_ga(X1, X2, subcC_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(-(X1, X2), X3) U25_ga(X1, X2, evaluatecA_out_ga(X1, X4)) -> U26_ga(X1, X2, X4, evaluatecA_in_ga(X2)) U26_ga(X1, X2, X4, evaluatecA_out_ga(X2, X5)) -> U27_ga(X1, X2, addcB_in_gga(X4, X5)) U27_ga(X1, X2, addcB_out_gga(X4, X5, X3)) -> evaluatecA_out_ga(+(X1, X2), X3) The set Q consists of the following terms: evaluatecA_in_ga(x0) myintegercE_in_g(x0) U39_g(x0, x1) U34_ga(x0, x1) U31_ga(x0, x1, x2) U32_ga(x0, x1, x2, x3) multcD_in_gga(x0, x1) U37_gga(x0, x1, x2) addcB_in_gga(x0, x1) U35_gga(x0, x1, x2) U38_gga(x0, x1, x2) U33_ga(x0, x1, x2) U28_ga(x0, x1, x2) U29_ga(x0, x1, x2, x3) subcC_in_gga(x0, x1) U36_gga(x0, x1, x2) U30_ga(x0, x1, x2) U25_ga(x0, x1, x2) U26_ga(x0, x1, x2, x3) U27_ga(x0, x1, x2) We have to consider all (P,Q,R)-chains. ---------------------------------------- (38) 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: *U2_GA(X1, X2, evaluatecA_out_ga(X1, X4)) -> EVALUATEA_IN_GA(X2) The graph contains the following edges 2 >= 1 *EVALUATEA_IN_GA(+(X1, X2)) -> U2_GA(X1, X2, evaluatecA_in_ga(X1)) The graph contains the following edges 1 > 1, 1 > 2 *U7_GA(X1, X2, evaluatecA_out_ga(X1, X4)) -> EVALUATEA_IN_GA(X2) The graph contains the following edges 2 >= 1 *U12_GA(X1, X2, evaluatecA_out_ga(X1, X4)) -> EVALUATEA_IN_GA(X2) The graph contains the following edges 2 >= 1 *EVALUATEA_IN_GA(-(X1, X2)) -> U7_GA(X1, X2, evaluatecA_in_ga(X1)) The graph contains the following edges 1 > 1, 1 > 2 *EVALUATEA_IN_GA(*(X1, X2)) -> U12_GA(X1, X2, evaluatecA_in_ga(X1)) The graph contains the following edges 1 > 1, 1 > 2 *EVALUATEA_IN_GA(+(X1, X2)) -> EVALUATEA_IN_GA(X1) The graph contains the following edges 1 > 1 *EVALUATEA_IN_GA(-(X1, X2)) -> EVALUATEA_IN_GA(X1) The graph contains the following edges 1 > 1 *EVALUATEA_IN_GA(*(X1, X2)) -> EVALUATEA_IN_GA(X1) The graph contains the following edges 1 > 1 ---------------------------------------- (39) YES