/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.pl /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/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, 31 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 0 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 29 ms] (10) IRSwT (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IRSwT (13) TempFilterProof [SOUND, 39 ms] (14) IntTRS (15) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (16) YES ---------------------------------------- (0) Obligation: Clauses: range(M, N, .(M, Ns)) :- ','(<(M, N), ','(is(M1, +(M, 1)), range(M1, N, Ns))). range(N, N, .(N, [])). Query: range(g,g,a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 1, "program": { "directives": [], "clauses": [ [ "(range M N (. M Ns))", "(',' (< M N) (',' (is M1 (+ M (1))) (range M1 N Ns)))" ], [ "(range N N (. N ([])))", null ] ] }, "graph": { "nodes": { "12": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (< T16 T17) (',' (is X18 (+ T16 (1))) (range X18 T17 T19)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17" ], "free": ["X18"], "exprvars": [] } }, "13": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "16": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1484": { "goal": [{ "clause": -1, "scope": -1, "term": "(range T20 T17 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T20", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T16", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T17", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T20", "T17", "T16" ], "free": ["X18"], "exprvars": [ "T20", "T17", "T16" ] } }, "1483": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T17", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T17", "T16" ], "free": ["X18"], "exprvars": [ "T17", "T16" ] } }, "1482": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X18 (+ T16 (1))) (range X18 T17 T19))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T16", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T17", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T17", "T16" ], "free": ["X18"], "exprvars": [ "T17", "T16" ] } }, "type": "Nodes", "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(range T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "1511": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "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": [] } }, "1510": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(range T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "7": { "goal": [{ "clause": 1, "scope": 1, "term": "(range T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "1509": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 4, "label": "CASE" }, { "from": 4, "to": 6, "label": "PARALLEL" }, { "from": 4, "to": 7, "label": "PARALLEL" }, { "from": 6, "to": 12, "label": "EVAL with clause\nrange(X15, X16, .(X15, X17)) :- ','(<(X15, X16), ','(is(X18, +(X15, 1)), range(X18, X16, X17))).\nand substitutionT1 -> T16,\nX15 -> T16,\nT2 -> T17,\nX16 -> T17,\nX17 -> T19,\nT3 -> .(T16, T19),\nT18 -> T19" }, { "from": 6, "to": 13, "label": "EVAL-BACKTRACK" }, { "from": 7, "to": 1509, "label": "EVAL with clause\nrange(X25, X25, .(X25, [])).\nand substitutionT1 -> T26,\nX25 -> T26,\nT2 -> T26,\nT3 -> .(T26, [])" }, { "from": 7, "to": 1510, "label": "EVAL-BACKTRACK" }, { "from": 12, "to": 16, "label": "IS ERROR" }, { "from": 12, "to": 1482, "label": "ARITHCOMP SUCCESS" }, { "from": 12, "to": 1483, "label": "ARITHCOMP FAIL" }, { "from": 1482, "to": 1484, "label": "\nX18 -> T20" }, { "from": 1484, "to": 1, "label": "INSTANCE with matching:\nT1 -> T20\nT2 -> T17\nT3 -> T19" }, { "from": 1509, "to": 1511, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f12_in(T16, T17) -> f1482_in(T16, T17) :|: T16 < T17 f16_out -> f12_out(x, x1) :|: TRUE f12_in(x2, x3) -> f1483_in(x3, x2) :|: x2 >= x3 f1482_out(x4, x5) -> f12_out(x4, x5) :|: x4 < x5 f12_in(x6, x7) -> f16_in :|: TRUE f1483_out(x8, x9) -> f12_out(x9, x8) :|: x9 >= x8 f1_in(T1, T2) -> f4_in(T1, T2) :|: TRUE f4_out(x10, x11) -> f1_out(x10, x11) :|: TRUE f13_out -> f6_out(x12, x13) :|: TRUE f12_out(x14, x15) -> f6_out(x14, x15) :|: TRUE f6_in(x16, x17) -> f12_in(x16, x17) :|: TRUE f6_in(x18, x19) -> f13_in :|: TRUE f1484_out(x20, x21, x22) -> f1482_out(x22, x21) :|: TRUE f1482_in(x23, x24) -> f1484_in(x25, x24, x23) :|: x25 = x23 + 1 f7_out(x26, x27) -> f4_out(x26, x27) :|: TRUE f4_in(x28, x29) -> f7_in(x28, x29) :|: TRUE f4_in(x30, x31) -> f6_in(x30, x31) :|: TRUE f6_out(x32, x33) -> f4_out(x32, x33) :|: TRUE f1_out(x34, x35) -> f1484_out(x34, x35, x36) :|: TRUE f1484_in(x37, x38, x39) -> f1_in(x37, x38) :|: TRUE Start term: f1_in(T1, T2) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f12_in(T16, T17) -> f1482_in(T16, T17) :|: T16 < T17 f1_in(T1, T2) -> f4_in(T1, T2) :|: TRUE f6_in(x16, x17) -> f12_in(x16, x17) :|: TRUE f1482_in(x23, x24) -> f1484_in(x25, x24, x23) :|: x25 = x23 + 1 f4_in(x30, x31) -> f6_in(x30, x31) :|: TRUE f1484_in(x37, x38, x39) -> f1_in(x37, x38) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f12_in(T16, T17) -> f1482_in(T16, T17) :|: T16 < T17 f1_in(T1, T2) -> f4_in(T1, T2) :|: TRUE f6_in(x16, x17) -> f12_in(x16, x17) :|: TRUE f1482_in(x23, x24) -> f1484_in(x25, x24, x23) :|: x25 = x23 + 1 f4_in(x30, x31) -> f6_in(x30, x31) :|: TRUE f1484_in(x37, x38, x39) -> f1_in(x37, x38) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f1_in(T1:0, T2:0) -> f1_in(T1:0 + 1, T2:0) :|: T2:0 > T1:0 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f1_in(T1:0, T2:0) -> f1_in(arith, T2:0) :|: T2:0 > T1:0 && arith = T1:0 + 1 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1_in(T1:0, T2:0) -> f1_in(arith, T2:0) :|: T2:0 > T1:0 && arith = T1:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f1_in(T1:0, T2:0) -> f1_in(arith, T2:0) :|: T2:0 > T1:0 && arith = T1:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f1_in(T1:0:0, T2:0:0) -> f1_in(T1:0:0 + 1, T2:0:0) :|: T2:0:0 > T1:0:0 ---------------------------------------- (13) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1_in(INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (14) Obligation: Rules: f1_in(T1:0:0, T2:0:0) -> f1_in(c, T2:0:0) :|: c = T1:0:0 + 1 && T2:0:0 > T1:0:0 ---------------------------------------- (15) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f1_in(x, x1)] = -x + x1 The following rules are decreasing: f1_in(T1:0:0, T2:0:0) -> f1_in(c, T2:0:0) :|: c = T1:0:0 + 1 && T2:0:0 > T1:0:0 The following rules are bounded: f1_in(T1:0:0, T2:0:0) -> f1_in(c, T2:0:0) :|: c = T1:0:0 + 1 && T2:0:0 > T1:0:0 ---------------------------------------- (16) YES