/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 range(g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 14 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 17 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 8 ms] (10) IRSwT (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IRSwT (13) TempFilterProof [SOUND, 35 ms] (14) IntTRS (15) PolynomialOrderProcessor [EQUIVALENT, 12 ms] (16) YES ---------------------------------------- (0) Obligation: Clauses: range(I, I, .(I, [])). range(I, K, .(I, L)) :- ','(<(I, K), ','(is(I1, +(I, 1)), range(I1, K, L))). Query: range(g,g,a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 2, "program": { "directives": [], "clauses": [ [ "(range I I (. I ([])))", null ], [ "(range I K (. I L))", "(',' (< I K) (',' (is I1 (+ I (1))) (range I1 K L)))" ] ] }, "graph": { "nodes": { "11": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "13": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "26": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (< T15 T16) (',' (is X16 (+ T15 (1))) (range X16 T16 T18)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T15", "T16" ], "free": ["X16"], "exprvars": [] } }, "16": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "27": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "28": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "274": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X16 (+ T15 (1))) (range X16 T16 T18))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T15", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T16", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T16", "T15" ], "free": ["X16"], "exprvars": [ "T16", "T15" ] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(range T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(range T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(range T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "279": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T15", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T16", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T16", "T15" ], "free": ["X16"], "exprvars": [ "T16", "T15" ] } }, "844": { "goal": [{ "clause": -1, "scope": -1, "term": "(range T19 T16 T18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T15", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T15", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T16", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T19", "T16", "T15" ], "free": ["X16"], "exprvars": [ "T19", "T16", "T15" ] } }, "9": { "goal": [{ "clause": 0, "scope": 1, "term": "(range T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "10": { "goal": [{ "clause": 1, "scope": 1, "term": "(range T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 4, "label": "CASE" }, { "from": 4, "to": 9, "label": "PARALLEL" }, { "from": 4, "to": 10, "label": "PARALLEL" }, { "from": 9, "to": 11, "label": "EVAL with clause\nrange(X5, X5, .(X5, [])).\nand substitutionT1 -> T8,\nX5 -> T8,\nT2 -> T8,\nT3 -> .(T8, [])" }, { "from": 9, "to": 13, "label": "EVAL-BACKTRACK" }, { "from": 10, "to": 26, "label": "EVAL with clause\nrange(X13, X14, .(X13, X15)) :- ','(<(X13, X14), ','(is(X16, +(X13, 1)), range(X16, X14, X15))).\nand substitutionT1 -> T15,\nX13 -> T15,\nT2 -> T16,\nX14 -> T16,\nX15 -> T18,\nT3 -> .(T15, T18),\nT17 -> T18" }, { "from": 10, "to": 27, "label": "EVAL-BACKTRACK" }, { "from": 11, "to": 16, "label": "SUCCESS" }, { "from": 26, "to": 28, "label": "IS ERROR" }, { "from": 26, "to": 274, "label": "ARITHCOMP SUCCESS" }, { "from": 26, "to": 279, "label": "ARITHCOMP FAIL" }, { "from": 274, "to": 844, "label": "\nX16 -> T19" }, { "from": 844, "to": 2, "label": "INSTANCE with matching:\nT1 -> T19\nT2 -> T16\nT3 -> T18" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f4_in(T1, T2) -> f10_in(T1, T2) :|: TRUE f10_out(x, x1) -> f4_out(x, x1) :|: TRUE f4_in(x2, x3) -> f9_in(x2, x3) :|: TRUE f9_out(x4, x5) -> f4_out(x4, x5) :|: TRUE f274_in(T15, T16) -> f844_in(T19, T16, T15) :|: T19 = T15 + 1 f844_out(x6, x7, x8) -> f274_out(x8, x7) :|: TRUE f844_in(x9, x10, x11) -> f2_in(x9, x10) :|: TRUE f2_out(x12, x13) -> f844_out(x12, x13, x14) :|: TRUE f26_in(x15, x16) -> f28_in :|: TRUE f279_out(x17, x18) -> f26_out(x18, x17) :|: x18 >= x17 f26_in(x19, x20) -> f274_in(x19, x20) :|: x19 < x20 f26_in(x21, x22) -> f279_in(x22, x21) :|: x21 >= x22 f28_out -> f26_out(x23, x24) :|: TRUE f274_out(x25, x26) -> f26_out(x25, x26) :|: x25 < x26 f2_in(x27, x28) -> f4_in(x27, x28) :|: TRUE f4_out(x29, x30) -> f2_out(x29, x30) :|: TRUE f26_out(x31, x32) -> f10_out(x31, x32) :|: TRUE f27_out -> f10_out(x33, x34) :|: TRUE f10_in(x35, x36) -> f27_in :|: TRUE f10_in(x37, x38) -> f26_in(x37, x38) :|: TRUE Start term: f2_in(T1, T2) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f4_in(T1, T2) -> f10_in(T1, T2) :|: TRUE f274_in(T15, T16) -> f844_in(T19, T16, T15) :|: T19 = T15 + 1 f844_in(x9, x10, x11) -> f2_in(x9, x10) :|: TRUE f26_in(x19, x20) -> f274_in(x19, x20) :|: x19 < x20 f2_in(x27, x28) -> f4_in(x27, x28) :|: TRUE f10_in(x37, x38) -> f26_in(x37, x38) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f4_in(T1, T2) -> f10_in(T1, T2) :|: TRUE f274_in(T15, T16) -> f844_in(T19, T16, T15) :|: T19 = T15 + 1 f844_in(x9, x10, x11) -> f2_in(x9, x10) :|: TRUE f26_in(x19, x20) -> f274_in(x19, x20) :|: x19 < x20 f2_in(x27, x28) -> f4_in(x27, x28) :|: TRUE f10_in(x37, x38) -> f26_in(x37, x38) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f26_in(x19:0, x20:0) -> f26_in(x19:0 + 1, x20:0) :|: x20:0 > x19:0 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f26_in(x19:0, x20:0) -> f26_in(arith, x20:0) :|: x20:0 > x19:0 && arith = x19:0 + 1 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f26_in(x19:0, x20:0) -> f26_in(arith, x20:0) :|: x20:0 > x19:0 && arith = x19:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f26_in(x19:0, x20:0) -> f26_in(arith, x20:0) :|: x20:0 > x19:0 && arith = x19:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f26_in(x19:0:0, x20:0:0) -> f26_in(x19:0:0 + 1, x20:0:0) :|: x20:0:0 > x19:0:0 ---------------------------------------- (13) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f26_in(INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (14) Obligation: Rules: f26_in(x19:0:0, x20:0:0) -> f26_in(c, x20:0:0) :|: c = x19:0:0 + 1 && x20:0:0 > x19:0:0 ---------------------------------------- (15) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f26_in(x, x1)] = -x + x1 The following rules are decreasing: f26_in(x19:0:0, x20:0:0) -> f26_in(c, x20:0:0) :|: c = x19:0:0 + 1 && x20:0:0 > x19:0:0 The following rules are bounded: f26_in(x19:0:0, x20:0:0) -> f26_in(c, x20:0:0) :|: c = x19:0:0 + 1 && x20:0:0 > x19:0:0 ---------------------------------------- (16) YES