/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.pl /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Left Termination of the query pattern mul(g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 0 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 ---------------------------------------- (0) Obligation: Clauses: mul(X1, 0, Z) :- ','(!, eq(Z, 0)). mul(X, Y, Z) :- ','(p(Y, P), ','(mul(X, P, V), add(X, V, Z))). add(X, 0, Z) :- ','(!, eq(Z, X)). add(X, Y, Z) :- ','(p(Y, V), ','(add(X, V, W), p(Z, W))). p(0, 0). p(s(X), X). eq(X, X). Query: mul(g,g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 19, "program": { "directives": [], "clauses": [ [ "(mul X1 (0) Z)", "(',' (!) (eq Z (0)))" ], [ "(mul X Y Z)", "(',' (p Y P) (',' (mul X P V) (add X V Z)))" ], [ "(add X (0) Z)", "(',' (!) (eq Z X))" ], [ "(add X Y Z)", "(',' (p Y V) (',' (add X V W) (p Z W)))" ], [ "(p (0) (0))", null ], [ "(p (s X) X)", null ], [ "(eq X X)", null ] ] }, "graph": { "nodes": { "type": "Nodes", "350": { "goal": [ { "clause": 2, "scope": 4, "term": "(add T15 T23 T18)" }, { "clause": 3, "scope": 4, "term": "(add T15 T23 T18)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T23" ], "free": [], "exprvars": [] } }, "394": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T46 X51) (',' (add T45 X51 X52) (p T48 X52)))" }], "kb": { "nonunifying": [[ "(add T45 T46 T18)", "(add X32 (0) X33)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T46" ], "free": [ "X32", "X33", "X51", "X52" ], "exprvars": [] } }, "351": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_4) (eq T33 T31))" }, { "clause": 3, "scope": 4, "term": "(add T31 (0) T18)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T31"], "free": [], "exprvars": [] } }, "373": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "330": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "352": { "goal": [{ "clause": 3, "scope": 4, "term": "(add T15 T23 T18)" }], "kb": { "nonunifying": [[ "(add T15 T23 T18)", "(add X32 (0) X33)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T23" ], "free": [ "X32", "X33" ], "exprvars": [] } }, "331": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "353": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq T33 T31)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T31"], "free": [], "exprvars": [] } }, "354": { "goal": [{ "clause": 6, "scope": 5, "term": "(eq T33 T31)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T31"], "free": [], "exprvars": [] } }, "398": { "goal": [ { "clause": 4, "scope": 6, "term": "(',' (p T46 X51) (',' (add T45 X51 X52) (p T48 X52)))" }, { "clause": 5, "scope": 6, "term": "(',' (p T46 X51) (',' (add T45 X51 X52) (p T48 X52)))" } ], "kb": { "nonunifying": [[ "(add T45 T46 T18)", "(add X32 (0) X33)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T46" ], "free": [ "X32", "X33", "X51", "X52" ], "exprvars": [] } }, "333": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "355": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "410": { "goal": [{ "clause": 5, "scope": 7, "term": "(p T48 T54)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T54"], "free": [], "exprvars": [] } }, "356": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "335": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p T16 X15) (',' (mul T15 X15 X16) (add T15 X16 T18)))" }], "kb": { "nonunifying": [[ "(mul T15 T16 T3)", "(mul X4 (0) X5)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T16" ], "free": [ "X4", "X5", "X15", "X16" ], "exprvars": [] } }, "413": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "337": { "goal": [ { "clause": 4, "scope": 3, "term": "(',' (p T16 X15) (',' (mul T15 X15 X16) (add T15 X16 T18)))" }, { "clause": 5, "scope": 3, "term": "(',' (p T16 X15) (',' (mul T15 X15 X16) (add T15 X16 T18)))" } ], "kb": { "nonunifying": [[ "(mul T15 T16 T3)", "(mul X4 (0) X5)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T16" ], "free": [ "X4", "X5", "X15", "X16" ], "exprvars": [] } }, "414": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "415": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "339": { "goal": [{ "clause": 5, "scope": 3, "term": "(',' (p T16 X15) (',' (mul T15 X15 X16) (add T15 X16 T18)))" }], "kb": { "nonunifying": [[ "(mul T15 T16 T3)", "(mul X4 (0) X5)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T16" ], "free": [ "X4", "X5", "X15", "X16" ], "exprvars": [] } }, "416": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "419": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "19": { "goal": [{ "clause": -1, "scope": -1, "term": "(mul T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "341": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (mul T15 T21 X16) (add T15 X16 T18))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T21" ], "free": ["X16"], "exprvars": [] } }, "342": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "420": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "322": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (!_1) (eq T8 (0)))" }, { "clause": 1, "scope": 1, "term": "(mul T6 (0) T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "323": { "goal": [{ "clause": 1, "scope": 1, "term": "(mul T1 T2 T3)" }], "kb": { "nonunifying": [[ "(mul T1 T2 T3)", "(mul X4 (0) X5)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [ "X4", "X5" ], "exprvars": [] } }, "400": { "goal": [{ "clause": 5, "scope": 6, "term": "(',' (p T46 X51) (',' (add T45 X51 X52) (p T48 X52)))" }], "kb": { "nonunifying": [[ "(add T45 T46 T18)", "(add X32 (0) X33)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T46" ], "free": [ "X32", "X33", "X51", "X52" ], "exprvars": [] } }, "324": { "goal": [{ "clause": -1, "scope": -1, "term": "(eq T8 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "346": { "goal": [{ "clause": -1, "scope": -1, "term": "(mul T15 T21 X16)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T21" ], "free": ["X16"], "exprvars": [] } }, "401": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (add T45 T52 X52) (p T48 X52))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T52" ], "free": ["X52"], "exprvars": [] } }, "402": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "326": { "goal": [{ "clause": 6, "scope": 2, "term": "(eq T8 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "348": { "goal": [{ "clause": -1, "scope": -1, "term": "(add T15 T23 T18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T23" ], "free": [], "exprvars": [] } }, "404": { "goal": [{ "clause": -1, "scope": -1, "term": "(add T45 T52 X52)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T45", "T52" ], "free": ["X52"], "exprvars": [] } }, "405": { "goal": [{ "clause": -1, "scope": -1, "term": "(p T48 T54)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T54"], "free": [], "exprvars": [] } }, "408": { "goal": [ { "clause": 4, "scope": 7, "term": "(p T48 T54)" }, { "clause": 5, "scope": 7, "term": "(p T48 T54)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T54"], "free": [], "exprvars": [] } }, "409": { "goal": [{ "clause": 4, "scope": 7, "term": "(p T48 T54)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T54"], "free": [], "exprvars": [] } }, "21": { "goal": [ { "clause": 0, "scope": 1, "term": "(mul T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(mul T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } } }, "edges": [ { "from": 19, "to": 21, "label": "CASE" }, { "from": 21, "to": 322, "label": "EVAL with clause\nmul(X4, 0, X5) :- ','(!_1, eq(X5, 0)).\nand substitutionT1 -> T6,\nX4 -> T6,\nT2 -> 0,\nT3 -> T8,\nX5 -> T8,\nT7 -> T8" }, { "from": 21, "to": 323, "label": "EVAL-BACKTRACK" }, { "from": 322, "to": 324, "label": "CUT" }, { "from": 323, "to": 335, "label": "ONLY EVAL with clause\nmul(X12, X13, X14) :- ','(p(X13, X15), ','(mul(X12, X15, X16), add(X12, X16, X14))).\nand substitutionT1 -> T15,\nX12 -> T15,\nT2 -> T16,\nX13 -> T16,\nT3 -> T18,\nX14 -> T18,\nT17 -> T18" }, { "from": 324, "to": 326, "label": "CASE" }, { "from": 326, "to": 330, "label": "EVAL with clause\neq(X8, X8).\nand substitutionT8 -> 0,\nX8 -> 0,\nT11 -> 0" }, { "from": 326, "to": 331, "label": "EVAL-BACKTRACK" }, { "from": 330, "to": 333, "label": "SUCCESS" }, { "from": 335, "to": 337, "label": "CASE" }, { "from": 337, "to": 339, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (mul(T15, T16, T3), mul(X4, 0, X5))" }, { "from": 339, "to": 341, "label": "EVAL with clause\np(s(X19), X19).\nand substitutionX19 -> T21,\nT16 -> s(T21),\nX15 -> T21" }, { "from": 339, "to": 342, "label": "EVAL-BACKTRACK" }, { "from": 341, "to": 346, "label": "SPLIT 1" }, { "from": 341, "to": 348, "label": "SPLIT 2\nnew knowledge:\nT15 is ground\nT21 is ground\nT23 is ground\nreplacements:X16 -> T23" }, { "from": 346, "to": 19, "label": "INSTANCE with matching:\nT1 -> T15\nT2 -> T21\nT3 -> X16" }, { "from": 348, "to": 350, "label": "CASE" }, { "from": 350, "to": 351, "label": "EVAL with clause\nadd(X32, 0, X33) :- ','(!_4, eq(X33, X32)).\nand substitutionT15 -> T31,\nX32 -> T31,\nT23 -> 0,\nT18 -> T33,\nX33 -> T33,\nT32 -> T33" }, { "from": 350, "to": 352, "label": "EVAL-BACKTRACK" }, { "from": 351, "to": 353, "label": "CUT" }, { "from": 352, "to": 394, "label": "ONLY EVAL with clause\nadd(X48, X49, X50) :- ','(p(X49, X51), ','(add(X48, X51, X52), p(X50, X52))).\nand substitutionT15 -> T45,\nX48 -> T45,\nT23 -> T46,\nX49 -> T46,\nT18 -> T48,\nX50 -> T48,\nT47 -> T48" }, { "from": 353, "to": 354, "label": "CASE" }, { "from": 354, "to": 355, "label": "EVAL with clause\neq(X36, X36).\nand substitutionT33 -> T36,\nX36 -> T36,\nT31 -> T36" }, { "from": 354, "to": 356, "label": "EVAL-BACKTRACK" }, { "from": 355, "to": 373, "label": "SUCCESS" }, { "from": 394, "to": 398, "label": "CASE" }, { "from": 398, "to": 400, "label": "BACKTRACK\nfor clause: p(0, 0)\nwith clash: (add(T45, T46, T18), add(X32, 0, X33))" }, { "from": 400, "to": 401, "label": "EVAL with clause\np(s(X58), X58).\nand substitutionX58 -> T52,\nT46 -> s(T52),\nX51 -> T52" }, { "from": 400, "to": 402, "label": "EVAL-BACKTRACK" }, { "from": 401, "to": 404, "label": "SPLIT 1" }, { "from": 401, "to": 405, "label": "SPLIT 2\nnew knowledge:\nT45 is ground\nT52 is ground\nT54 is ground\nreplacements:X52 -> T54" }, { "from": 404, "to": 348, "label": "INSTANCE with matching:\nT15 -> T45\nT23 -> T52\nT18 -> X52" }, { "from": 405, "to": 408, "label": "CASE" }, { "from": 408, "to": 409, "label": "PARALLEL" }, { "from": 408, "to": 410, "label": "PARALLEL" }, { "from": 409, "to": 413, "label": "EVAL with clause\np(0, 0).\nand substitutionT48 -> 0,\nT54 -> 0" }, { "from": 409, "to": 414, "label": "EVAL-BACKTRACK" }, { "from": 410, "to": 416, "label": "EVAL with clause\np(s(X67), X67).\nand substitutionX67 -> T58,\nT48 -> s(T58),\nT54 -> T58" }, { "from": 410, "to": 419, "label": "EVAL-BACKTRACK" }, { "from": 413, "to": 415, "label": "SUCCESS" }, { "from": 416, "to": 420, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: addB(X1, s(X2), X3) :- addB(X1, X2, X4). mulA(X1, s(X2), X3) :- mulA(X1, X2, X4). mulA(X1, s(X2), X3) :- ','(mulcA(X1, X2, X4), addB(X1, X4, X3)). Clauses: mulcA(X1, 0, 0). mulcA(X1, s(X2), X3) :- ','(mulcA(X1, X2, X4), addcB(X1, X4, X3)). addcB(X1, 0, X1). addcB(X1, s(X2), 0) :- addcB(X1, X2, 0). addcB(X1, s(X2), s(X3)) :- addcB(X1, X2, X3). Afs: mulA(x1, x2, x3) = mulA(x1, 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: mulA_in_3: (b,b,f) mulcA_in_3: (b,b,f) addcB_in_3: (b,b,f) (b,b,b) addB_in_3: (b,b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: MULA_IN_GGA(X1, s(X2), X3) -> U2_GGA(X1, X2, X3, mulA_in_gga(X1, X2, X4)) MULA_IN_GGA(X1, s(X2), X3) -> MULA_IN_GGA(X1, X2, X4) MULA_IN_GGA(X1, s(X2), X3) -> U3_GGA(X1, X2, X3, mulcA_in_gga(X1, X2, X4)) U3_GGA(X1, X2, X3, mulcA_out_gga(X1, X2, X4)) -> U4_GGA(X1, X2, X3, addB_in_gga(X1, X4, X3)) U3_GGA(X1, X2, X3, mulcA_out_gga(X1, X2, X4)) -> ADDB_IN_GGA(X1, X4, X3) ADDB_IN_GGA(X1, s(X2), X3) -> U1_GGA(X1, X2, X3, addB_in_gga(X1, X2, X4)) ADDB_IN_GGA(X1, s(X2), X3) -> ADDB_IN_GGA(X1, X2, X4) The TRS R consists of the following rules: mulcA_in_gga(X1, 0, 0) -> mulcA_out_gga(X1, 0, 0) mulcA_in_gga(X1, s(X2), X3) -> U6_gga(X1, X2, X3, mulcA_in_gga(X1, X2, X4)) U6_gga(X1, X2, X3, mulcA_out_gga(X1, X2, X4)) -> U7_gga(X1, X2, X3, addcB_in_gga(X1, X4, X3)) addcB_in_gga(X1, 0, X1) -> addcB_out_gga(X1, 0, X1) addcB_in_gga(X1, s(X2), 0) -> U8_gga(X1, X2, addcB_in_ggg(X1, X2, 0)) addcB_in_ggg(X1, 0, X1) -> addcB_out_ggg(X1, 0, X1) addcB_in_ggg(X1, s(X2), 0) -> U8_ggg(X1, X2, addcB_in_ggg(X1, X2, 0)) addcB_in_ggg(X1, s(X2), s(X3)) -> U9_ggg(X1, X2, X3, addcB_in_ggg(X1, X2, X3)) U9_ggg(X1, X2, X3, addcB_out_ggg(X1, X2, X3)) -> addcB_out_ggg(X1, s(X2), s(X3)) U8_ggg(X1, X2, addcB_out_ggg(X1, X2, 0)) -> addcB_out_ggg(X1, s(X2), 0) U8_gga(X1, X2, addcB_out_ggg(X1, X2, 0)) -> addcB_out_gga(X1, s(X2), 0) addcB_in_gga(X1, s(X2), s(X3)) -> U9_gga(X1, X2, X3, addcB_in_gga(X1, X2, X3)) U9_gga(X1, X2, X3, addcB_out_gga(X1, X2, X3)) -> addcB_out_gga(X1, s(X2), s(X3)) U7_gga(X1, X2, X3, addcB_out_gga(X1, X4, X3)) -> mulcA_out_gga(X1, s(X2), X3) The argument filtering Pi contains the following mapping: mulA_in_gga(x1, x2, x3) = mulA_in_gga(x1, x2) s(x1) = s(x1) mulcA_in_gga(x1, x2, x3) = mulcA_in_gga(x1, x2) 0 = 0 mulcA_out_gga(x1, x2, x3) = mulcA_out_gga(x1, x2, x3) U6_gga(x1, x2, x3, x4) = U6_gga(x1, x2, x4) U7_gga(x1, x2, x3, x4) = U7_gga(x1, x2, x4) addcB_in_gga(x1, x2, x3) = addcB_in_gga(x1, x2) addcB_out_gga(x1, x2, x3) = addcB_out_gga(x1, x2, x3) U8_gga(x1, x2, x3) = U8_gga(x1, x2, x3) addcB_in_ggg(x1, x2, x3) = addcB_in_ggg(x1, x2, x3) addcB_out_ggg(x1, x2, x3) = addcB_out_ggg(x1, x2, x3) U8_ggg(x1, x2, x3) = U8_ggg(x1, x2, x3) U9_ggg(x1, x2, x3, x4) = U9_ggg(x1, x2, x3, x4) U9_gga(x1, x2, x3, x4) = U9_gga(x1, x2, x4) addB_in_gga(x1, x2, x3) = addB_in_gga(x1, x2) MULA_IN_GGA(x1, x2, x3) = MULA_IN_GGA(x1, x2) U2_GGA(x1, x2, x3, x4) = U2_GGA(x1, x2, x4) U3_GGA(x1, x2, x3, x4) = U3_GGA(x1, x2, x4) U4_GGA(x1, x2, x3, x4) = U4_GGA(x1, x2, x4) ADDB_IN_GGA(x1, x2, x3) = ADDB_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4) = U1_GGA(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: MULA_IN_GGA(X1, s(X2), X3) -> U2_GGA(X1, X2, X3, mulA_in_gga(X1, X2, X4)) MULA_IN_GGA(X1, s(X2), X3) -> MULA_IN_GGA(X1, X2, X4) MULA_IN_GGA(X1, s(X2), X3) -> U3_GGA(X1, X2, X3, mulcA_in_gga(X1, X2, X4)) U3_GGA(X1, X2, X3, mulcA_out_gga(X1, X2, X4)) -> U4_GGA(X1, X2, X3, addB_in_gga(X1, X4, X3)) U3_GGA(X1, X2, X3, mulcA_out_gga(X1, X2, X4)) -> ADDB_IN_GGA(X1, X4, X3) ADDB_IN_GGA(X1, s(X2), X3) -> U1_GGA(X1, X2, X3, addB_in_gga(X1, X2, X4)) ADDB_IN_GGA(X1, s(X2), X3) -> ADDB_IN_GGA(X1, X2, X4) The TRS R consists of the following rules: mulcA_in_gga(X1, 0, 0) -> mulcA_out_gga(X1, 0, 0) mulcA_in_gga(X1, s(X2), X3) -> U6_gga(X1, X2, X3, mulcA_in_gga(X1, X2, X4)) U6_gga(X1, X2, X3, mulcA_out_gga(X1, X2, X4)) -> U7_gga(X1, X2, X3, addcB_in_gga(X1, X4, X3)) addcB_in_gga(X1, 0, X1) -> addcB_out_gga(X1, 0, X1) addcB_in_gga(X1, s(X2), 0) -> U8_gga(X1, X2, addcB_in_ggg(X1, X2, 0)) addcB_in_ggg(X1, 0, X1) -> addcB_out_ggg(X1, 0, X1) addcB_in_ggg(X1, s(X2), 0) -> U8_ggg(X1, X2, addcB_in_ggg(X1, X2, 0)) addcB_in_ggg(X1, s(X2), s(X3)) -> U9_ggg(X1, X2, X3, addcB_in_ggg(X1, X2, X3)) U9_ggg(X1, X2, X3, addcB_out_ggg(X1, X2, X3)) -> addcB_out_ggg(X1, s(X2), s(X3)) U8_ggg(X1, X2, addcB_out_ggg(X1, X2, 0)) -> addcB_out_ggg(X1, s(X2), 0) U8_gga(X1, X2, addcB_out_ggg(X1, X2, 0)) -> addcB_out_gga(X1, s(X2), 0) addcB_in_gga(X1, s(X2), s(X3)) -> U9_gga(X1, X2, X3, addcB_in_gga(X1, X2, X3)) U9_gga(X1, X2, X3, addcB_out_gga(X1, X2, X3)) -> addcB_out_gga(X1, s(X2), s(X3)) U7_gga(X1, X2, X3, addcB_out_gga(X1, X4, X3)) -> mulcA_out_gga(X1, s(X2), X3) The argument filtering Pi contains the following mapping: mulA_in_gga(x1, x2, x3) = mulA_in_gga(x1, x2) s(x1) = s(x1) mulcA_in_gga(x1, x2, x3) = mulcA_in_gga(x1, x2) 0 = 0 mulcA_out_gga(x1, x2, x3) = mulcA_out_gga(x1, x2, x3) U6_gga(x1, x2, x3, x4) = U6_gga(x1, x2, x4) U7_gga(x1, x2, x3, x4) = U7_gga(x1, x2, x4) addcB_in_gga(x1, x2, x3) = addcB_in_gga(x1, x2) addcB_out_gga(x1, x2, x3) = addcB_out_gga(x1, x2, x3) U8_gga(x1, x2, x3) = U8_gga(x1, x2, x3) addcB_in_ggg(x1, x2, x3) = addcB_in_ggg(x1, x2, x3) addcB_out_ggg(x1, x2, x3) = addcB_out_ggg(x1, x2, x3) U8_ggg(x1, x2, x3) = U8_ggg(x1, x2, x3) U9_ggg(x1, x2, x3, x4) = U9_ggg(x1, x2, x3, x4) U9_gga(x1, x2, x3, x4) = U9_gga(x1, x2, x4) addB_in_gga(x1, x2, x3) = addB_in_gga(x1, x2) MULA_IN_GGA(x1, x2, x3) = MULA_IN_GGA'(x1, x2) U2_GGA(x1, x2, x3, x4) = U2_GGA(x1, x2, x4) U3_GGA(x1, x2, x3, x4) = U3_GGA(x1, x2, x4) U4_GGA(x1, x2, x3, x4) = U4_GGA(x1, x2, x4) ADDB_IN_GGA(x1, x2, x3) = ADDB_IN_GGA(x1, x2) U1_GGA(x1, x2, x3, x4) = U1_GGA(x1, x2, x4) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 2 SCCs with 5 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Pi DP problem: The TRS P consists of the following rules: ADDB_IN_GGA(X1, s(X2), X3) -> ADDB_IN_GGA(X1, X2, X4) The TRS R consists of the following rules: mulcA_in_gga(X1, 0, 0) -> mulcA_out_gga(X1, 0, 0) mulcA_in_gga(X1, s(X2), X3) -> U6_gga(X1, X2, X3, mulcA_in_gga(X1, X2, X4)) U6_gga(X1, X2, X3, mulcA_out_gga(X1, X2, X4)) -> U7_gga(X1, X2, X3, addcB_in_gga(X1, X4, X3)) addcB_in_gga(X1, 0, X1) -> addcB_out_gga(X1, 0, X1) addcB_in_gga(X1, s(X2), 0) -> U8_gga(X1, X2, addcB_in_ggg(X1, X2, 0)) addcB_in_ggg(X1, 0, X1) -> addcB_out_ggg(X1, 0, X1) addcB_in_ggg(X1, s(X2), 0) -> U8_ggg(X1, X2, addcB_in_ggg(X1, X2, 0)) addcB_in_ggg(X1, s(X2), s(X3)) -> U9_ggg(X1, X2, X3, addcB_in_ggg(X1, X2, X3)) U9_ggg(X1, X2, X3, addcB_out_ggg(X1, X2, X3)) -> addcB_out_ggg(X1, s(X2), s(X3)) U8_ggg(X1, X2, addcB_out_ggg(X1, X2, 0)) -> addcB_out_ggg(X1, s(X2), 0) U8_gga(X1, X2, addcB_out_ggg(X1, X2, 0)) -> addcB_out_gga(X1, s(X2), 0) addcB_in_gga(X1, s(X2), s(X3)) -> U9_gga(X1, X2, X3, addcB_in_gga(X1, X2, X3)) U9_gga(X1, X2, X3, addcB_out_gga(X1, X2, X3)) -> addcB_out_gga(X1, s(X2), s(X3)) U7_gga(X1, X2, X3, addcB_out_gga(X1, X4, X3)) -> mulcA_out_gga(X1, s(X2), X3) The argument filtering Pi contains the following mapping: s(x1) = s(x1) mulcA_in_gga(x1, x2, x3) = mulcA_in_gga(x1, x2) 0 = 0 mulcA_out_gga(x1, x2, x3) = mulcA_out_gga(x1, x2, x3) U6_gga(x1, x2, x3, x4) = U6_gga(x1, x2, x4) U7_gga(x1, x2, x3, x4) = U7_gga(x1, x2, x4) addcB_in_gga(x1, x2, x3) = addcB_in_gga(x1, x2) addcB_out_gga(x1, x2, x3) = addcB_out_gga(x1, x2, x3) U8_gga(x1, x2, x3) = U8_gga(x1, x2, x3) addcB_in_ggg(x1, x2, x3) = addcB_in_ggg(x1, x2, x3) addcB_out_ggg(x1, x2, x3) = addcB_out_ggg(x1, x2, x3) U8_ggg(x1, x2, x3) = U8_ggg(x1, x2, x3) U9_ggg(x1, x2, x3, x4) = U9_ggg(x1, x2, x3, x4) U9_gga(x1, x2, x3, x4) = U9_gga(x1, x2, x4) ADDB_IN_GGA(x1, x2, x3) = ADDB_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: ADDB_IN_GGA(X1, s(X2), X3) -> ADDB_IN_GGA(X1, X2, X4) 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 ---------------------------------------- (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: ADDB_IN_GGA(X1, s(X2)) -> ADDB_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: *ADDB_IN_GGA(X1, s(X2)) -> ADDB_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: MULA_IN_GGA(X1, s(X2), X3) -> MULA_IN_GGA(X1, X2, X4) The TRS R consists of the following rules: mulcA_in_gga(X1, 0, 0) -> mulcA_out_gga(X1, 0, 0) mulcA_in_gga(X1, s(X2), X3) -> U6_gga(X1, X2, X3, mulcA_in_gga(X1, X2, X4)) U6_gga(X1, X2, X3, mulcA_out_gga(X1, X2, X4)) -> U7_gga(X1, X2, X3, addcB_in_gga(X1, X4, X3)) addcB_in_gga(X1, 0, X1) -> addcB_out_gga(X1, 0, X1) addcB_in_gga(X1, s(X2), 0) -> U8_gga(X1, X2, addcB_in_ggg(X1, X2, 0)) addcB_in_ggg(X1, 0, X1) -> addcB_out_ggg(X1, 0, X1) addcB_in_ggg(X1, s(X2), 0) -> U8_ggg(X1, X2, addcB_in_ggg(X1, X2, 0)) addcB_in_ggg(X1, s(X2), s(X3)) -> U9_ggg(X1, X2, X3, addcB_in_ggg(X1, X2, X3)) U9_ggg(X1, X2, X3, addcB_out_ggg(X1, X2, X3)) -> addcB_out_ggg(X1, s(X2), s(X3)) U8_ggg(X1, X2, addcB_out_ggg(X1, X2, 0)) -> addcB_out_ggg(X1, s(X2), 0) U8_gga(X1, X2, addcB_out_ggg(X1, X2, 0)) -> addcB_out_gga(X1, s(X2), 0) addcB_in_gga(X1, s(X2), s(X3)) -> U9_gga(X1, X2, X3, addcB_in_gga(X1, X2, X3)) U9_gga(X1, X2, X3, addcB_out_gga(X1, X2, X3)) -> addcB_out_gga(X1, s(X2), s(X3)) U7_gga(X1, X2, X3, addcB_out_gga(X1, X4, X3)) -> mulcA_out_gga(X1, s(X2), X3) The argument filtering Pi contains the following mapping: s(x1) = s(x1) mulcA_in_gga(x1, x2, x3) = mulcA_in_gga(x1, x2) 0 = 0 mulcA_out_gga(x1, x2, x3) = mulcA_out_gga(x1, x2, x3) U6_gga(x1, x2, x3, x4) = U6_gga(x1, x2, x4) U7_gga(x1, x2, x3, x4) = U7_gga(x1, x2, x4) addcB_in_gga(x1, x2, x3) = addcB_in_gga(x1, x2) addcB_out_gga(x1, x2, x3) = addcB_out_gga(x1, x2, x3) U8_gga(x1, x2, x3) = U8_gga(x1, x2, x3) addcB_in_ggg(x1, x2, x3) = addcB_in_ggg(x1, x2, x3) addcB_out_ggg(x1, x2, x3) = addcB_out_ggg(x1, x2, x3) U8_ggg(x1, x2, x3) = U8_ggg(x1, x2, x3) U9_ggg(x1, x2, x3, x4) = U9_ggg(x1, x2, x3, x4) U9_gga(x1, x2, x3, x4) = U9_gga(x1, x2, x4) MULA_IN_GGA(x1, x2, x3) = MULA_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: MULA_IN_GGA(X1, s(X2), X3) -> MULA_IN_GGA(X1, X2, X4) R is empty. The argument filtering Pi contains the following mapping: s(x1) = s(x1) MULA_IN_GGA(x1, x2, x3) = MULA_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: MULA_IN_GGA(X1, s(X2)) -> MULA_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: *MULA_IN_GGA(X1, s(X2)) -> MULA_IN_GGA(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (20) YES