/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 fib(g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 47 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 20 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 45 ms] (10) IRSwT (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IRSwT (13) TempFilterProof [SOUND, 37 ms] (14) IntTRS (15) PolynomialOrderProcessor [EQUIVALENT, 0 ms] (16) YES ---------------------------------------- (0) Obligation: Clauses: fib(0, 0). fib(1, 1). fib(M, N) :- ','(>(M, 1), ','(is(M1, -(M, 1)), ','(is(M2, -(M, 2)), ','(fib(M1, N1), ','(fib(M2, N2), is(N, +(N1, N2))))))). no_trace_main :- ','(time(X1), ','(fib(15, M), ','(time(T), ','(write('Executed in '), ','(write(T), ','(write(' mS.'), ','(nl, ','(write('Result '), ','(write(M), nl))))))))). trace_main(Eventfile) :- ','(start_event_trace, ','(fib(15, M), ','(stop_event_trace, ','(save_trace(Eventfile), ','(write('Result '), ','(write(M), nl)))))). save_trace(X) :- ','(write('Saving trace in file '), ','(write(X), ','(write('... '), ','(open(X, write, Y), ','(save_event_trace(Y), ','(close(X), ','(write('done.'), nl))))))). time(T) :- statistics(runtime, .(X2, .(T, []))). Query: fib(g,a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 2, "program": { "directives": [], "clauses": [ [ "(fib (0) (0))", null ], [ "(fib (1) (1))", null ], [ "(fib M N)", "(',' (> M (1)) (',' (is M1 (- M (1))) (',' (is M2 (- M (2))) (',' (fib M1 N1) (',' (fib M2 N2) (is N (+ N1 N2)))))))" ], [ "(no_trace_main)", "(',' (time X1) (',' (fib (15) M) (',' (time T) (',' (write ('Executed in ')) (',' (write T) (',' (write (' mS.')) (',' (nl) (',' (write ('Result ')) (',' (write M) (nl))))))))))" ], [ "(trace_main Eventfile)", "(',' (start_event_trace) (',' (fib (15) M) (',' (stop_event_trace) (',' (save_trace Eventfile) (',' (write ('Result ')) (',' (write M) (nl)))))))" ], [ "(save_trace X)", "(',' (write ('Saving trace in file ')) (',' (write X) (',' (write ('... ')) (',' (open X (write) Y) (',' (save_event_trace Y) (',' (close X) (',' (write ('done.')) (nl))))))))" ], [ "(time T)", "(statistics (runtime) (. X2 (. T ([]))))" ] ] }, "graph": { "nodes": { "23": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "26": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "27": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T8 (1)) (',' (is X13 (- T8 (1))) (',' (is X14 (- T8 (2))) (',' (fib X13 X15) (',' (fib X14 X16) (is T10 (+ X15 X16)))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [ "X13", "X14", "X15", "X16" ], "exprvars": [] } }, "28": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "1613": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "598": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X13 (- T8 (1))) (',' (is X14 (- T8 (2))) (',' (fib X13 X15) (',' (fib X14 X16) (is T10 (+ X15 X16))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T8", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": ["T8"], "free": [ "X13", "X14", "X15", "X16" ], "exprvars": ["T8"] } }, "910": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (fib T11 X15) (',' (fib T12 X16) (is T10 (+ X15 X16))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T11", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T8", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T12", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T8", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "2" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T8", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T12", "T11", "T8" ], "free": [ "X13", "X14", "X15", "X16" ], "exprvars": [ "T12", "T11", "T8" ] } }, "617": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T8", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": ["T8"], "free": [ "X13", "X14", "X15", "X16" ], "exprvars": ["T8"] } }, "1518": { "goal": [{ "clause": -1, "scope": -1, "term": "(fib T12 X16)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T12"], "free": ["X16"], "exprvars": [] } }, "1636": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T15", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T14", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }] }, "ground": [], "free": [], "exprvars": [ "T14", "T13", "T15" ] } }, "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": [] } }, "15": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": 1, "scope": 1, "term": "(fib T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "19": { "goal": [{ "clause": 2, "scope": 1, "term": "(fib T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "1030": { "goal": [{ "clause": -1, "scope": -1, "term": "(fib T11 X15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T11", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T8", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "name": "T12", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T8", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "2" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T8", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": ["T11"], "free": ["X15"], "exprvars": [ "T12", "T11", "T8" ] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(fib T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "5": { "goal": [ { "clause": 0, "scope": 1, "term": "(fib T1 T2)" }, { "clause": 1, "scope": 1, "term": "(fib T1 T2)" }, { "clause": 2, "scope": 1, "term": "(fib T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(fib T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "7": { "goal": [ { "clause": 1, "scope": 1, "term": "(fib T1 T2)" }, { "clause": 2, "scope": 1, "term": "(fib T1 T2)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "821": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X14 (- T8 (2))) (',' (fib T11 X15) (',' (fib X14 X16) (is T10 (+ X15 X16)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T11", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T8", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T8", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T11", "T8" ], "free": [ "X13", "X14", "X15", "X16" ], "exprvars": [ "T11", "T8" ] } }, "1045": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (fib T12 X16) (is T10 (+ T13 X16)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13" ], "free": ["X16"], "exprvars": [] } }, "1629": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T14", "T13" ], "free": [], "exprvars": [ "T14", "T13" ] } }, "1528": { "goal": [{ "clause": -1, "scope": -1, "term": "(is T10 (+ T13 T14))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T13", "T14" ], "free": [], "exprvars": [] } }, "1627": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T15", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T13", "type": "PlainIntegerVariable" }, { "name": "T14", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }] }, "ground": [ "T14", "T13", "T15" ], "free": [], "exprvars": [ "T14", "T13", "T15" ] } }, "21": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 5, "label": "CASE" }, { "from": 5, "to": 6, "label": "PARALLEL" }, { "from": 5, "to": 7, "label": "PARALLEL" }, { "from": 6, "to": 11, "label": "EVAL with clause\nfib(0, 0).\nand substitutionT1 -> 0,\nT2 -> 0" }, { "from": 6, "to": 13, "label": "EVAL-BACKTRACK" }, { "from": 7, "to": 17, "label": "PARALLEL" }, { "from": 7, "to": 19, "label": "PARALLEL" }, { "from": 11, "to": 15, "label": "SUCCESS" }, { "from": 17, "to": 21, "label": "EVAL with clause\nfib(1, 1).\nand substitutionT1 -> 1,\nT2 -> 1" }, { "from": 17, "to": 23, "label": "EVAL-BACKTRACK" }, { "from": 19, "to": 27, "label": "ONLY EVAL with clause\nfib(X11, X12) :- ','(>(X11, 1), ','(is(X13, -(X11, 1)), ','(is(X14, -(X11, 2)), ','(fib(X13, X15), ','(fib(X14, X16), is(X12, +(X15, X16))))))).\nand substitutionT1 -> T8,\nX11 -> T8,\nT2 -> T10,\nX12 -> T10,\nT9 -> T10" }, { "from": 21, "to": 26, "label": "SUCCESS" }, { "from": 27, "to": 28, "label": "IS ERROR" }, { "from": 27, "to": 598, "label": "ARITHCOMP SUCCESS" }, { "from": 27, "to": 617, "label": "ARITHCOMP FAIL" }, { "from": 598, "to": 821, "label": "\nX13 -> T11" }, { "from": 821, "to": 910, "label": "\nX14 -> T12" }, { "from": 910, "to": 1030, "label": "SPLIT 1" }, { "from": 910, "to": 1045, "label": "SPLIT 2\nnew knowledge:\nT11 is ground\nT13 is ground\nreplacements:X15 -> T13" }, { "from": 1030, "to": 2, "label": "INSTANCE with matching:\nT1 -> T11\nT2 -> X15" }, { "from": 1045, "to": 1518, "label": "SPLIT 1" }, { "from": 1045, "to": 1528, "label": "SPLIT 2\nnew knowledge:\nT12 is ground\nT14 is ground\nreplacements:X16 -> T14" }, { "from": 1518, "to": 2, "label": "INSTANCE with matching:\nT1 -> T12\nT2 -> X16" }, { "from": 1528, "to": 1613, "label": "IS ERROR" }, { "from": 1528, "to": 1627, "label": "\nT10 -> T15" }, { "from": 1528, "to": 1629, "label": "IS FAIL" }, { "from": 1627, "to": 1636, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f821_in(T8, T11) -> f910_in(T11, T12, T8) :|: T12 = T8 - 2 f910_out(x, x1, x2) -> f821_out(x2, x) :|: TRUE f1045_in(x3, x4) -> f1518_in(x3) :|: TRUE f1518_out(x5) -> f1528_in(x6, x7) :|: TRUE f1528_out(x8, x9) -> f1045_out(x10, x8) :|: TRUE f1627_out(T14, T13, T15) -> f1528_out(T13, T14) :|: TRUE f1528_in(x11, x12) -> f1613_in :|: TRUE f1528_in(x13, x14) -> f1627_in(x14, x13, x15) :|: x15 = x13 + x14 f1629_out(x16, x17) -> f1528_out(x17, x16) :|: TRUE f1528_in(x18, x19) -> f1629_in(x19, x18) :|: !(x20 = x18 + x19) f1613_out -> f1528_out(x21, x22) :|: TRUE f1045_out(x23, x24) -> f910_out(x25, x23, x26) :|: TRUE f1030_out(x27) -> f1045_in(x28, x29) :|: TRUE f910_in(x30, x31, x32) -> f1030_in(x30) :|: TRUE f1627_in(x33, x34, x35) -> f1627_out(x33, x34, x35) :|: TRUE f5_in(T1) -> f6_in(T1) :|: TRUE f7_out(x36) -> f5_out(x36) :|: TRUE f5_in(x37) -> f7_in(x37) :|: TRUE f6_out(x38) -> f5_out(x38) :|: TRUE f17_out(x39) -> f7_out(x39) :|: TRUE f7_in(x40) -> f19_in(x40) :|: TRUE f19_out(x41) -> f7_out(x41) :|: TRUE f7_in(x42) -> f17_in(x42) :|: TRUE f2_out(x43) -> f1030_out(x43) :|: TRUE f1030_in(x44) -> f2_in(x44) :|: TRUE f27_out(x45) -> f19_out(x45) :|: TRUE f19_in(x46) -> f27_in(x46) :|: TRUE f2_out(x47) -> f1518_out(x47) :|: TRUE f1518_in(x48) -> f2_in(x48) :|: TRUE f821_out(x49, x50) -> f598_out(x49) :|: TRUE f598_in(x51) -> f821_in(x51, x52) :|: x52 = x51 - 1 f28_out -> f27_out(x53) :|: TRUE f27_in(x54) -> f28_in :|: TRUE f598_out(x55) -> f27_out(x55) :|: x55 > 1 f27_in(x56) -> f617_in(x56) :|: x56 <= 1 f617_out(x57) -> f27_out(x57) :|: x57 <= 1 f27_in(x58) -> f598_in(x58) :|: x58 > 1 f5_out(x59) -> f2_out(x59) :|: TRUE f2_in(x60) -> f5_in(x60) :|: TRUE Start term: f2_in(T1) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f821_in(T8, T11) -> f910_in(T11, T12, T8) :|: T12 = T8 - 2 f910_in(x30, x31, x32) -> f1030_in(x30) :|: TRUE f5_in(x37) -> f7_in(x37) :|: TRUE f7_in(x40) -> f19_in(x40) :|: TRUE f1030_in(x44) -> f2_in(x44) :|: TRUE f19_in(x46) -> f27_in(x46) :|: TRUE f598_in(x51) -> f821_in(x51, x52) :|: x52 = x51 - 1 f27_in(x58) -> f598_in(x58) :|: x58 > 1 f2_in(x60) -> f5_in(x60) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f821_in(T8, T11) -> f910_in(T11, T12, T8) :|: T12 = T8 - 2 f910_in(x30, x31, x32) -> f1030_in(x30) :|: TRUE f5_in(x37) -> f7_in(x37) :|: TRUE f7_in(x40) -> f19_in(x40) :|: TRUE f1030_in(x44) -> f2_in(x44) :|: TRUE f19_in(x46) -> f27_in(x46) :|: TRUE f598_in(x51) -> f821_in(x51, x52) :|: x52 = x51 - 1 f27_in(x58) -> f598_in(x58) :|: x58 > 1 f2_in(x60) -> f5_in(x60) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f5_in(x37:0) -> f5_in(x37:0 - 1) :|: x37:0 > 1 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f5_in(x37:0) -> f5_in(arith) :|: x37:0 > 1 && arith = x37:0 - 1 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f5_in(x37:0) -> f5_in(arith) :|: x37:0 > 1 && arith = x37:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f5_in(x37:0) -> f5_in(arith) :|: x37:0 > 1 && arith = x37:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f5_in(x37:0:0) -> f5_in(x37:0:0 - 1) :|: x37:0:0 > 1 ---------------------------------------- (13) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f5_in(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (14) Obligation: Rules: f5_in(x37:0:0) -> f5_in(c) :|: c = x37:0:0 - 1 && x37:0:0 > 1 ---------------------------------------- (15) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f5_in(x)] = x The following rules are decreasing: f5_in(x37:0:0) -> f5_in(c) :|: c = x37:0:0 - 1 && x37:0:0 > 1 The following rules are bounded: f5_in(x37:0:0) -> f5_in(c) :|: c = x37:0:0 - 1 && x37:0:0 > 1 ---------------------------------------- (16) YES