/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 element_at(a,g,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 43 ms] (2) TRIPLES (3) TPisEmptyProof [EQUIVALENT, 0 ms] (4) YES ---------------------------------------- (0) Obligation: Clauses: element_at(X, .(X, X1), 1). element_at(X, .(X2, L), K) :- ','(>(K, 1), ','(is(K1, -(K, 1)), element_at(X, L, K1))). Query: element_at(a,g,g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 2, "program": { "directives": [], "clauses": [ [ "(element_at X (. X X1) (1))", null ], [ "(element_at X (. X2 L) K)", "(',' (> K (1)) (',' (is K1 (- K (1))) (element_at X L K1)))" ] ] }, "graph": { "nodes": { "15": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(element_at T1 (. T6 T7) (1))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": 1, "scope": 1, "term": "(element_at T1 T2 T3)" }], "kb": { "nonunifying": [[ "(element_at T1 T2 T3)", "(element_at X5 (. X5 X6) (1))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T2", "T3" ], "free": [ "X5", "X6" ], "exprvars": [] } }, "18": { "goal": [{ "clause": 1, "scope": 1, "term": "(element_at T1 (. T6 T7) (1))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": [], "exprvars": [] } }, "19": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> (1) (1)) (',' (is X15 (- (1) (1))) (element_at T14 T13 X15)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T13"], "free": ["X15"], "exprvars": [] } }, "1583": { "goal": [{ "clause": 1, "scope": 2, "term": "(element_at T23 T21 T24)" }], "kb": { "nonunifying": [[ "(element_at T1 (. T20 T21) T22)", "(element_at X5 (. X5 X6) (1))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T24", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T22", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T20", "T24", "T22", "T21" ], "free": [ "X5", "X6" ], "exprvars": [ "T24", "T22" ] } }, "1582": { "goal": [{ "clause": 0, "scope": 2, "term": "(element_at T23 T21 T24)" }], "kb": { "nonunifying": [[ "(element_at T1 (. T20 T21) T22)", "(element_at X5 (. X5 X6) (1))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T24", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T22", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T20", "T24", "T22", "T21" ], "free": [ "X5", "X6" ], "exprvars": [ "T24", "T22" ] } }, "1581": { "goal": [ { "clause": 0, "scope": 2, "term": "(element_at T23 T21 T24)" }, { "clause": 1, "scope": 2, "term": "(element_at T23 T21 T24)" } ], "kb": { "nonunifying": [[ "(element_at T1 (. T20 T21) T22)", "(element_at X5 (. X5 X6) (1))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T24", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T22", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T20", "T24", "T22", "T21" ], "free": [ "X5", "X6" ], "exprvars": [ "T24", "T22" ] } }, "1580": { "goal": [{ "clause": -1, "scope": -1, "term": "(element_at T23 T21 T24)" }], "kb": { "nonunifying": [[ "(element_at T1 (. T20 T21) T22)", "(element_at X5 (. X5 X6) (1))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T24", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T22", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T20", "T24", "T22", "T21" ], "free": [ "X5", "X6", "X24" ], "exprvars": [ "T24", "T22" ] } }, "type": "Nodes", "1547": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1546": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T22 (1)) (',' (is X24 (- T22 (1))) (element_at T23 T21 X24)))" }], "kb": { "nonunifying": [[ "(element_at T1 (. T20 T21) T22)", "(element_at X5 (. X5 X6) (1))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21", "T22" ], "free": [ "X5", "X6", "X24" ], "exprvars": [] } }, "1579": { "goal": [], "kb": { "nonunifying": [[ "(element_at T1 (. T20 T21) T22)", "(element_at X5 (. X5 X6) (1))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T22", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T20", "T22", "T21" ], "free": [ "X5", "X6", "X24" ], "exprvars": ["T22"] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(element_at T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T2", "T3" ], "free": [], "exprvars": [] } }, "1578": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X24 (- T22 (1))) (element_at T23 T21 X24))" }], "kb": { "nonunifying": [[ "(element_at T1 (. T20 T21) T22)", "(element_at X5 (. X5 X6) (1))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T22", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T20", "T22", "T21" ], "free": [ "X5", "X6", "X24" ], "exprvars": ["T22"] } }, "1589": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T24", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T22", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T24", "T22" ] } }, "1588": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T46 (1)) (',' (is X48 (- T46 (1))) (element_at T47 T45 X48)))" }], "kb": { "nonunifying": [[ "(element_at T1 (. T20 (. T44 T45)) T22)", "(element_at X5 (. X5 X6) (1))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T24", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T22", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T22", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T22", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T20", "T22", "T44", "T45", "T46" ], "free": [ "X5", "X6", "X48" ], "exprvars": [ "T24", "T46", "T22" ] } }, "1587": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T24", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T22", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T22", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T22", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T24", "T22" ] } }, "5": { "goal": [ { "clause": 0, "scope": 1, "term": "(element_at T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(element_at T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T2", "T3" ], "free": [], "exprvars": [] } }, "1586": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T24", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T22", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T24", "T22" ] } }, "1541": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": ">=" }] }, "ground": ["T13"], "free": ["X15"], "exprvars": [] } }, "1585": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T24", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T22", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T22", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T22", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T22", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [], "free": [], "exprvars": [ "T24", "T22" ] } }, "1548": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 5, "label": "CASE" }, { "from": 5, "to": 15, "label": "EVAL with clause\nelement_at(X5, .(X5, X6), 1).\nand substitutionT1 -> T6,\nX5 -> T6,\nX6 -> T7,\nT2 -> .(T6, T7),\nT3 -> 1" }, { "from": 5, "to": 17, "label": "EVAL-BACKTRACK" }, { "from": 15, "to": 18, "label": "SUCCESS" }, { "from": 17, "to": 1546, "label": "EVAL with clause\nelement_at(X20, .(X21, X22), X23) :- ','(>(X23, 1), ','(is(X24, -(X23, 1)), element_at(X20, X22, X24))).\nand substitutionT1 -> T23,\nX20 -> T23,\nX21 -> T20,\nX22 -> T21,\nT2 -> .(T20, T21),\nT3 -> T22,\nX23 -> T22,\nT19 -> T23" }, { "from": 17, "to": 1547, "label": "EVAL-BACKTRACK" }, { "from": 18, "to": 19, "label": "ONLY EVAL with clause\nelement_at(X11, .(X12, X13), X14) :- ','(>(X14, 1), ','(is(X15, -(X14, 1)), element_at(X11, X13, X15))).\nand substitutionT1 -> T14,\nX11 -> T14,\nT6 -> T12,\nX12 -> T12,\nT7 -> T13,\nX13 -> T13,\nX14 -> 1,\nT11 -> T14" }, { "from": 19, "to": 1541, "label": "ARITHCOMP FAIL" }, { "from": 1546, "to": 1548, "label": "IS ERROR" }, { "from": 1546, "to": 1578, "label": "ARITHCOMP SUCCESS" }, { "from": 1546, "to": 1579, "label": "ARITHCOMP FAIL" }, { "from": 1578, "to": 1580, "label": "\nX24 -> T24" }, { "from": 1580, "to": 1581, "label": "CASE" }, { "from": 1581, "to": 1582, "label": "PARALLEL" }, { "from": 1581, "to": 1583, "label": "PARALLEL" }, { "from": 1582, "to": 1585, "label": "EVAL with clause\nelement_at(X33, .(X33, X34), 1).\nand substitutionT23 -> T33,\nX33 -> T33,\nX34 -> T34,\nT21 -> .(T33, T34),\nT24 -> 1" }, { "from": 1582, "to": 1586, "label": "EVAL-BACKTRACK" }, { "from": 1583, "to": 1588, "label": "EVAL with clause\nelement_at(X44, .(X45, X46), X47) :- ','(>(X47, 1), ','(is(X48, -(X47, 1)), element_at(X44, X46, X48))).\nand substitutionT23 -> T47,\nX44 -> T47,\nX45 -> T44,\nX46 -> T45,\nT21 -> .(T44, T45),\nT24 -> T46,\nX47 -> T46,\nT43 -> T47" }, { "from": 1583, "to": 1589, "label": "EVAL-BACKTRACK" }, { "from": 1585, "to": 1587, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: Clauses: Afs: ---------------------------------------- (3) TPisEmptyProof (EQUIVALENT) There are no more dependency triples. Hence, the dependency triple problem trivially terminates. ---------------------------------------- (4) YES