/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 test_fun(g,g,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 68 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 8 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 44 ms] (10) TRUE ---------------------------------------- (0) Obligation: Clauses: test_fun(X, Y, Z) :- loop(X, Y, Z). loop(X, Tmp1, Tmp2) :- ','(>(X, 0), ','(=:=(X, *(2, Tmp1)), ','(is(X1, -(X, 1)), loop(X1, Tmp2, Tmp2)))). loop(X, Tmp1, Tmp2) :- =<(X, Y). Query: test_fun(g,g,g) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 5, "program": { "directives": [], "clauses": [ [ "(test_fun X Y Z)", "(loop X Y Z)" ], [ "(loop X Tmp1 Tmp2)", "(',' (> X (0)) (',' (=:= X (* (2) Tmp1)) (',' (is X1 (- X (1))) (loop X1 Tmp2 Tmp2))))" ], [ "(loop X Tmp1 Tmp2)", "(=< X Y)" ] ] }, "graph": { "nodes": { "15": { "goal": [ { "clause": 1, "scope": 2, "term": "(loop T13 T14 T15)" }, { "clause": 2, "scope": 2, "term": "(loop T13 T14 T15)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T13", "T14", "T15" ], "free": [], "exprvars": [] } }, "16": { "goal": [{ "clause": 1, "scope": 2, "term": "(loop T13 T14 T15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T13", "T14", "T15" ], "free": [], "exprvars": [] } }, "17": { "goal": [{ "clause": 2, "scope": 2, "term": "(loop T13 T14 T15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T13", "T14", "T15" ], "free": [], "exprvars": [] } }, "18": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T31 (0)) (',' (=:= T31 (* (2) T32)) (',' (is X36 (- T31 (1))) (loop X36 T33 T33))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T31", "T32", "T33" ], "free": ["X36"], "exprvars": [] } }, "19": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2265": { "goal": [{ "clause": -1, "scope": -1, "term": "(loop T34 T33 T33)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "name": "T32", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "name": "T34", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T31", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "-" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T31", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T31", "T34", "T33", "T32" ], "free": ["X36"], "exprvars": [ "T31", "T34", "T32" ] } }, "2264": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "name": "T32", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "!=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T31", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T31", "T33", "T32" ], "free": ["X36"], "exprvars": [ "T31", "T32" ] } }, "2263": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X36 (- T31 (1))) (loop X36 T33 T33))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T31", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "type": "PlainIntegerConstant", "value": "2" }, { "name": "T32", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "*" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T31", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T31", "T33", "T32" ], "free": ["X36"], "exprvars": [ "T31", "T32" ] } }, "type": "Nodes", "1139": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1138": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T31", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T31", "T33", "T32" ], "free": ["X36"], "exprvars": ["T31"] } }, "1137": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (=:= T31 (* (2) T32)) (',' (is X36 (- T31 (1))) (loop X36 T33 T33)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T31", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T31", "T33", "T32" ], "free": ["X36"], "exprvars": ["T31"] } }, "5": { "goal": [{ "clause": -1, "scope": -1, "term": "(test_fun T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(test_fun T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "2267": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "7": { "goal": [{ "clause": -1, "scope": -1, "term": "(loop T13 T14 T15)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T13", "T14", "T15" ], "free": [], "exprvars": [] } }, "2266": { "goal": [{ "clause": -1, "scope": -1, "term": "(=< T43 X51)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T43"], "free": ["X51"], "exprvars": [] } } }, "edges": [ { "from": 5, "to": 6, "label": "CASE" }, { "from": 6, "to": 7, "label": "ONLY EVAL with clause\ntest_fun(X12, X13, X14) :- loop(X12, X13, X14).\nand substitutionT1 -> T13,\nX12 -> T13,\nT2 -> T14,\nX13 -> T14,\nT3 -> T15,\nX14 -> T15" }, { "from": 7, "to": 15, "label": "CASE" }, { "from": 15, "to": 16, "label": "PARALLEL" }, { "from": 15, "to": 17, "label": "PARALLEL" }, { "from": 16, "to": 18, "label": "ONLY EVAL with clause\nloop(X33, X34, X35) :- ','(>(X33, 0), ','(=:=(X33, *(2, X34)), ','(is(X36, -(X33, 1)), loop(X36, X35, X35)))).\nand substitutionT13 -> T31,\nX33 -> T31,\nT14 -> T32,\nX34 -> T32,\nT15 -> T33,\nX35 -> T33" }, { "from": 17, "to": 2266, "label": "ONLY EVAL with clause\nloop(X48, X49, X50) :- =<(X48, X51).\nand substitutionT13 -> T43,\nX48 -> T43,\nT14 -> T44,\nX49 -> T44,\nT15 -> T45,\nX50 -> T45" }, { "from": 18, "to": 19, "label": "IS ERROR" }, { "from": 18, "to": 1137, "label": "ARITHCOMP SUCCESS" }, { "from": 18, "to": 1138, "label": "ARITHCOMP FAIL" }, { "from": 1137, "to": 1139, "label": "IS ERROR" }, { "from": 1137, "to": 2263, "label": "ARITHCOMP SUCCESS" }, { "from": 1137, "to": 2264, "label": "ARITHCOMP FAIL" }, { "from": 2263, "to": 2265, "label": "\nX36 -> T34" }, { "from": 2265, "to": 7, "label": "INSTANCE with matching:\nT13 -> T34\nT14 -> T33\nT15 -> T33" }, { "from": 2266, "to": 2267, "label": "IS ERROR" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f1139_out -> f1137_out(T31, T32, T33) :|: TRUE f2263_out(x, x1, x2) -> f1137_out(x, x2, x1) :|: x = 2 * x2 f2264_out(x3, x4, x5) -> f1137_out(x3, x5, x4) :|: !(x3 = 2 * x5) f1137_in(x6, x7, x8) -> f2264_in(x6, x8, x7) :|: !(x6 = 2 * x7) f1137_in(x9, x10, x11) -> f1139_in :|: TRUE f1137_in(x12, x13, x14) -> f2263_in(x12, x14, x13) :|: x12 = 2 * x13 f2265_in(x15, x16, x17, x18) -> f7_in(x15, x16, x16) :|: TRUE f7_out(x19, x20, x20) -> f2265_out(x19, x20, x21, x22) :|: TRUE f2263_in(x23, x24, x25) -> f2265_in(x26, x24, x23, x25) :|: x26 = x23 - 1 f2265_out(x27, x28, x29, x30) -> f2263_out(x29, x28, x30) :|: TRUE f1137_out(x31, x32, x33) -> f18_out(x31, x32, x33) :|: x31 > 0 f19_out -> f18_out(x34, x35, x36) :|: TRUE f18_in(x37, x38, x39) -> f1137_in(x37, x38, x39) :|: x37 > 0 f18_in(x40, x41, x42) -> f19_in :|: TRUE f18_in(x43, x44, x45) -> f1138_in(x43, x45, x44) :|: x43 <= 0 f1138_out(x46, x47, x48) -> f18_out(x46, x48, x47) :|: x46 <= 0 f15_in(T13, T14, T15) -> f16_in(T13, T14, T15) :|: TRUE f17_out(x49, x50, x51) -> f15_out(x49, x50, x51) :|: TRUE f16_out(x52, x53, x54) -> f15_out(x52, x53, x54) :|: TRUE f15_in(x55, x56, x57) -> f17_in(x55, x56, x57) :|: TRUE f18_out(x58, x59, x60) -> f16_out(x58, x59, x60) :|: TRUE f16_in(x61, x62, x63) -> f18_in(x61, x62, x63) :|: TRUE f15_out(x64, x65, x66) -> f7_out(x64, x65, x66) :|: TRUE f7_in(x67, x68, x69) -> f15_in(x67, x68, x69) :|: TRUE f5_in(T1, T2, T3) -> f6_in(T1, T2, T3) :|: TRUE f6_out(x70, x71, x72) -> f5_out(x70, x71, x72) :|: TRUE f6_in(x73, x74, x75) -> f7_in(x73, x74, x75) :|: TRUE f7_out(x76, x77, x78) -> f6_out(x76, x77, x78) :|: TRUE Start term: f5_in(T1, T2, T3) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f1137_in(x12, x13, x14) -> f2263_in(x12, x14, x13) :|: x12 = 2 * x13 f2265_in(x15, x16, x17, x18) -> f7_in(x15, x16, x16) :|: TRUE f2263_in(x23, x24, x25) -> f2265_in(x26, x24, x23, x25) :|: x26 = x23 - 1 f18_in(x37, x38, x39) -> f1137_in(x37, x38, x39) :|: x37 > 0 f15_in(T13, T14, T15) -> f16_in(T13, T14, T15) :|: TRUE f16_in(x61, x62, x63) -> f18_in(x61, x62, x63) :|: TRUE f7_in(x67, x68, x69) -> f15_in(x67, x68, x69) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f1137_in(x12, x13, x14) -> f2263_in(x12, x14, x13) :|: x12 = 2 * x13 f2265_in(x15, x16, x17, x18) -> f7_in(x15, x16, x16) :|: TRUE f2263_in(x23, x24, x25) -> f2265_in(x26, x24, x23, x25) :|: x26 = x23 - 1 f18_in(x37, x38, x39) -> f1137_in(x37, x38, x39) :|: x37 > 0 f15_in(T13, T14, T15) -> f16_in(T13, T14, T15) :|: TRUE f16_in(x61, x62, x63) -> f18_in(x61, x62, x63) :|: TRUE f7_in(x67, x68, x69) -> f15_in(x67, x68, x69) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f15_in(times~cons_2~T14:0, T14:0, T15:0) -> f15_in(2 * T14:0 - 1, T15:0, T15:0) :|: 2 * T14:0 > 0 && times~cons_2~T14:0 = 2 * T14:0 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f15_in(times~cons_2~T14:0, T14:0, T15:0) -> f15_in(arith, T15:0, T15:0) :|: 2 * T14:0 > 0 && times~cons_2~T14:0 = 2 * T14:0 && arith = 2 * T14:0 - 1 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f15_in(times~cons_2~T14:0, T14:0, T15:0) -> f15_in(arith, T15:0, T15:0) :|: 2 * T14:0 > 0 && times~cons_2~T14:0 = 2 * T14:0 && arith = 2 * T14:0 - 1 No arcs! This digraph is fully evaluated! ---------------------------------------- (10) TRUE