/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern minus(g,a,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 32 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 3 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 [SOUND, 0 ms] (32) QDP (33) QDPSizeChangeProof [EQUIVALENT, 0 ms] (34) YES (35) PiDP (36) UsableRulesProof [EQUIVALENT, 0 ms] (37) PiDP (38) PiDPToQDPProof [SOUND, 0 ms] (39) QDP (40) QDPSizeChangeProof [EQUIVALENT, 0 ms] (41) YES ---------------------------------------- (0) Obligation: Clauses: p(0, 0). p(s(X), X). le(0, Y, true). le(s(X), 0, false). le(s(X), s(Y), B) :- le(X, Y, B). minus(X, Y, Z) :- ','(le(X, Y, B), if(B, X, Y, Z)). if(true, X, Y, 0). if(false, X, Y, s(Z)) :- ','(p(X, X1), minus(X1, Y, Z)). Query: minus(g,a,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(p (0) (0))", null ], [ "(p (s X) X)", null ], [ "(le (0) Y (true))", null ], [ "(le (s X) (0) (false))", null ], [ "(le (s X) (s Y) B)", "(le X Y B)" ], [ "(minus X Y Z)", "(',' (le X Y B) (if B X Y Z))" ], [ "(if (true) X Y (0))", null ], [ "(if (false) X Y (s Z))", "(',' (p X X1) (minus X1 Y Z))" ] ] }, "graph": { "nodes": { "270": { "goal": [{ "clause": 2, "scope": 2, "term": "(',' (le T7 T10 X8) (if X8 T7 T10 T11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": ["X8"], "exprvars": [] } }, "type": "Nodes", "271": { "goal": [ { "clause": 3, "scope": 2, "term": "(',' (le T7 T10 X8) (if X8 T7 T10 T11))" }, { "clause": 4, "scope": 2, "term": "(',' (le T7 T10 X8) (if X8 T7 T10 T11))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": ["X8"], "exprvars": [] } }, "274": { "goal": [{ "clause": -1, "scope": -1, "term": "(if (true) (0) T17 T18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "395": { "goal": [{ "clause": 2, "scope": 6, "term": "(le T51 T53 X80)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T51"], "free": ["X80"], "exprvars": [] } }, "275": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "396": { "goal": [ { "clause": 3, "scope": 6, "term": "(le T51 T53 X80)" }, { "clause": 4, "scope": 6, "term": "(le T51 T53 X80)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T51"], "free": ["X80"], "exprvars": [] } }, "397": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "398": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "399": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(minus T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "365": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "366": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "367": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "400": { "goal": [{ "clause": 3, "scope": 6, "term": "(le T51 T53 X80)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T51"], "free": ["X80"], "exprvars": [] } }, "368": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "401": { "goal": [{ "clause": 4, "scope": 6, "term": "(le T51 T53 X80)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T51"], "free": ["X80"], "exprvars": [] } }, "369": { "goal": [{ "clause": 3, "scope": 2, "term": "(',' (le T7 T10 X8) (if X8 T7 T10 T11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": ["X8"], "exprvars": [] } }, "402": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "403": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "404": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "405": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T76 T78 X106)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T76"], "free": ["X106"], "exprvars": [] } }, "406": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "407": { "goal": [ { "clause": 6, "scope": 7, "term": "(if T57 (s T51) (s T58) T59)" }, { "clause": 7, "scope": 7, "term": "(if T57 (s T51) (s T58) T59)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T51", "T57" ], "free": [], "exprvars": [] } }, "408": { "goal": [{ "clause": 6, "scope": 7, "term": "(if T57 (s T51) (s T58) T59)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T51", "T57" ], "free": [], "exprvars": [] } }, "409": { "goal": [{ "clause": 7, "scope": 7, "term": "(if T57 (s T51) (s T58) T59)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T51", "T57" ], "free": [], "exprvars": [] } }, "370": { "goal": [{ "clause": 4, "scope": 2, "term": "(',' (le T7 T10 X8) (if X8 T7 T10 T11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": ["X8"], "exprvars": [] } }, "371": { "goal": [{ "clause": -1, "scope": -1, "term": "(if (false) (s T30) (0) T31)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T30"], "free": [], "exprvars": [] } }, "372": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "373": { "goal": [ { "clause": 6, "scope": 4, "term": "(if (false) (s T30) (0) T31)" }, { "clause": 7, "scope": 4, "term": "(if (false) (s T30) (0) T31)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T30"], "free": [], "exprvars": [] } }, "374": { "goal": [{ "clause": 7, "scope": 4, "term": "(if (false) (s T30) (0) T31)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T30"], "free": [], "exprvars": [] } }, "375": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p (s T36) X52) (minus X52 (0) T38))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T36"], "free": ["X52"], "exprvars": [] } }, "376": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "377": { "goal": [ { "clause": 0, "scope": 5, "term": "(',' (p (s T36) X52) (minus X52 (0) T38))" }, { "clause": 1, "scope": 5, "term": "(',' (p (s T36) X52) (minus X52 (0) T38))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T36"], "free": ["X52"], "exprvars": [] } }, "410": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "334": { "goal": [ { "clause": 6, "scope": 3, "term": "(if (true) (0) T17 T18)" }, { "clause": 7, "scope": 3, "term": "(if (true) (0) T17 T18)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "378": { "goal": [{ "clause": 1, "scope": 5, "term": "(',' (p (s T36) X52) (minus X52 (0) T38))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T36"], "free": ["X52"], "exprvars": [] } }, "411": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "335": { "goal": [{ "clause": 6, "scope": 3, "term": "(if (true) (0) T17 T18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "379": { "goal": [{ "clause": -1, "scope": -1, "term": "(minus T44 (0) T38)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T44"], "free": [], "exprvars": [] } }, "412": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "336": { "goal": [{ "clause": 7, "scope": 3, "term": "(if (true) (0) T17 T18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "413": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p (s T101) X133) (minus X133 (s T105) T104))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T101"], "free": ["X133"], "exprvars": [] } }, "414": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "415": { "goal": [ { "clause": 0, "scope": 8, "term": "(',' (p (s T101) X133) (minus X133 (s T105) T104))" }, { "clause": 1, "scope": 8, "term": "(',' (p (s T101) X133) (minus X133 (s T105) T104))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T101"], "free": ["X133"], "exprvars": [] } }, "416": { "goal": [{ "clause": 1, "scope": 8, "term": "(',' (p (s T101) X133) (minus X133 (s T105) T104))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T101"], "free": ["X133"], "exprvars": [] } }, "417": { "goal": [{ "clause": -1, "scope": -1, "term": "(minus T113 (s T105) T104)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T113"], "free": [], "exprvars": [] } }, "380": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (le T51 T53 X80) (if X80 (s T51) (s T53) T54))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T51"], "free": ["X80"], "exprvars": [] } }, "381": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "382": { "goal": [{ "clause": -1, "scope": -1, "term": "(le T51 T53 X80)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T51"], "free": ["X80"], "exprvars": [] } }, "383": { "goal": [{ "clause": -1, "scope": -1, "term": "(if T57 (s T51) (s T58) T59)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T51", "T57" ], "free": [], "exprvars": [] } }, "384": { "goal": [ { "clause": 2, "scope": 6, "term": "(le T51 T53 X80)" }, { "clause": 3, "scope": 6, "term": "(le T51 T53 X80)" }, { "clause": 4, "scope": 6, "term": "(le T51 T53 X80)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T51"], "free": ["X80"], "exprvars": [] } }, "267": { "goal": [{ "clause": 5, "scope": 1, "term": "(minus T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "268": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (le T7 T10 X8) (if X8 T7 T10 T11))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": ["X8"], "exprvars": [] } }, "269": { "goal": [ { "clause": 2, "scope": 2, "term": "(',' (le T7 T10 X8) (if X8 T7 T10 T11))" }, { "clause": 3, "scope": 2, "term": "(',' (le T7 T10 X8) (if X8 T7 T10 T11))" }, { "clause": 4, "scope": 2, "term": "(',' (le T7 T10 X8) (if X8 T7 T10 T11))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": ["X8"], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 267, "label": "CASE" }, { "from": 267, "to": 268, "label": "ONLY EVAL with clause\nminus(X5, X6, X7) :- ','(le(X5, X6, X8), if(X8, X5, X6, X7)).\nand substitutionT1 -> T7,\nX5 -> T7,\nT2 -> T10,\nX6 -> T10,\nT3 -> T11,\nX7 -> T11,\nT8 -> T10,\nT9 -> T11" }, { "from": 268, "to": 269, "label": "CASE" }, { "from": 269, "to": 270, "label": "PARALLEL" }, { "from": 269, "to": 271, "label": "PARALLEL" }, { "from": 270, "to": 274, "label": "EVAL with clause\nle(0, X13, true).\nand substitutionT7 -> 0,\nT10 -> T17,\nX13 -> T17,\nX8 -> true,\nT16 -> T17,\nT11 -> T18" }, { "from": 270, "to": 275, "label": "EVAL-BACKTRACK" }, { "from": 271, "to": 369, "label": "PARALLEL" }, { "from": 271, "to": 370, "label": "PARALLEL" }, { "from": 274, "to": 334, "label": "CASE" }, { "from": 334, "to": 335, "label": "PARALLEL" }, { "from": 334, "to": 336, "label": "PARALLEL" }, { "from": 335, "to": 365, "label": "EVAL with clause\nif(true, X26, X27, 0).\nand substitutionX26 -> 0,\nT17 -> T25,\nX27 -> T25,\nT18 -> 0" }, { "from": 335, "to": 366, "label": "EVAL-BACKTRACK" }, { "from": 336, "to": 368, "label": "BACKTRACK\nfor clause: if(false, X, Y, s(Z)) :- ','(p(X, X1), minus(X1, Y, Z))because of non-unification" }, { "from": 365, "to": 367, "label": "SUCCESS" }, { "from": 369, "to": 371, "label": "EVAL with clause\nle(s(X35), 0, false).\nand substitutionX35 -> T30,\nT7 -> s(T30),\nT10 -> 0,\nX8 -> false,\nT11 -> T31" }, { "from": 369, "to": 372, "label": "EVAL-BACKTRACK" }, { "from": 370, "to": 380, "label": "EVAL with clause\nle(s(X77), s(X78), X79) :- le(X77, X78, X79).\nand substitutionX77 -> T51,\nT7 -> s(T51),\nX78 -> T53,\nT10 -> s(T53),\nX8 -> X80,\nX79 -> X80,\nT52 -> T53,\nT11 -> T54" }, { "from": 370, "to": 381, "label": "EVAL-BACKTRACK" }, { "from": 371, "to": 373, "label": "CASE" }, { "from": 373, "to": 374, "label": "BACKTRACK\nfor clause: if(true, X, Y, 0)because of non-unification" }, { "from": 374, "to": 375, "label": "EVAL with clause\nif(false, X49, X50, s(X51)) :- ','(p(X49, X52), minus(X52, X50, X51)).\nand substitutionT30 -> T36,\nX49 -> s(T36),\nX50 -> 0,\nX51 -> T38,\nT31 -> s(T38),\nT37 -> T38" }, { "from": 374, "to": 376, "label": "EVAL-BACKTRACK" }, { "from": 375, "to": 377, "label": "CASE" }, { "from": 377, "to": 378, "label": "BACKTRACK\nfor clause: p(0, 0)because of non-unification" }, { "from": 378, "to": 379, "label": "ONLY EVAL with clause\np(s(X64), X64).\nand substitutionT36 -> T44,\nX64 -> T44,\nX52 -> T44" }, { "from": 379, "to": 1, "label": "INSTANCE with matching:\nT1 -> T44\nT2 -> 0\nT3 -> T38" }, { "from": 380, "to": 382, "label": "SPLIT 1" }, { "from": 380, "to": 383, "label": "SPLIT 2\nnew knowledge:\nT51 is ground\nT57 is ground\nreplacements:X80 -> T57,\nT53 -> T58,\nT54 -> T59" }, { "from": 382, "to": 384, "label": "CASE" }, { "from": 383, "to": 407, "label": "CASE" }, { "from": 384, "to": 395, "label": "PARALLEL" }, { "from": 384, "to": 396, "label": "PARALLEL" }, { "from": 395, "to": 397, "label": "EVAL with clause\nle(0, X89, true).\nand substitutionT51 -> 0,\nT53 -> T66,\nX89 -> T66,\nX80 -> true" }, { "from": 395, "to": 398, "label": "EVAL-BACKTRACK" }, { "from": 396, "to": 400, "label": "PARALLEL" }, { "from": 396, "to": 401, "label": "PARALLEL" }, { "from": 397, "to": 399, "label": "SUCCESS" }, { "from": 400, "to": 402, "label": "EVAL with clause\nle(s(X94), 0, false).\nand substitutionX94 -> T71,\nT51 -> s(T71),\nT53 -> 0,\nX80 -> false" }, { "from": 400, "to": 403, "label": "EVAL-BACKTRACK" }, { "from": 401, "to": 405, "label": "EVAL with clause\nle(s(X103), s(X104), X105) :- le(X103, X104, X105).\nand substitutionX103 -> T76,\nT51 -> s(T76),\nX104 -> T78,\nT53 -> s(T78),\nX80 -> X106,\nX105 -> X106,\nT77 -> T78" }, { "from": 401, "to": 406, "label": "EVAL-BACKTRACK" }, { "from": 402, "to": 404, "label": "SUCCESS" }, { "from": 405, "to": 382, "label": "INSTANCE with matching:\nT51 -> T76\nT53 -> T78\nX80 -> X106" }, { "from": 407, "to": 408, "label": "PARALLEL" }, { "from": 407, "to": 409, "label": "PARALLEL" }, { "from": 408, "to": 410, "label": "EVAL with clause\nif(true, X121, X122, 0).\nand substitutionT57 -> true,\nT51 -> T93,\nX121 -> s(T93),\nT58 -> T94,\nX122 -> s(T94),\nT59 -> 0" }, { "from": 408, "to": 411, "label": "EVAL-BACKTRACK" }, { "from": 409, "to": 413, "label": "EVAL with clause\nif(false, X130, X131, s(X132)) :- ','(p(X130, X133), minus(X133, X131, X132)).\nand substitutionT57 -> false,\nT51 -> T101,\nX130 -> s(T101),\nT58 -> T105,\nX131 -> s(T105),\nX132 -> T104,\nT59 -> s(T104),\nT103 -> T104,\nT102 -> T105" }, { "from": 409, "to": 414, "label": "EVAL-BACKTRACK" }, { "from": 410, "to": 412, "label": "SUCCESS" }, { "from": 413, "to": 415, "label": "CASE" }, { "from": 415, "to": 416, "label": "BACKTRACK\nfor clause: p(0, 0)because of non-unification" }, { "from": 416, "to": 417, "label": "ONLY EVAL with clause\np(s(X145), X145).\nand substitutionT101 -> T113,\nX145 -> T113,\nX133 -> T113" }, { "from": 417, "to": 1, "label": "INSTANCE with matching:\nT1 -> T113\nT2 -> s(T105)\nT3 -> T104" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: leB(s(X1), s(X2), X3) :- leB(X1, X2, X3). minusA(s(X1), 0, s(X2)) :- minusA(X1, 0, X2). minusA(s(X1), s(X2), X3) :- leB(X1, X2, X4). minusA(s(X1), s(X2), s(X3)) :- ','(lecB(X1, X2, false), minusA(X1, s(X2), X3)). Clauses: minuscA(0, X1, 0). minuscA(s(X1), 0, s(X2)) :- minuscA(X1, 0, X2). minuscA(s(X1), s(X2), 0) :- lecB(X1, X2, true). minuscA(s(X1), s(X2), s(X3)) :- ','(lecB(X1, X2, false), minuscA(X1, s(X2), X3)). lecB(0, X1, true). lecB(s(X1), 0, false). lecB(s(X1), s(X2), X3) :- lecB(X1, X2, X3). Afs: minusA(x1, x2, x3) = minusA(x1) ---------------------------------------- (3) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: minusA_in_3: (b,f,f) (b,b,f) leB_in_3: (b,b,f) (b,f,f) lecB_in_3: (b,b,b) (b,f,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: MINUSA_IN_GAA(s(X1), 0, s(X2)) -> U2_GAA(X1, X2, minusA_in_gga(X1, 0, X2)) MINUSA_IN_GAA(s(X1), 0, s(X2)) -> MINUSA_IN_GGA(X1, 0, X2) MINUSA_IN_GGA(s(X1), 0, s(X2)) -> U2_GGA(X1, X2, minusA_in_gga(X1, 0, X2)) MINUSA_IN_GGA(s(X1), 0, s(X2)) -> MINUSA_IN_GGA(X1, 0, X2) MINUSA_IN_GGA(s(X1), s(X2), X3) -> U3_GGA(X1, X2, X3, leB_in_gga(X1, X2, X4)) MINUSA_IN_GGA(s(X1), s(X2), X3) -> LEB_IN_GGA(X1, X2, X4) LEB_IN_GGA(s(X1), s(X2), X3) -> U1_GGA(X1, X2, X3, leB_in_gga(X1, X2, X3)) LEB_IN_GGA(s(X1), s(X2), X3) -> LEB_IN_GGA(X1, X2, X3) MINUSA_IN_GGA(s(X1), s(X2), s(X3)) -> U4_GGA(X1, X2, X3, lecB_in_ggg(X1, X2, false)) U4_GGA(X1, X2, X3, lecB_out_ggg(X1, X2, false)) -> U5_GGA(X1, X2, X3, minusA_in_gga(X1, s(X2), X3)) U4_GGA(X1, X2, X3, lecB_out_ggg(X1, X2, false)) -> MINUSA_IN_GGA(X1, s(X2), X3) MINUSA_IN_GAA(s(X1), s(X2), X3) -> U3_GAA(X1, X2, X3, leB_in_gaa(X1, X2, X4)) MINUSA_IN_GAA(s(X1), s(X2), X3) -> LEB_IN_GAA(X1, X2, X4) LEB_IN_GAA(s(X1), s(X2), X3) -> U1_GAA(X1, X2, X3, leB_in_gaa(X1, X2, X3)) LEB_IN_GAA(s(X1), s(X2), X3) -> LEB_IN_GAA(X1, X2, X3) MINUSA_IN_GAA(s(X1), s(X2), s(X3)) -> U4_GAA(X1, X2, X3, lecB_in_gag(X1, X2, false)) U4_GAA(X1, X2, X3, lecB_out_gag(X1, X2, false)) -> U5_GAA(X1, X2, X3, minusA_in_gaa(X1, s(X2), X3)) U4_GAA(X1, X2, X3, lecB_out_gag(X1, X2, false)) -> MINUSA_IN_GAA(X1, s(X2), X3) The TRS R consists of the following rules: lecB_in_ggg(0, X1, true) -> lecB_out_ggg(0, X1, true) lecB_in_ggg(s(X1), 0, false) -> lecB_out_ggg(s(X1), 0, false) lecB_in_ggg(s(X1), s(X2), X3) -> U11_ggg(X1, X2, X3, lecB_in_ggg(X1, X2, X3)) U11_ggg(X1, X2, X3, lecB_out_ggg(X1, X2, X3)) -> lecB_out_ggg(s(X1), s(X2), X3) lecB_in_gag(0, X1, true) -> lecB_out_gag(0, X1, true) lecB_in_gag(s(X1), 0, false) -> lecB_out_gag(s(X1), 0, false) lecB_in_gag(s(X1), s(X2), X3) -> U11_gag(X1, X2, X3, lecB_in_gag(X1, X2, X3)) U11_gag(X1, X2, X3, lecB_out_gag(X1, X2, X3)) -> lecB_out_gag(s(X1), s(X2), X3) The argument filtering Pi contains the following mapping: minusA_in_gaa(x1, x2, x3) = minusA_in_gaa(x1) s(x1) = s(x1) minusA_in_gga(x1, x2, x3) = minusA_in_gga(x1, x2) 0 = 0 leB_in_gga(x1, x2, x3) = leB_in_gga(x1, x2) lecB_in_ggg(x1, x2, x3) = lecB_in_ggg(x1, x2, x3) true = true lecB_out_ggg(x1, x2, x3) = lecB_out_ggg(x1, x2, x3) false = false U11_ggg(x1, x2, x3, x4) = U11_ggg(x1, x2, x3, x4) leB_in_gaa(x1, x2, x3) = leB_in_gaa(x1) lecB_in_gag(x1, x2, x3) = lecB_in_gag(x1, x3) lecB_out_gag(x1, x2, x3) = lecB_out_gag(x1, x3) U11_gag(x1, x2, x3, x4) = U11_gag(x1, x3, x4) MINUSA_IN_GAA(x1, x2, x3) = MINUSA_IN_GAA(x1) U2_GAA(x1, x2, x3) = U2_GAA(x1, x3) MINUSA_IN_GGA(x1, x2, x3) = MINUSA_IN_GGA(x1, x2) U2_GGA(x1, x2, x3) = U2_GGA(x1, x3) U3_GGA(x1, x2, x3, x4) = U3_GGA(x1, x2, x4) LEB_IN_GGA(x1, x2, x3) = LEB_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4) = U1_GGA(x1, x2, x4) U4_GGA(x1, x2, x3, x4) = U4_GGA(x1, x2, x4) U5_GGA(x1, x2, x3, x4) = U5_GGA(x1, x2, x4) U3_GAA(x1, x2, x3, x4) = U3_GAA(x1, x4) LEB_IN_GAA(x1, x2, x3) = LEB_IN_GAA(x1) U1_GAA(x1, x2, x3, x4) = U1_GAA(x1, x4) U4_GAA(x1, x2, x3, x4) = U4_GAA(x1, x4) U5_GAA(x1, x2, x3, x4) = U5_GAA(x1, 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: MINUSA_IN_GAA(s(X1), 0, s(X2)) -> U2_GAA(X1, X2, minusA_in_gga(X1, 0, X2)) MINUSA_IN_GAA(s(X1), 0, s(X2)) -> MINUSA_IN_GGA(X1, 0, X2) MINUSA_IN_GGA(s(X1), 0, s(X2)) -> U2_GGA(X1, X2, minusA_in_gga(X1, 0, X2)) MINUSA_IN_GGA(s(X1), 0, s(X2)) -> MINUSA_IN_GGA(X1, 0, X2) MINUSA_IN_GGA(s(X1), s(X2), X3) -> U3_GGA(X1, X2, X3, leB_in_gga(X1, X2, X4)) MINUSA_IN_GGA(s(X1), s(X2), X3) -> LEB_IN_GGA(X1, X2, X4) LEB_IN_GGA(s(X1), s(X2), X3) -> U1_GGA(X1, X2, X3, leB_in_gga(X1, X2, X3)) LEB_IN_GGA(s(X1), s(X2), X3) -> LEB_IN_GGA(X1, X2, X3) MINUSA_IN_GGA(s(X1), s(X2), s(X3)) -> U4_GGA(X1, X2, X3, lecB_in_ggg(X1, X2, false)) U4_GGA(X1, X2, X3, lecB_out_ggg(X1, X2, false)) -> U5_GGA(X1, X2, X3, minusA_in_gga(X1, s(X2), X3)) U4_GGA(X1, X2, X3, lecB_out_ggg(X1, X2, false)) -> MINUSA_IN_GGA(X1, s(X2), X3) MINUSA_IN_GAA(s(X1), s(X2), X3) -> U3_GAA(X1, X2, X3, leB_in_gaa(X1, X2, X4)) MINUSA_IN_GAA(s(X1), s(X2), X3) -> LEB_IN_GAA(X1, X2, X4) LEB_IN_GAA(s(X1), s(X2), X3) -> U1_GAA(X1, X2, X3, leB_in_gaa(X1, X2, X3)) LEB_IN_GAA(s(X1), s(X2), X3) -> LEB_IN_GAA(X1, X2, X3) MINUSA_IN_GAA(s(X1), s(X2), s(X3)) -> U4_GAA(X1, X2, X3, lecB_in_gag(X1, X2, false)) U4_GAA(X1, X2, X3, lecB_out_gag(X1, X2, false)) -> U5_GAA(X1, X2, X3, minusA_in_gaa(X1, s(X2), X3)) U4_GAA(X1, X2, X3, lecB_out_gag(X1, X2, false)) -> MINUSA_IN_GAA(X1, s(X2), X3) The TRS R consists of the following rules: lecB_in_ggg(0, X1, true) -> lecB_out_ggg(0, X1, true) lecB_in_ggg(s(X1), 0, false) -> lecB_out_ggg(s(X1), 0, false) lecB_in_ggg(s(X1), s(X2), X3) -> U11_ggg(X1, X2, X3, lecB_in_ggg(X1, X2, X3)) U11_ggg(X1, X2, X3, lecB_out_ggg(X1, X2, X3)) -> lecB_out_ggg(s(X1), s(X2), X3) lecB_in_gag(0, X1, true) -> lecB_out_gag(0, X1, true) lecB_in_gag(s(X1), 0, false) -> lecB_out_gag(s(X1), 0, false) lecB_in_gag(s(X1), s(X2), X3) -> U11_gag(X1, X2, X3, lecB_in_gag(X1, X2, X3)) U11_gag(X1, X2, X3, lecB_out_gag(X1, X2, X3)) -> lecB_out_gag(s(X1), s(X2), X3) The argument filtering Pi contains the following mapping: minusA_in_gaa(x1, x2, x3) = minusA_in_gaa(x1) s(x1) = s(x1) minusA_in_gga(x1, x2, x3) = minusA_in_gga(x1, x2) 0 = 0 leB_in_gga(x1, x2, x3) = leB_in_gga(x1, x2) lecB_in_ggg(x1, x2, x3) = lecB_in_ggg(x1, x2, x3) true = true lecB_out_ggg(x1, x2, x3) = lecB_out_ggg(x1, x2, x3) false = false U11_ggg(x1, x2, x3, x4) = U11_ggg(x1, x2, x3, x4) leB_in_gaa(x1, x2, x3) = leB_in_gaa(x1) lecB_in_gag(x1, x2, x3) = lecB_in_gag(x1, x3) lecB_out_gag(x1, x2, x3) = lecB_out_gag(x1, x3) U11_gag(x1, x2, x3, x4) = U11_gag(x1, x3, x4) MINUSA_IN_GAA(x1, x2, x3) = MINUSA_IN_GAA(x1) U2_GAA(x1, x2, x3) = U2_GAA(x1, x3) MINUSA_IN_GGA(x1, x2, x3) = MINUSA_IN_GGA(x1, x2) U2_GGA(x1, x2, x3) = U2_GGA(x1, x3) U3_GGA(x1, x2, x3, x4) = U3_GGA(x1, x2, x4) LEB_IN_GGA(x1, x2, x3) = LEB_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4) = U1_GGA(x1, x2, x4) U4_GGA(x1, x2, x3, x4) = U4_GGA(x1, x2, x4) U5_GGA(x1, x2, x3, x4) = U5_GGA(x1, x2, x4) U3_GAA(x1, x2, x3, x4) = U3_GAA(x1, x4) LEB_IN_GAA(x1, x2, x3) = LEB_IN_GAA(x1) U1_GAA(x1, x2, x3, x4) = U1_GAA(x1, x4) U4_GAA(x1, x2, x3, x4) = U4_GAA(x1, x4) U5_GAA(x1, x2, x3, x4) = U5_GAA(x1, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 5 SCCs with 11 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: LEB_IN_GAA(s(X1), s(X2), X3) -> LEB_IN_GAA(X1, X2, X3) The TRS R consists of the following rules: lecB_in_ggg(0, X1, true) -> lecB_out_ggg(0, X1, true) lecB_in_ggg(s(X1), 0, false) -> lecB_out_ggg(s(X1), 0, false) lecB_in_ggg(s(X1), s(X2), X3) -> U11_ggg(X1, X2, X3, lecB_in_ggg(X1, X2, X3)) U11_ggg(X1, X2, X3, lecB_out_ggg(X1, X2, X3)) -> lecB_out_ggg(s(X1), s(X2), X3) lecB_in_gag(0, X1, true) -> lecB_out_gag(0, X1, true) lecB_in_gag(s(X1), 0, false) -> lecB_out_gag(s(X1), 0, false) lecB_in_gag(s(X1), s(X2), X3) -> U11_gag(X1, X2, X3, lecB_in_gag(X1, X2, X3)) U11_gag(X1, X2, X3, lecB_out_gag(X1, X2, X3)) -> lecB_out_gag(s(X1), s(X2), X3) The argument filtering Pi contains the following mapping: s(x1) = s(x1) 0 = 0 lecB_in_ggg(x1, x2, x3) = lecB_in_ggg(x1, x2, x3) true = true lecB_out_ggg(x1, x2, x3) = lecB_out_ggg(x1, x2, x3) false = false U11_ggg(x1, x2, x3, x4) = U11_ggg(x1, x2, x3, x4) lecB_in_gag(x1, x2, x3) = lecB_in_gag(x1, x3) lecB_out_gag(x1, x2, x3) = lecB_out_gag(x1, x3) U11_gag(x1, x2, x3, x4) = U11_gag(x1, x3, x4) LEB_IN_GAA(x1, x2, x3) = LEB_IN_GAA(x1) 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: LEB_IN_GAA(s(X1), s(X2), X3) -> LEB_IN_GAA(X1, X2, X3) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) LEB_IN_GAA(x1, x2, x3) = LEB_IN_GAA(x1) 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: LEB_IN_GAA(s(X1)) -> LEB_IN_GAA(X1) 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: *LEB_IN_GAA(s(X1)) -> LEB_IN_GAA(X1) The graph contains the following edges 1 > 1 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Pi DP problem: The TRS P consists of the following rules: MINUSA_IN_GAA(s(X1), s(X2), s(X3)) -> U4_GAA(X1, X2, X3, lecB_in_gag(X1, X2, false)) U4_GAA(X1, X2, X3, lecB_out_gag(X1, X2, false)) -> MINUSA_IN_GAA(X1, s(X2), X3) The TRS R consists of the following rules: lecB_in_ggg(0, X1, true) -> lecB_out_ggg(0, X1, true) lecB_in_ggg(s(X1), 0, false) -> lecB_out_ggg(s(X1), 0, false) lecB_in_ggg(s(X1), s(X2), X3) -> U11_ggg(X1, X2, X3, lecB_in_ggg(X1, X2, X3)) U11_ggg(X1, X2, X3, lecB_out_ggg(X1, X2, X3)) -> lecB_out_ggg(s(X1), s(X2), X3) lecB_in_gag(0, X1, true) -> lecB_out_gag(0, X1, true) lecB_in_gag(s(X1), 0, false) -> lecB_out_gag(s(X1), 0, false) lecB_in_gag(s(X1), s(X2), X3) -> U11_gag(X1, X2, X3, lecB_in_gag(X1, X2, X3)) U11_gag(X1, X2, X3, lecB_out_gag(X1, X2, X3)) -> lecB_out_gag(s(X1), s(X2), X3) The argument filtering Pi contains the following mapping: s(x1) = s(x1) 0 = 0 lecB_in_ggg(x1, x2, x3) = lecB_in_ggg(x1, x2, x3) true = true lecB_out_ggg(x1, x2, x3) = lecB_out_ggg(x1, x2, x3) false = false U11_ggg(x1, x2, x3, x4) = U11_ggg(x1, x2, x3, x4) lecB_in_gag(x1, x2, x3) = lecB_in_gag(x1, x3) lecB_out_gag(x1, x2, x3) = lecB_out_gag(x1, x3) U11_gag(x1, x2, x3, x4) = U11_gag(x1, x3, x4) MINUSA_IN_GAA(x1, x2, x3) = MINUSA_IN_GAA(x1) U4_GAA(x1, x2, x3, x4) = U4_GAA(x1, x4) 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: MINUSA_IN_GAA(s(X1), s(X2), s(X3)) -> U4_GAA(X1, X2, X3, lecB_in_gag(X1, X2, false)) U4_GAA(X1, X2, X3, lecB_out_gag(X1, X2, false)) -> MINUSA_IN_GAA(X1, s(X2), X3) The TRS R consists of the following rules: lecB_in_gag(s(X1), 0, false) -> lecB_out_gag(s(X1), 0, false) lecB_in_gag(s(X1), s(X2), X3) -> U11_gag(X1, X2, X3, lecB_in_gag(X1, X2, X3)) U11_gag(X1, X2, X3, lecB_out_gag(X1, X2, X3)) -> lecB_out_gag(s(X1), s(X2), X3) lecB_in_gag(0, X1, true) -> lecB_out_gag(0, X1, true) The argument filtering Pi contains the following mapping: s(x1) = s(x1) 0 = 0 true = true false = false lecB_in_gag(x1, x2, x3) = lecB_in_gag(x1, x3) lecB_out_gag(x1, x2, x3) = lecB_out_gag(x1, x3) U11_gag(x1, x2, x3, x4) = U11_gag(x1, x3, x4) MINUSA_IN_GAA(x1, x2, x3) = MINUSA_IN_GAA(x1) U4_GAA(x1, x2, x3, x4) = U4_GAA(x1, x4) 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: MINUSA_IN_GAA(s(X1)) -> U4_GAA(X1, lecB_in_gag(X1, false)) U4_GAA(X1, lecB_out_gag(X1, false)) -> MINUSA_IN_GAA(X1) The TRS R consists of the following rules: lecB_in_gag(s(X1), false) -> lecB_out_gag(s(X1), false) lecB_in_gag(s(X1), X3) -> U11_gag(X1, X3, lecB_in_gag(X1, X3)) U11_gag(X1, X3, lecB_out_gag(X1, X3)) -> lecB_out_gag(s(X1), X3) lecB_in_gag(0, true) -> lecB_out_gag(0, true) The set Q consists of the following terms: lecB_in_gag(x0, x1) U11_gag(x0, x1, x2) 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: *U4_GAA(X1, lecB_out_gag(X1, false)) -> MINUSA_IN_GAA(X1) The graph contains the following edges 1 >= 1, 2 > 1 *MINUSA_IN_GAA(s(X1)) -> U4_GAA(X1, lecB_in_gag(X1, false)) The graph contains the following edges 1 > 1 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Pi DP problem: The TRS P consists of the following rules: LEB_IN_GGA(s(X1), s(X2), X3) -> LEB_IN_GGA(X1, X2, X3) The TRS R consists of the following rules: lecB_in_ggg(0, X1, true) -> lecB_out_ggg(0, X1, true) lecB_in_ggg(s(X1), 0, false) -> lecB_out_ggg(s(X1), 0, false) lecB_in_ggg(s(X1), s(X2), X3) -> U11_ggg(X1, X2, X3, lecB_in_ggg(X1, X2, X3)) U11_ggg(X1, X2, X3, lecB_out_ggg(X1, X2, X3)) -> lecB_out_ggg(s(X1), s(X2), X3) lecB_in_gag(0, X1, true) -> lecB_out_gag(0, X1, true) lecB_in_gag(s(X1), 0, false) -> lecB_out_gag(s(X1), 0, false) lecB_in_gag(s(X1), s(X2), X3) -> U11_gag(X1, X2, X3, lecB_in_gag(X1, X2, X3)) U11_gag(X1, X2, X3, lecB_out_gag(X1, X2, X3)) -> lecB_out_gag(s(X1), s(X2), X3) The argument filtering Pi contains the following mapping: s(x1) = s(x1) 0 = 0 lecB_in_ggg(x1, x2, x3) = lecB_in_ggg(x1, x2, x3) true = true lecB_out_ggg(x1, x2, x3) = lecB_out_ggg(x1, x2, x3) false = false U11_ggg(x1, x2, x3, x4) = U11_ggg(x1, x2, x3, x4) lecB_in_gag(x1, x2, x3) = lecB_in_gag(x1, x3) lecB_out_gag(x1, x2, x3) = lecB_out_gag(x1, x3) U11_gag(x1, x2, x3, x4) = U11_gag(x1, x3, x4) LEB_IN_GGA(x1, x2, x3) = LEB_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: LEB_IN_GGA(s(X1), s(X2), X3) -> LEB_IN_GGA(X1, X2, X3) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) LEB_IN_GGA(x1, x2, x3) = LEB_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: LEB_IN_GGA(s(X1), s(X2)) -> LEB_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: *LEB_IN_GGA(s(X1), s(X2)) -> LEB_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: MINUSA_IN_GGA(s(X1), s(X2), s(X3)) -> U4_GGA(X1, X2, X3, lecB_in_ggg(X1, X2, false)) U4_GGA(X1, X2, X3, lecB_out_ggg(X1, X2, false)) -> MINUSA_IN_GGA(X1, s(X2), X3) The TRS R consists of the following rules: lecB_in_ggg(0, X1, true) -> lecB_out_ggg(0, X1, true) lecB_in_ggg(s(X1), 0, false) -> lecB_out_ggg(s(X1), 0, false) lecB_in_ggg(s(X1), s(X2), X3) -> U11_ggg(X1, X2, X3, lecB_in_ggg(X1, X2, X3)) U11_ggg(X1, X2, X3, lecB_out_ggg(X1, X2, X3)) -> lecB_out_ggg(s(X1), s(X2), X3) lecB_in_gag(0, X1, true) -> lecB_out_gag(0, X1, true) lecB_in_gag(s(X1), 0, false) -> lecB_out_gag(s(X1), 0, false) lecB_in_gag(s(X1), s(X2), X3) -> U11_gag(X1, X2, X3, lecB_in_gag(X1, X2, X3)) U11_gag(X1, X2, X3, lecB_out_gag(X1, X2, X3)) -> lecB_out_gag(s(X1), s(X2), X3) The argument filtering Pi contains the following mapping: s(x1) = s(x1) 0 = 0 lecB_in_ggg(x1, x2, x3) = lecB_in_ggg(x1, x2, x3) true = true lecB_out_ggg(x1, x2, x3) = lecB_out_ggg(x1, x2, x3) false = false U11_ggg(x1, x2, x3, x4) = U11_ggg(x1, x2, x3, x4) lecB_in_gag(x1, x2, x3) = lecB_in_gag(x1, x3) lecB_out_gag(x1, x2, x3) = lecB_out_gag(x1, x3) U11_gag(x1, x2, x3, x4) = U11_gag(x1, x3, x4) MINUSA_IN_GGA(x1, x2, x3) = MINUSA_IN_GGA(x1, x2) U4_GGA(x1, x2, x3, x4) = U4_GGA(x1, x2, x4) 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: MINUSA_IN_GGA(s(X1), s(X2), s(X3)) -> U4_GGA(X1, X2, X3, lecB_in_ggg(X1, X2, false)) U4_GGA(X1, X2, X3, lecB_out_ggg(X1, X2, false)) -> MINUSA_IN_GGA(X1, s(X2), X3) The TRS R consists of the following rules: lecB_in_ggg(s(X1), 0, false) -> lecB_out_ggg(s(X1), 0, false) lecB_in_ggg(s(X1), s(X2), X3) -> U11_ggg(X1, X2, X3, lecB_in_ggg(X1, X2, X3)) U11_ggg(X1, X2, X3, lecB_out_ggg(X1, X2, X3)) -> lecB_out_ggg(s(X1), s(X2), X3) lecB_in_ggg(0, X1, true) -> lecB_out_ggg(0, X1, true) The argument filtering Pi contains the following mapping: s(x1) = s(x1) 0 = 0 lecB_in_ggg(x1, x2, x3) = lecB_in_ggg(x1, x2, x3) true = true lecB_out_ggg(x1, x2, x3) = lecB_out_ggg(x1, x2, x3) false = false U11_ggg(x1, x2, x3, x4) = U11_ggg(x1, x2, x3, x4) MINUSA_IN_GGA(x1, x2, x3) = MINUSA_IN_GGA(x1, x2) U4_GGA(x1, x2, x3, x4) = U4_GGA(x1, x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (31) PiDPToQDPProof (SOUND) 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: MINUSA_IN_GGA(s(X1), s(X2)) -> U4_GGA(X1, X2, lecB_in_ggg(X1, X2, false)) U4_GGA(X1, X2, lecB_out_ggg(X1, X2, false)) -> MINUSA_IN_GGA(X1, s(X2)) The TRS R consists of the following rules: lecB_in_ggg(s(X1), 0, false) -> lecB_out_ggg(s(X1), 0, false) lecB_in_ggg(s(X1), s(X2), X3) -> U11_ggg(X1, X2, X3, lecB_in_ggg(X1, X2, X3)) U11_ggg(X1, X2, X3, lecB_out_ggg(X1, X2, X3)) -> lecB_out_ggg(s(X1), s(X2), X3) lecB_in_ggg(0, X1, true) -> lecB_out_ggg(0, X1, true) The set Q consists of the following terms: lecB_in_ggg(x0, x1, x2) U11_ggg(x0, x1, x2, x3) 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: *U4_GGA(X1, X2, lecB_out_ggg(X1, X2, false)) -> MINUSA_IN_GGA(X1, s(X2)) The graph contains the following edges 1 >= 1, 3 > 1 *MINUSA_IN_GGA(s(X1), s(X2)) -> U4_GGA(X1, X2, lecB_in_ggg(X1, X2, false)) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (34) YES ---------------------------------------- (35) Obligation: Pi DP problem: The TRS P consists of the following rules: MINUSA_IN_GGA(s(X1), 0, s(X2)) -> MINUSA_IN_GGA(X1, 0, X2) The TRS R consists of the following rules: lecB_in_ggg(0, X1, true) -> lecB_out_ggg(0, X1, true) lecB_in_ggg(s(X1), 0, false) -> lecB_out_ggg(s(X1), 0, false) lecB_in_ggg(s(X1), s(X2), X3) -> U11_ggg(X1, X2, X3, lecB_in_ggg(X1, X2, X3)) U11_ggg(X1, X2, X3, lecB_out_ggg(X1, X2, X3)) -> lecB_out_ggg(s(X1), s(X2), X3) lecB_in_gag(0, X1, true) -> lecB_out_gag(0, X1, true) lecB_in_gag(s(X1), 0, false) -> lecB_out_gag(s(X1), 0, false) lecB_in_gag(s(X1), s(X2), X3) -> U11_gag(X1, X2, X3, lecB_in_gag(X1, X2, X3)) U11_gag(X1, X2, X3, lecB_out_gag(X1, X2, X3)) -> lecB_out_gag(s(X1), s(X2), X3) The argument filtering Pi contains the following mapping: s(x1) = s(x1) 0 = 0 lecB_in_ggg(x1, x2, x3) = lecB_in_ggg(x1, x2, x3) true = true lecB_out_ggg(x1, x2, x3) = lecB_out_ggg(x1, x2, x3) false = false U11_ggg(x1, x2, x3, x4) = U11_ggg(x1, x2, x3, x4) lecB_in_gag(x1, x2, x3) = lecB_in_gag(x1, x3) lecB_out_gag(x1, x2, x3) = lecB_out_gag(x1, x3) U11_gag(x1, x2, x3, x4) = U11_gag(x1, x3, x4) MINUSA_IN_GGA(x1, x2, x3) = MINUSA_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (36) UsableRulesProof (EQUIVALENT) For (infinitary) constructor rewriting [LOPSTR] we can delete all non-usable rules from R. ---------------------------------------- (37) Obligation: Pi DP problem: The TRS P consists of the following rules: MINUSA_IN_GGA(s(X1), 0, s(X2)) -> MINUSA_IN_GGA(X1, 0, X2) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) 0 = 0 MINUSA_IN_GGA(x1, x2, x3) = MINUSA_IN_GGA(x1, x2) We have to consider all (P,R,Pi)-chains ---------------------------------------- (38) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: MINUSA_IN_GGA(s(X1), 0) -> MINUSA_IN_GGA(X1, 0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (40) 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: *MINUSA_IN_GGA(s(X1), 0) -> MINUSA_IN_GGA(X1, 0) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (41) YES