/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 sumlist(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, 11 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) PiDP (7) PiDPToQDPProof [SOUND, 0 ms] (8) QDP (9) QDPSizeChangeProof [EQUIVALENT, 0 ms] (10) YES ---------------------------------------- (0) Obligation: Clauses: sumlist(.(I, Is), Sum) :- ','(sumlist(Is, IsSum), is(Sum, +(I, IsSum))). sumlist([], 0). Query: sumlist(g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(sumlist (. I Is) Sum)", "(',' (sumlist Is IsSum) (is Sum (+ I IsSum)))" ], [ "(sumlist ([]) (0))", null ] ] }, "graph": { "nodes": { "24": { "goal": [{ "clause": -1, "scope": -1, "term": "(sumlist T19 X29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": ["X29"], "exprvars": [] } }, "25": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X30 (+ T18 T22)) (is T9 (+ T6 X30)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T18", "T22" ], "free": ["X30"], "exprvars": [] } }, "48": { "goal": [{ "clause": 1, "scope": 2, "term": "(',' (sumlist T7 X7) (is T9 (+ T6 X7)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X7"], "exprvars": [] } }, "49": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(sumlist (. T6 T7) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": [], "exprvars": [] } }, "28": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "50": { "goal": [{ "clause": -1, "scope": -1, "term": "(is T9 (+ T6 (0)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "51": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "52": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "53": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T6", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "0" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }] }, "ground": [ "T6", "T27" ], "free": [], "exprvars": [ "T6", "T27" ] } }, "32": { "goal": [{ "clause": -1, "scope": -1, "term": "(is T9 (+ T6 T25))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "name": "T22", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }] }, "ground": [ "T25", "T6", "T18", "T22" ], "free": ["X30"], "exprvars": [ "T25", "T18", "T22" ] } }, "54": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": ["T6"] } }, "11": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (sumlist T7 X7) (is T9 (+ T6 X7)))" }, { "clause": 1, "scope": 1, "term": "(sumlist (. T6 T7) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X7"], "exprvars": [] } }, "55": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T6", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "0" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }] }, "ground": [], "free": [], "exprvars": [ "T6", "T27" ] } }, "12": { "goal": [{ "clause": 1, "scope": 1, "term": "(sumlist T1 T2)" }], "kb": { "nonunifying": [[ "(sumlist T1 T2)", "(sumlist (. X4 X5) X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [ "X4", "X5", "X6" ], "exprvars": [] } }, "56": { "goal": [{ "clause": 1, "scope": 1, "term": "(sumlist (. T6 T7) T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": [], "exprvars": [] } }, "13": { "goal": [ { "clause": 0, "scope": 2, "term": "(',' (sumlist T7 X7) (is T9 (+ T6 X7)))" }, { "clause": 1, "scope": 2, "term": "(',' (sumlist T7 X7) (is T9 (+ T6 X7)))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(sumlist (. T6 T7) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X7"], "exprvars": [] } }, "57": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "36": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "58": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "37": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "name": "T22", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T26", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T6", "type": "PlainIntegerVariable" }, { "name": "T25", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" } ] }, "ground": [ "T25", "T6", "T18", "T22", "T26" ], "free": ["X30"], "exprvars": [ "T25", "T18", "T6", "T22", "T26" ] } }, "59": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "38": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "name": "T22", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }] }, "ground": [ "T25", "T6", "T18", "T22" ], "free": ["X30"], "exprvars": [ "T25", "T18", "T6", "T22" ] } }, "39": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "name": "T22", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T26", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T6", "type": "PlainIntegerVariable" }, { "name": "T25", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" } ] }, "ground": [], "free": [], "exprvars": [ "T25", "T18", "T6", "T22", "T26" ] } }, "18": { "goal": [{ "clause": 0, "scope": 2, "term": "(',' (sumlist T7 X7) (is T9 (+ T6 X7)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X7"], "exprvars": [] } }, "19": { "goal": [ { "clause": 1, "scope": 2, "term": "(',' (sumlist T7 X7) (is T9 (+ T6 X7)))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(sumlist (. T6 T7) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X7"], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(sumlist T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "6": { "goal": [ { "clause": 0, "scope": 1, "term": "(sumlist T1 T2)" }, { "clause": 1, "scope": 1, "term": "(sumlist T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "60": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "20": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (sumlist T19 X29) (is X30 (+ T18 X29))) (is T9 (+ T6 X30)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T18", "T19" ], "free": [ "X30", "X29" ], "exprvars": [] } }, "21": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 6, "label": "CASE" }, { "from": 6, "to": 11, "label": "EVAL with clause\nsumlist(.(X4, X5), X6) :- ','(sumlist(X5, X7), is(X6, +(X4, X7))).\nand substitutionX4 -> T6,\nX5 -> T7,\nT1 -> .(T6, T7),\nT2 -> T9,\nX6 -> T9,\nT8 -> T9" }, { "from": 6, "to": 12, "label": "EVAL-BACKTRACK" }, { "from": 11, "to": 13, "label": "CASE" }, { "from": 12, "to": 58, "label": "EVAL with clause\nsumlist([], 0).\nand substitutionT1 -> [],\nT2 -> 0" }, { "from": 12, "to": 59, "label": "EVAL-BACKTRACK" }, { "from": 13, "to": 18, "label": "PARALLEL" }, { "from": 13, "to": 19, "label": "PARALLEL" }, { "from": 18, "to": 20, "label": "EVAL with clause\nsumlist(.(X26, X27), X28) :- ','(sumlist(X27, X29), is(X28, +(X26, X29))).\nand substitutionX26 -> T18,\nX27 -> T19,\nT7 -> .(T18, T19),\nX7 -> X30,\nX28 -> X30" }, { "from": 18, "to": 21, "label": "EVAL-BACKTRACK" }, { "from": 19, "to": 48, "label": "PARALLEL" }, { "from": 19, "to": 49, "label": "PARALLEL" }, { "from": 20, "to": 24, "label": "SPLIT 1" }, { "from": 20, "to": 25, "label": "SPLIT 2\nnew knowledge:\nT19 is ground\nT22 is ground\nreplacements:X29 -> T22" }, { "from": 24, "to": 1, "label": "INSTANCE with matching:\nT1 -> T19\nT2 -> X29" }, { "from": 25, "to": 28, "label": "IS ERROR" }, { "from": 25, "to": 32, "label": "\nX30 -> T25" }, { "from": 32, "to": 36, "label": "IS ERROR" }, { "from": 32, "to": 37, "label": "\nT9 -> T26" }, { "from": 32, "to": 38, "label": "IS FAIL" }, { "from": 37, "to": 39, "label": "SUCCESS" }, { "from": 48, "to": 50, "label": "EVAL with clause\nsumlist([], 0).\nand substitutionT7 -> [],\nX7 -> 0" }, { "from": 48, "to": 51, "label": "EVAL-BACKTRACK" }, { "from": 49, "to": 56, "label": "FAILURE" }, { "from": 50, "to": 52, "label": "IS ERROR" }, { "from": 50, "to": 53, "label": "\nT9 -> T27" }, { "from": 50, "to": 54, "label": "IS FAIL" }, { "from": 53, "to": 55, "label": "SUCCESS" }, { "from": 56, "to": 57, "label": "BACKTRACK\nfor clause: sumlist([], 0)because of non-unification" }, { "from": 58, "to": 60, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: sumlistA(.(X1, .(X2, X3)), X4) :- sumlistA(X3, X5). Clauses: sumlistcA(.(X1, .(X2, X3)), X4) :- sumlistcA(X3, X5). sumlistcA(.(X1, []), X2). sumlistcA([], 0). Afs: sumlistA(x1, x2) = sumlistA(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: sumlistA_in_2: (b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: SUMLISTA_IN_GA(.(X1, .(X2, X3)), X4) -> U1_GA(X1, X2, X3, X4, sumlistA_in_ga(X3, X5)) SUMLISTA_IN_GA(.(X1, .(X2, X3)), X4) -> SUMLISTA_IN_GA(X3, X5) R is empty. The argument filtering Pi contains the following mapping: sumlistA_in_ga(x1, x2) = sumlistA_in_ga(x1) .(x1, x2) = .(x1, x2) SUMLISTA_IN_GA(x1, x2) = SUMLISTA_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x2, x3, x5) 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: SUMLISTA_IN_GA(.(X1, .(X2, X3)), X4) -> U1_GA(X1, X2, X3, X4, sumlistA_in_ga(X3, X5)) SUMLISTA_IN_GA(.(X1, .(X2, X3)), X4) -> SUMLISTA_IN_GA(X3, X5) R is empty. The argument filtering Pi contains the following mapping: sumlistA_in_ga(x1, x2) = sumlistA_in_ga(x1) .(x1, x2) = .(x1, x2) SUMLISTA_IN_GA(x1, x2) = SUMLISTA_IN_GA(x1) U1_GA(x1, x2, x3, x4, x5) = U1_GA(x1, x2, x3, x5) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node. ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: SUMLISTA_IN_GA(.(X1, .(X2, X3)), X4) -> SUMLISTA_IN_GA(X3, X5) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) SUMLISTA_IN_GA(x1, x2) = SUMLISTA_IN_GA(x1) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: SUMLISTA_IN_GA(.(X1, .(X2, X3))) -> SUMLISTA_IN_GA(X3) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (9) 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: *SUMLISTA_IN_GA(.(X1, .(X2, X3))) -> SUMLISTA_IN_GA(X3) The graph contains the following edges 1 > 1 ---------------------------------------- (10) YES