/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 find_length(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) PiDP (7) PiDPToQDPProof [SOUND, 0 ms] (8) QDP (9) QDPSizeChangeProof [EQUIVALENT, 0 ms] (10) YES ---------------------------------------- (0) Obligation: Clauses: find_length(.(X, Xs), N) :- ','(find_length(Xs, N1), is(N, +(N1, 1))). find_length([], 0). Query: find_length(g,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 3, "program": { "directives": [], "clauses": [ [ "(find_length (. X Xs) N)", "(',' (find_length Xs N1) (is N (+ N1 (1))))" ], [ "(find_length ([]) (0))", null ] ] }, "graph": { "nodes": { "46": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T26", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T25", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" } ] }, "ground": [], "free": [], "exprvars": [ "T25", "T22", "T26" ] } }, "47": { "goal": [{ "clause": 1, "scope": 2, "term": "(',' (find_length T7 X7) (is T9 (+ X7 (1))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": ["X7"], "exprvars": [] } }, "26": { "goal": [{ "clause": -1, "scope": -1, "term": "(find_length T19 X29)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": ["X29"], "exprvars": [] } }, "48": { "goal": [ { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(find_length (. T6 T7) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": [], "exprvars": [] } }, "27": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X30 (+ T22 (1))) (is T9 (+ X30 (1))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T22"], "free": ["X30"], "exprvars": [] } }, "49": { "goal": [{ "clause": -1, "scope": -1, "term": "(is T9 (+ (0) (1)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "50": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "51": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }] }, "ground": ["T27"], "free": [], "exprvars": ["T27"] } }, "30": { "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": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T27", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "0" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }] }, "ground": [], "free": [], "exprvars": ["T27"] } }, "10": { "goal": [{ "clause": 1, "scope": 1, "term": "(find_length T1 T2)" }], "kb": { "nonunifying": [[ "(find_length T1 T2)", "(find_length (. X4 X5) X6)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [ "X4", "X5", "X6" ], "exprvars": [] } }, "32": { "goal": [{ "clause": -1, "scope": -1, "term": "(is T9 (+ T25 (1)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }] }, "ground": [ "T25", "T22" ], "free": ["X30"], "exprvars": [ "T25", "T22" ] } }, "54": { "goal": [{ "clause": 1, "scope": 1, "term": "(find_length (. T6 T7) T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": [], "exprvars": [] } }, "55": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "12": { "goal": [ { "clause": 0, "scope": 2, "term": "(',' (find_length T7 X7) (is T9 (+ X7 (1))))" }, { "clause": 1, "scope": 2, "term": "(',' (find_length T7 X7) (is T9 (+ X7 (1))))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(find_length (. T6 T7) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X7"], "exprvars": [] } }, "56": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "35": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T26", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T25", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" } ] }, "ground": [ "T25", "T22", "T26" ], "free": ["X30"], "exprvars": [ "T25", "T22", "T26" ] } }, "57": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "14": { "goal": [{ "clause": 0, "scope": 2, "term": "(',' (find_length T7 X7) (is T9 (+ X7 (1))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": ["X7"], "exprvars": [] } }, "36": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }] }, "ground": [ "T25", "T22" ], "free": ["X30"], "exprvars": [ "T25", "T22" ] } }, "58": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "15": { "goal": [ { "clause": 1, "scope": 2, "term": "(',' (find_length T7 X7) (is T9 (+ X7 (1))))" }, { "clause": -1, "scope": 2, "term": null }, { "clause": 1, "scope": 1, "term": "(find_length (. T6 T7) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X7"], "exprvars": [] } }, "16": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (',' (find_length T19 X29) (is X30 (+ X29 (1)))) (is T9 (+ X30 (1))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T19"], "free": [ "X30", "X29" ], "exprvars": [] } }, "17": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(find_length T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "5": { "goal": [ { "clause": 0, "scope": 1, "term": "(find_length T1 T2)" }, { "clause": 1, "scope": 1, "term": "(find_length T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "9": { "goal": [ { "clause": -1, "scope": -1, "term": "(',' (find_length T7 X7) (is T9 (+ X7 (1))))" }, { "clause": 1, "scope": 1, "term": "(find_length (. T6 T7) T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": ["X7"], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 5, "label": "CASE" }, { "from": 5, "to": 9, "label": "EVAL with clause\nfind_length(.(X4, X5), X6) :- ','(find_length(X5, X7), is(X6, +(X7, 1))).\nand substitutionX4 -> T6,\nX5 -> T7,\nT1 -> .(T6, T7),\nT2 -> T9,\nX6 -> T9,\nT8 -> T9" }, { "from": 5, "to": 10, "label": "EVAL-BACKTRACK" }, { "from": 9, "to": 12, "label": "CASE" }, { "from": 10, "to": 56, "label": "EVAL with clause\nfind_length([], 0).\nand substitutionT1 -> [],\nT2 -> 0" }, { "from": 10, "to": 57, "label": "EVAL-BACKTRACK" }, { "from": 12, "to": 14, "label": "PARALLEL" }, { "from": 12, "to": 15, "label": "PARALLEL" }, { "from": 14, "to": 16, "label": "EVAL with clause\nfind_length(.(X26, X27), X28) :- ','(find_length(X27, X29), is(X28, +(X29, 1))).\nand substitutionX26 -> T18,\nX27 -> T19,\nT7 -> .(T18, T19),\nX7 -> X30,\nX28 -> X30" }, { "from": 14, "to": 17, "label": "EVAL-BACKTRACK" }, { "from": 15, "to": 47, "label": "PARALLEL" }, { "from": 15, "to": 48, "label": "PARALLEL" }, { "from": 16, "to": 26, "label": "SPLIT 1" }, { "from": 16, "to": 27, "label": "SPLIT 2\nnew knowledge:\nT19 is ground\nT22 is ground\nreplacements:X29 -> T22" }, { "from": 26, "to": 3, "label": "INSTANCE with matching:\nT1 -> T19\nT2 -> X29" }, { "from": 27, "to": 30, "label": "IS ERROR" }, { "from": 27, "to": 32, "label": "\nX30 -> T25" }, { "from": 32, "to": 35, "label": "\nT9 -> T26" }, { "from": 32, "to": 36, "label": "IS FAIL" }, { "from": 35, "to": 46, "label": "SUCCESS" }, { "from": 47, "to": 49, "label": "EVAL with clause\nfind_length([], 0).\nand substitutionT7 -> [],\nX7 -> 0" }, { "from": 47, "to": 50, "label": "EVAL-BACKTRACK" }, { "from": 48, "to": 54, "label": "FAILURE" }, { "from": 49, "to": 51, "label": "\nT9 -> T27" }, { "from": 49, "to": 52, "label": "IS FAIL" }, { "from": 51, "to": 53, "label": "SUCCESS" }, { "from": 54, "to": 55, "label": "BACKTRACK\nfor clause: find_length([], 0)because of non-unification" }, { "from": 56, "to": 58, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: find_lengthA(.(X1, .(X2, X3)), X4) :- find_lengthA(X3, X5). Clauses: find_lengthcA(.(X1, .(X2, X3)), X4) :- find_lengthcA(X3, X5). find_lengthcA(.(X1, []), X2). find_lengthcA([], 0). Afs: find_lengthA(x1, x2) = find_lengthA(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: find_lengthA_in_2: (b,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: FIND_LENGTHA_IN_GA(.(X1, .(X2, X3)), X4) -> U1_GA(X1, X2, X3, X4, find_lengthA_in_ga(X3, X5)) FIND_LENGTHA_IN_GA(.(X1, .(X2, X3)), X4) -> FIND_LENGTHA_IN_GA(X3, X5) R is empty. The argument filtering Pi contains the following mapping: find_lengthA_in_ga(x1, x2) = find_lengthA_in_ga(x1) .(x1, x2) = .(x1, x2) FIND_LENGTHA_IN_GA(x1, x2) = FIND_LENGTHA_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: FIND_LENGTHA_IN_GA(.(X1, .(X2, X3)), X4) -> U1_GA(X1, X2, X3, X4, find_lengthA_in_ga(X3, X5)) FIND_LENGTHA_IN_GA(.(X1, .(X2, X3)), X4) -> FIND_LENGTHA_IN_GA(X3, X5) R is empty. The argument filtering Pi contains the following mapping: find_lengthA_in_ga(x1, x2) = find_lengthA_in_ga(x1) .(x1, x2) = .(x1, x2) FIND_LENGTHA_IN_GA(x1, x2) = FIND_LENGTHA_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: FIND_LENGTHA_IN_GA(.(X1, .(X2, X3)), X4) -> FIND_LENGTHA_IN_GA(X3, X5) R is empty. The argument filtering Pi contains the following mapping: .(x1, x2) = .(x1, x2) FIND_LENGTHA_IN_GA(x1, x2) = FIND_LENGTHA_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: FIND_LENGTHA_IN_GA(.(X1, .(X2, X3))) -> FIND_LENGTHA_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: *FIND_LENGTHA_IN_GA(.(X1, .(X2, X3))) -> FIND_LENGTHA_IN_GA(X3) The graph contains the following edges 1 > 1 ---------------------------------------- (10) YES