/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 greatest_common_divisor(g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 23 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 38 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (10) TRUE ---------------------------------------- (0) Obligation: Clauses: greatest_common_divisor(I, 0, I). greatest_common_divisor(I, J, Gcd) :- ','(>(J, 0), ','(is(R, mod(I, J)), greatest_common_divisor(J, R, Gcd))). Query: greatest_common_divisor(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": [ [ "(greatest_common_divisor I (0) I)", null ], [ "(greatest_common_divisor I J Gcd)", "(',' (> J (0)) (',' (is R (mod I J)) (greatest_common_divisor J R Gcd)))" ] ] }, "graph": { "nodes": { "12": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "14": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "16": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "18": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T17 (0)) (',' (is X16 (mod T16 T17)) (greatest_common_divisor T17 X16 T19)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17" ], "free": ["X16"], "exprvars": [] } }, "19": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(greatest_common_divisor T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "1832": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1831": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T17", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T17", "T16" ], "free": ["X16"], "exprvars": ["T17"] } }, "1830": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X16 (mod T16 T17)) (greatest_common_divisor T17 X16 T19))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T17", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T17", "T16" ], "free": ["X16"], "exprvars": ["T17"] } }, "6": { "goal": [ { "clause": 0, "scope": 1, "term": "(greatest_common_divisor T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(greatest_common_divisor T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "7": { "goal": [{ "clause": 0, "scope": 1, "term": "(greatest_common_divisor T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "8": { "goal": [{ "clause": 1, "scope": 1, "term": "(greatest_common_divisor T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "1916": { "goal": [{ "clause": -1, "scope": -1, "term": "(greatest_common_divisor T17 T20 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T20", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T16", "type": "PlainIntegerVariable" }, { "name": "T17", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "mod" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T17", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T20", "T17", "T16" ], "free": ["X16"], "exprvars": [ "T20", "T17", "T16" ] } } }, "edges": [ { "from": 1, "to": 6, "label": "CASE" }, { "from": 6, "to": 7, "label": "PARALLEL" }, { "from": 6, "to": 8, "label": "PARALLEL" }, { "from": 7, "to": 12, "label": "EVAL with clause\ngreatest_common_divisor(X5, 0, X5).\nand substitutionT1 -> T8,\nX5 -> T8,\nT2 -> 0,\nT3 -> T8" }, { "from": 7, "to": 14, "label": "EVAL-BACKTRACK" }, { "from": 8, "to": 18, "label": "ONLY EVAL with clause\ngreatest_common_divisor(X13, X14, X15) :- ','(>(X14, 0), ','(is(X16, mod(X13, X14)), greatest_common_divisor(X14, X16, X15))).\nand substitutionT1 -> T16,\nX13 -> T16,\nT2 -> T17,\nX14 -> T17,\nT3 -> T19,\nX15 -> T19,\nT18 -> T19" }, { "from": 12, "to": 16, "label": "SUCCESS" }, { "from": 18, "to": 19, "label": "IS ERROR" }, { "from": 18, "to": 1830, "label": "ARITHCOMP SUCCESS" }, { "from": 18, "to": 1831, "label": "ARITHCOMP FAIL" }, { "from": 1830, "to": 1832, "label": "IS ERROR" }, { "from": 1830, "to": 1916, "label": "\nX16 -> T20" }, { "from": 1916, "to": 1, "label": "INSTANCE with matching:\nT1 -> T17\nT2 -> T20\nT3 -> T19" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f18_out(T17, T16) -> f8_out(T16, T17) :|: TRUE f8_in(x, x1) -> f18_in(x1, x) :|: TRUE f6_in(T1, T2) -> f7_in(T1, T2) :|: TRUE f6_in(x2, x3) -> f8_in(x2, x3) :|: TRUE f7_out(x4, x5) -> f6_out(x4, x5) :|: TRUE f8_out(x6, x7) -> f6_out(x6, x7) :|: TRUE f1831_out(x8, x9) -> f18_out(x8, x9) :|: x8 <= 0 f1830_out(x10, x11) -> f18_out(x11, x10) :|: x11 > 0 f19_out -> f18_out(x12, x13) :|: TRUE f18_in(x14, x15) -> f1830_in(x15, x14) :|: x14 > 0 f18_in(x16, x17) -> f19_in :|: TRUE f18_in(x18, x19) -> f1831_in(x18, x19) :|: x18 <= 0 f1_out(x20, x21) -> f1916_out(x20, x21, x22) :|: TRUE f1916_in(x23, x24, x25) -> f1_in(x23, x24) :|: TRUE f1830_in(x26, x27) -> f1832_in :|: TRUE f1830_in(x28, x29) -> f1916_in(x29, x30, x28) :|: x30 = mod(x28, x29) f1916_out(x31, x32, x33) -> f1830_out(x33, x31) :|: TRUE f1832_out -> f1830_out(x34, x35) :|: TRUE f1_in(x36, x37) -> f6_in(x36, x37) :|: TRUE f6_out(x38, x39) -> f1_out(x38, x39) :|: TRUE Start term: f1_in(T1, T2) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f8_in(x, x1) -> f18_in(x1, x) :|: TRUE f6_in(x2, x3) -> f8_in(x2, x3) :|: TRUE f18_in(x14, x15) -> f1830_in(x15, x14) :|: x14 > 0 f1916_in(x23, x24, x25) -> f1_in(x23, x24) :|: TRUE f1830_in(x28, x29) -> f1916_in(x29, x30, x28) :|: x30 = mod(x28, x29) f1_in(x36, x37) -> f6_in(x36, x37) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f8_in(x, x1) -> f18_in(x1, x) :|: TRUE f6_in(x2, x3) -> f8_in(x2, x3) :|: TRUE f18_in(x14, x15) -> f1830_in(x15, x14) :|: x14 > 0 f1916_in(x23, x24, x25) -> f1_in(x23, x24) :|: TRUE f1830_in(x28, x29) -> f1916_in(x29, x30, x28) :|: x30 = mod(x28, x29) f1_in(x36, x37) -> f6_in(x36, x37) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f6_in(x2:0, x3:0) -> f6_in(x3:0, x30:0) :|: x3:0 > 0 && x30:0 = mod(x2:0, x3:0) && TRUE ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f6_in(x2:0, x3:0) -> f6_in(x3:0, x30:0) :|: x3:0 > 0 && x30:0 = mod(x2:0, x3:0) && TRUE ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f6_in(x2:0, x3:0) -> f6_in(x3:0, x30:0) :|: x3:0 > 0 && x30:0 = mod(x2:0, x3:0) && TRUE No arcs! This digraph is fully evaluated! ---------------------------------------- (10) TRUE