/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 evenSpaced(g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 51 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) PiDP (7) PiDPToQDPProof [EQUIVALENT, 0 ms] (8) QDP (9) QDPSizeChangeProof [EQUIVALENT, 1 ms] (10) YES ---------------------------------------- (0) Obligation: Clauses: evenSpaced(.(X1, .(X2, []))). evenSpaced(.(X, .(Y, .(Z, Xs)))) :- ','(is(Diff, -(Y, X)), ','(=:=(Diff, -(Z, Y)), evenSpaced(.(Y, .(Z, Xs))))). Query: evenSpaced(g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(evenSpaced (. X1 (. X2 ([]))))", null ], [ "(evenSpaced (. X (. Y (. Z Xs))))", "(',' (is Diff (- Y X)) (',' (=:= Diff (- Z Y)) (evenSpaced (. Y (. Z Xs)))))" ] ] }, "graph": { "nodes": { "type": "Nodes", "1519": { "goal": [{ "clause": 0, "scope": 2, "term": "(evenSpaced (. T13 (. T14 T15)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [ "T14", "T13", "T15" ], "free": [], "exprvars": [ "T14", "T13", "T12", "T16" ] } }, "1518": { "goal": [ { "clause": 0, "scope": 2, "term": "(evenSpaced (. T13 (. T14 T15)))" }, { "clause": 1, "scope": 2, "term": "(evenSpaced (. T13 (. T14 T15)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [ "T14", "T13", "T15" ], "free": [], "exprvars": [ "T14", "T13", "T12", "T16" ] } }, "30": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (=:= T16 (- T14 T13)) (evenSpaced (. T13 (. T14 T15))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }] }, "ground": [ "T14", "T13", "T12", "T16", "T15" ], "free": ["X19"], "exprvars": [ "T13", "T12", "T16" ] } }, "1517": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "!=" } ] }, "ground": [ "T14", "T13", "T12", "T16", "T15" ], "free": ["X19"], "exprvars": [ "T14", "T13", "T12", "T16" ] } }, "1516": { "goal": [{ "clause": -1, "scope": -1, "term": "(evenSpaced (. T13 (. T14 T15)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [ "T14", "T13", "T12", "T16", "T15" ], "free": ["X19"], "exprvars": [ "T14", "T13", "T12", "T16" ] } }, "32": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "13": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X19 (- T13 T12)) (',' (=:= X19 (- T14 T13)) (evenSpaced (. T13 (. T14 T15)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13", "T14", "T15" ], "free": ["X19"], "exprvars": [] } }, "16": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "17": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1525": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [], "free": [], "exprvars": [ "T14", "T13", "T12", "T16" ] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(evenSpaced T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "1524": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X43 (- T36 T35)) (',' (=:= X43 (- T37 T36)) (evenSpaced (. T36 (. T37 T38)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T35", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T36", "type": "PlainIntegerVariable" }, { "name": "T35", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [ "T35", "T36", "T37", "T38" ], "free": ["X43"], "exprvars": [ "T14", "T36", "T13", "T35", "T12", "T16" ] } }, "1523": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T25", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T26", "type": "PlainIntegerVariable" }, { "name": "T25", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [], "free": [], "exprvars": [ "T14", "T25", "T13", "T12", "T16", "T26" ] } }, "1522": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [], "free": [], "exprvars": [ "T14", "T13", "T12", "T16" ] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(evenSpaced T1)" }, { "clause": 1, "scope": 1, "term": "(evenSpaced T1)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "1521": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T25", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T26", "type": "PlainIntegerVariable" }, { "name": "T25", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [], "free": [], "exprvars": [ "T14", "T25", "T13", "T12", "T16", "T26" ] } }, "5": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 1, "scope": 1, "term": "(evenSpaced (. T4 (. T5 ([]))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T5" ], "free": [], "exprvars": [] } }, "1520": { "goal": [{ "clause": 1, "scope": 2, "term": "(evenSpaced (. T13 (. T14 T15)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [ "T14", "T13", "T15" ], "free": [], "exprvars": [ "T14", "T13", "T12", "T16" ] } }, "6": { "goal": [{ "clause": 1, "scope": 1, "term": "(evenSpaced T1)" }], "kb": { "nonunifying": [[ "(evenSpaced T1)", "(evenSpaced (. X5 (. X6 ([]))))" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [ "X5", "X6" ], "exprvars": [] } }, "7": { "goal": [{ "clause": 1, "scope": 1, "term": "(evenSpaced (. T4 (. T5 ([]))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T4", "T5" ], "free": [], "exprvars": [] } }, "9": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1529": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T35", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T36", "type": "PlainIntegerVariable" }, { "name": "T35", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T39", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T36", "type": "PlainIntegerVariable" }, { "name": "T35", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T39", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T37", "type": "PlainIntegerVariable" }, { "name": "T36", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "!=" } ] }, "ground": [ "T36", "T35", "T39", "T38", "T37" ], "free": ["X43"], "exprvars": [ "T14", "T36", "T13", "T35", "T12", "T39", "T16", "T37" ] } }, "1528": { "goal": [{ "clause": -1, "scope": -1, "term": "(evenSpaced (. T36 (. T37 T38)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T35", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T36", "type": "PlainIntegerVariable" }, { "name": "T35", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T39", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T36", "type": "PlainIntegerVariable" }, { "name": "T35", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T39", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T37", "type": "PlainIntegerVariable" }, { "name": "T36", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [ "T36", "T35", "T39", "T38", "T37" ], "free": ["X43"], "exprvars": [ "T14", "T36", "T13", "T35", "T12", "T39", "T16", "T37" ] } }, "1527": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1526": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (=:= T39 (- T37 T36)) (evenSpaced (. T36 (. T37 T38))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T35", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T12", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "arguments": [ { "name": "T36", "type": "PlainIntegerVariable" }, { "name": "T35", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T14", "type": "PlainIntegerVariable" }, { "name": "T13", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T39", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T36", "type": "PlainIntegerVariable" }, { "name": "T35", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" } ] }, "ground": [ "T36", "T35", "T39", "T38", "T37" ], "free": ["X43"], "exprvars": [ "T14", "T36", "T13", "T35", "T12", "T39", "T16" ] } } }, "edges": [ { "from": 1, "to": 4, "label": "CASE" }, { "from": 4, "to": 5, "label": "EVAL with clause\nevenSpaced(.(X5, .(X6, []))).\nand substitutionX5 -> T4,\nX6 -> T5,\nT1 -> .(T4, .(T5, []))" }, { "from": 4, "to": 6, "label": "EVAL-BACKTRACK" }, { "from": 5, "to": 7, "label": "SUCCESS" }, { "from": 6, "to": 13, "label": "EVAL with clause\nevenSpaced(.(X15, .(X16, .(X17, X18)))) :- ','(is(X19, -(X16, X15)), ','(=:=(X19, -(X17, X16)), evenSpaced(.(X16, .(X17, X18))))).\nand substitutionX15 -> T12,\nX16 -> T13,\nX17 -> T14,\nX18 -> T15,\nT1 -> .(T12, .(T13, .(T14, T15)))" }, { "from": 6, "to": 16, "label": "EVAL-BACKTRACK" }, { "from": 7, "to": 9, "label": "BACKTRACK\nfor clause: evenSpaced(.(X, .(Y, .(Z, Xs)))) :- ','(is(Diff, -(Y, X)), ','(=:=(Diff, -(Z, Y)), evenSpaced(.(Y, .(Z, Xs)))))because of non-unification" }, { "from": 13, "to": 17, "label": "IS ERROR" }, { "from": 13, "to": 30, "label": "\nX19 -> T16" }, { "from": 30, "to": 32, "label": "IS ERROR" }, { "from": 30, "to": 1516, "label": "ARITHCOMP SUCCESS" }, { "from": 30, "to": 1517, "label": "ARITHCOMP FAIL" }, { "from": 1516, "to": 1518, "label": "CASE" }, { "from": 1518, "to": 1519, "label": "PARALLEL" }, { "from": 1518, "to": 1520, "label": "PARALLEL" }, { "from": 1519, "to": 1521, "label": "EVAL with clause\nevenSpaced(.(X28, .(X29, []))).\nand substitutionT13 -> T25,\nX28 -> T25,\nT14 -> T26,\nX29 -> T26,\nT15 -> []" }, { "from": 1519, "to": 1522, "label": "EVAL-BACKTRACK" }, { "from": 1520, "to": 1524, "label": "EVAL with clause\nevenSpaced(.(X39, .(X40, .(X41, X42)))) :- ','(is(X43, -(X40, X39)), ','(=:=(X43, -(X41, X40)), evenSpaced(.(X40, .(X41, X42))))).\nand substitutionT13 -> T35,\nX39 -> T35,\nT14 -> T36,\nX40 -> T36,\nX41 -> T37,\nX42 -> T38,\nT15 -> .(T37, T38)" }, { "from": 1520, "to": 1525, "label": "EVAL-BACKTRACK" }, { "from": 1521, "to": 1523, "label": "SUCCESS" }, { "from": 1524, "to": 1526, "label": "\nX43 -> T39" }, { "from": 1526, "to": 1527, "label": "IS ERROR" }, { "from": 1526, "to": 1528, "label": "ARITHCOMP SUCCESS" }, { "from": 1526, "to": 1529, "label": "ARITHCOMP FAIL" }, { "from": 1528, "to": 1, "label": "INSTANCE with matching:\nT1 -> .(T36, .(T37, T38))" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: evenSpacedA(.(X1, .(X2, .(X3, .(X4, X5))))) :- evenSpacedA(.(X3, .(X4, X5))). Clauses: evenSpacedcA(.(X1, .(X2, []))). evenSpacedcA(.(X1, .(X2, .(X3, [])))). evenSpacedcA(.(X1, .(X2, .(X3, .(X4, X5))))) :- evenSpacedcA(.(X3, .(X4, X5))). Afs: evenSpacedA(x1) = evenSpacedA(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: evenSpacedA_in_1: (b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: EVENSPACEDA_IN_G(.(X1, .(X2, .(X3, .(X4, X5))))) -> U1_G(X1, X2, X3, X4, X5, evenSpacedA_in_g(.(X3, .(X4, X5)))) EVENSPACEDA_IN_G(.(X1, .(X2, .(X3, .(X4, X5))))) -> EVENSPACEDA_IN_G(.(X3, .(X4, X5))) R is empty. Pi is empty. 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: EVENSPACEDA_IN_G(.(X1, .(X2, .(X3, .(X4, X5))))) -> U1_G(X1, X2, X3, X4, X5, evenSpacedA_in_g(.(X3, .(X4, X5)))) EVENSPACEDA_IN_G(.(X1, .(X2, .(X3, .(X4, X5))))) -> EVENSPACEDA_IN_G(.(X3, .(X4, X5))) R is empty. Pi is empty. 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: EVENSPACEDA_IN_G(.(X1, .(X2, .(X3, .(X4, X5))))) -> EVENSPACEDA_IN_G(.(X3, .(X4, X5))) R is empty. Pi is empty. We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) PiDPToQDPProof (EQUIVALENT) 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: EVENSPACEDA_IN_G(.(X1, .(X2, .(X3, .(X4, X5))))) -> EVENSPACEDA_IN_G(.(X3, .(X4, X5))) 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: *EVENSPACEDA_IN_G(.(X1, .(X2, .(X3, .(X4, X5))))) -> EVENSPACEDA_IN_G(.(X3, .(X4, X5))) The graph contains the following edges 1 > 1 ---------------------------------------- (10) YES