/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 my_log(g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 44 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 2 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (10) TRUE ---------------------------------------- (0) Obligation: Clauses: my_log(X, Y, Ret) :- ','(>=(X, Y), ','(>(Y, 1), ','(!, ','(is(X1, //(X, Y)), ','(my_log(X1, Y, Ret1), is(Ret, +(1, Ret1))))))). my_log(X2, X3, 1). Query: my_log(g,g,a) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(my_log X Y Ret)", "(',' (>= X Y) (',' (> Y (1)) (',' (!) (',' (is X1 (// X Y)) (',' (my_log X1 Y Ret1) (is Ret (+ (1) Ret1)))))))" ], [ "(my_log X2 X3 (1))", null ] ] }, "graph": { "nodes": { "11": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (>= T18 T19) (',' (> T19 (1)) (',' (!_1) (',' (is X23 (// T18 T19)) (',' (my_log X23 T19 X24) (is T21 (+ (1) X24)))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T18", "T19" ], "free": [ "X23", "X24" ], "exprvars": [] } }, "12": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2034": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2067": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1173": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": ">" }] }, "ground": [ "T19", "T18" ], "free": [ "X23", "X24" ], "exprvars": [ "T19", "T18" ] } }, "type": "Nodes", "1998": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (my_log T22 T19 X24) (is T21 (+ (1) X24)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T22", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "name": "T19", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "//t" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T19", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": [ "T19", "T18", "T22" ], "free": [ "X23", "X24" ], "exprvars": [ "T19", "T18", "T22" ] } }, "980": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T19 (1)) (',' (!_1) (',' (is X23 (// T18 T19)) (',' (my_log X23 T19 X24) (is T21 (+ (1) X24))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": [ "T19", "T18" ], "free": [ "X23", "X24" ], "exprvars": [ "T19", "T18" ] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(my_log T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "2049": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [], "exprvars": ["T25"] } }, "5": { "goal": [ { "clause": 0, "scope": 1, "term": "(my_log T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(my_log T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "1982": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X23 (// T18 T19)) (',' (my_log X23 T19 X24) (is T21 (+ (1) X24))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T19", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": [ "T19", "T18" ], "free": [ "X23", "X24" ], "exprvars": [ "T19", "T18" ] } }, "2059": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T28", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T25", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }] }, "ground": [], "free": [], "exprvars": [ "T25", "T28" ] } }, "1981": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T19", "type": "PlainIntegerVariable" }, "operation": ">=" } ] }, "ground": [ "T19", "T18" ], "free": [ "X23", "X24" ], "exprvars": [ "T19", "T18" ] } }, "2003": { "goal": [{ "clause": -1, "scope": -1, "term": "(is T21 (+ (1) T25))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T25"], "free": [], "exprvars": [] } }, "2069": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1980": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (!_1) (',' (is X23 (// T18 T19)) (',' (my_log X23 T19 X24) (is T21 (+ (1) X24)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T19", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": [ "T19", "T18" ], "free": [ "X23", "X24" ], "exprvars": [ "T19", "T18" ] } }, "2002": { "goal": [{ "clause": -1, "scope": -1, "term": "(my_log T22 T19 X24)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T22", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T18", "type": "PlainIntegerVariable" }, { "name": "T19", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "//t" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "1" }, "type": "PlainIntegerRelation", "rhs": { "name": "T19", "type": "PlainIntegerVariable" }, "operation": "<" }, { "lhs": { "name": "T19", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T18", "type": "PlainIntegerVariable" }, "operation": "<=" } ] }, "ground": [ "T19", "T22" ], "free": ["X24"], "exprvars": [ "T19", "T18", "T22" ] } }, "2046": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T28", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "1" }, { "name": "T25", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }] }, "ground": [ "T25", "T28" ], "free": [], "exprvars": [ "T25", "T28" ] } }, "2068": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "9": { "goal": [{ "clause": 0, "scope": 1, "term": "(my_log T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "10": { "goal": [{ "clause": 1, "scope": 1, "term": "(my_log T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 5, "label": "CASE" }, { "from": 5, "to": 9, "label": "PARALLEL" }, { "from": 5, "to": 10, "label": "PARALLEL" }, { "from": 9, "to": 11, "label": "ONLY EVAL with clause\nmy_log(X20, X21, X22) :- ','(>=(X20, X21), ','(>(X21, 1), ','(!_1, ','(is(X23, //(X20, X21)), ','(my_log(X23, X21, X24), is(X22, +(1, X24))))))).\nand substitutionT1 -> T18,\nX20 -> T18,\nT2 -> T19,\nX21 -> T19,\nT3 -> T21,\nX22 -> T21,\nT20 -> T21" }, { "from": 10, "to": 2067, "label": "EVAL with clause\nmy_log(X41, X42, 1).\nand substitutionT1 -> T33,\nX41 -> T33,\nT2 -> T34,\nX42 -> T34,\nT3 -> 1" }, { "from": 10, "to": 2068, "label": "EVAL-BACKTRACK" }, { "from": 11, "to": 12, "label": "IS ERROR" }, { "from": 11, "to": 980, "label": "ARITHCOMP SUCCESS" }, { "from": 11, "to": 1173, "label": "ARITHCOMP FAIL" }, { "from": 980, "to": 1980, "label": "ARITHCOMP SUCCESS" }, { "from": 980, "to": 1981, "label": "ARITHCOMP FAIL" }, { "from": 1980, "to": 1982, "label": "CUT" }, { "from": 1982, "to": 1998, "label": "\nX23 -> T22" }, { "from": 1998, "to": 2002, "label": "SPLIT 1" }, { "from": 1998, "to": 2003, "label": "SPLIT 2\nnew knowledge:\nT22 is ground\nT19 is ground\nT25 is ground\nreplacements:X24 -> T25" }, { "from": 2002, "to": 3, "label": "INSTANCE with matching:\nT1 -> T22\nT2 -> T19\nT3 -> X24" }, { "from": 2003, "to": 2034, "label": "IS ERROR" }, { "from": 2003, "to": 2046, "label": "\nT21 -> T28" }, { "from": 2003, "to": 2049, "label": "IS FAIL" }, { "from": 2046, "to": 2059, "label": "SUCCESS" }, { "from": 2067, "to": 2069, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f3_out(T22, T19) -> f2002_out(T22, T19) :|: TRUE f2002_in(x, x1) -> f3_in(x, x1) :|: TRUE f12_out -> f11_out(x2, x3) :|: TRUE f980_out(x4, x5) -> f11_out(x5, x4) :|: x5 >= x4 f11_in(x6, x7) -> f12_in :|: TRUE f1173_out(x8, x9) -> f11_out(x9, x8) :|: x9 < x8 f11_in(x10, x11) -> f980_in(x11, x10) :|: x10 >= x11 f11_in(x12, x13) -> f1173_in(x13, x12) :|: x12 < x13 f3_in(T1, T2) -> f5_in(T1, T2) :|: TRUE f5_out(x14, x15) -> f3_out(x14, x15) :|: TRUE f1982_in(x16, x17) -> f1998_in(x18, x17, x16) :|: x18 = //(x16, x17) f1998_out(x19, x20, x21) -> f1982_out(x21, x20) :|: TRUE f9_out(x22, x23) -> f5_out(x22, x23) :|: TRUE f5_in(x24, x25) -> f10_in(x24, x25) :|: TRUE f5_in(x26, x27) -> f9_in(x26, x27) :|: TRUE f10_out(x28, x29) -> f5_out(x28, x29) :|: TRUE f2002_out(x30, x31) -> f2003_in(x32) :|: TRUE f1998_in(x33, x34, x35) -> f2002_in(x33, x34) :|: TRUE f2003_out(x36) -> f1998_out(x37, x38, x39) :|: TRUE f11_out(x40, x41) -> f9_out(x40, x41) :|: TRUE f9_in(x42, x43) -> f11_in(x42, x43) :|: TRUE f2049_out(T25) -> f2003_out(T25) :|: TRUE f2003_in(x44) -> f2046_in(x44, x45) :|: x45 = 1 + x44 f2034_out -> f2003_out(x46) :|: TRUE f2046_out(x47, x48) -> f2003_out(x47) :|: TRUE f2003_in(x49) -> f2034_in :|: TRUE f2003_in(x50) -> f2049_in(x50) :|: !(x51 = 1 + x50) f1980_out(x52, x53) -> f980_out(x53, x52) :|: x53 > 1 f1981_out(x54, x55) -> f980_out(x54, x55) :|: x54 <= 1 f980_in(x56, x57) -> f1981_in(x56, x57) :|: x56 <= 1 f980_in(x58, x59) -> f1980_in(x59, x58) :|: x58 > 1 f1982_out(x60, x61) -> f1980_out(x60, x61) :|: TRUE f1980_in(x62, x63) -> f1982_in(x62, x63) :|: TRUE f2046_in(x64, x65) -> f2046_out(x64, x65) :|: TRUE Start term: f3_in(T1, T2) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f2002_in(x, x1) -> f3_in(x, x1) :|: TRUE f11_in(x10, x11) -> f980_in(x11, x10) :|: x10 >= x11 f3_in(T1, T2) -> f5_in(T1, T2) :|: TRUE f1982_in(x16, x17) -> f1998_in(x18, x17, x16) :|: x18 = //(x16, x17) f5_in(x26, x27) -> f9_in(x26, x27) :|: TRUE f1998_in(x33, x34, x35) -> f2002_in(x33, x34) :|: TRUE f9_in(x42, x43) -> f11_in(x42, x43) :|: TRUE f980_in(x58, x59) -> f1980_in(x59, x58) :|: x58 > 1 f1980_in(x62, x63) -> f1982_in(x62, x63) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f2002_in(x, x1) -> f3_in(x, x1) :|: TRUE f11_in(x10, x11) -> f980_in(x11, x10) :|: x10 >= x11 f3_in(T1, T2) -> f5_in(T1, T2) :|: TRUE f1982_in(x16, x17) -> f1998_in(x18, x17, x16) :|: x18 = //(x16, x17) f5_in(x26, x27) -> f9_in(x26, x27) :|: TRUE f1998_in(x33, x34, x35) -> f2002_in(x33, x34) :|: TRUE f9_in(x42, x43) -> f11_in(x42, x43) :|: TRUE f980_in(x58, x59) -> f1980_in(x59, x58) :|: x58 > 1 f1980_in(x62, x63) -> f1982_in(x62, x63) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f1982_in(x16:0, x17:0) -> f1982_in(x18:0, x17:0) :|: x18:0 = //(x16:0, x17:0) && x17:0 > 1 && TRUE && x18:0 >= x17:0 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f1982_in(x16:0, x17:0) -> f1982_in(x18:0, x17:0) :|: x18:0 = //(x16:0, x17:0) && x17:0 > 1 && TRUE && x18:0 >= x17:0 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1982_in(x16:0, x17:0) -> f1982_in(x18:0, x17:0) :|: x18:0 = //(x16:0, x17:0) && x17:0 > 1 && TRUE && x18:0 >= x17:0 No arcs! This digraph is fully evaluated! ---------------------------------------- (10) TRUE