/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 gcd(g,g,a) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 73 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 23 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 3 ms] (10) TRUE ---------------------------------------- (0) Obligation: Clauses: gcd(X, 0, X) :- >(X, 0). gcd(X, Y, G) :- ','(>(Y, 0), ','(is(Z, mod(X, Y)), gcd(Y, Z, G))). Query: gcd(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": [ [ "(gcd X (0) X)", "(> X (0))" ], [ "(gcd X Y G)", "(',' (> Y (0)) (',' (is Z (mod X Y)) (gcd Y Z G)))" ] ] }, "graph": { "nodes": { "17": { "goal": [{ "clause": -1, "scope": -1, "term": "(> T8 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T8"], "free": [], "exprvars": [] } }, "18": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "19": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "1514": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T8", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": ["T8"], "free": [], "exprvars": ["T8"] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(gcd T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "1513": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T8", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": ["T8"], "free": [], "exprvars": ["T8"] } }, "1863": { "goal": [{ "clause": -1, "scope": -1, "term": "(gcd 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" ] } }, "5": { "goal": [ { "clause": 0, "scope": 1, "term": "(gcd T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(gcd T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "1861": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1860": { "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"] } }, "7": { "goal": [{ "clause": 0, "scope": 1, "term": "(gcd T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "8": { "goal": [{ "clause": 1, "scope": 1, "term": "(gcd T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "1859": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X16 (mod T16 T17)) (gcd 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"] } }, "1517": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1516": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T17 (0)) (',' (is X16 (mod T16 T17)) (gcd T17 X16 T19)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T16", "T17" ], "free": ["X16"], "exprvars": [] } }, "1515": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T8", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [], "free": [], "exprvars": ["T8"] } } }, "edges": [ { "from": 1, "to": 5, "label": "CASE" }, { "from": 5, "to": 7, "label": "PARALLEL" }, { "from": 5, "to": 8, "label": "PARALLEL" }, { "from": 7, "to": 17, "label": "EVAL with clause\ngcd(X5, 0, X5) :- >(X5, 0).\nand substitutionT1 -> T8,\nX5 -> T8,\nT2 -> 0,\nT3 -> T8" }, { "from": 7, "to": 18, "label": "EVAL-BACKTRACK" }, { "from": 8, "to": 1516, "label": "ONLY EVAL with clause\ngcd(X13, X14, X15) :- ','(>(X14, 0), ','(is(X16, mod(X13, X14)), gcd(X14, X16, X15))).\nand substitutionT1 -> T16,\nX13 -> T16,\nT2 -> T17,\nX14 -> T17,\nT3 -> T19,\nX15 -> T19,\nT18 -> T19" }, { "from": 17, "to": 19, "label": "IS ERROR" }, { "from": 17, "to": 1513, "label": "ARITHCOMP SUCCESS" }, { "from": 17, "to": 1514, "label": "ARITHCOMP FAIL" }, { "from": 1513, "to": 1515, "label": "SUCCESS" }, { "from": 1516, "to": 1517, "label": "IS ERROR" }, { "from": 1516, "to": 1859, "label": "ARITHCOMP SUCCESS" }, { "from": 1516, "to": 1860, "label": "ARITHCOMP FAIL" }, { "from": 1859, "to": 1861, "label": "IS ERROR" }, { "from": 1859, "to": 1863, "label": "\nX16 -> T20" }, { "from": 1863, "to": 1, "label": "INSTANCE with matching:\nT1 -> T17\nT2 -> T20\nT3 -> T19" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f8_in(T16, T17) -> f1516_in(T17, T16) :|: TRUE f1516_out(x, x1) -> f8_out(x1, x) :|: TRUE f5_in(T1, T2) -> f7_in(T1, T2) :|: TRUE f5_in(x2, x3) -> f8_in(x2, x3) :|: TRUE f8_out(x4, x5) -> f5_out(x4, x5) :|: TRUE f7_out(x6, x7) -> f5_out(x6, x7) :|: TRUE f1859_out(x8, x9) -> f1516_out(x9, x8) :|: x9 > 0 f1516_in(x10, x11) -> f1860_in(x10, x11) :|: x10 <= 0 f1517_out -> f1516_out(x12, x13) :|: TRUE f1516_in(x14, x15) -> f1859_in(x15, x14) :|: x14 > 0 f1860_out(x16, x17) -> f1516_out(x16, x17) :|: x16 <= 0 f1516_in(x18, x19) -> f1517_in :|: TRUE f1859_in(x20, x21) -> f1863_in(x21, x22, x20) :|: x22 = mod(x20, x21) f1863_out(x23, x24, x25) -> f1859_out(x25, x23) :|: TRUE f1859_in(x26, x27) -> f1861_in :|: TRUE f1861_out -> f1859_out(x28, x29) :|: TRUE f1_out(x30, x31) -> f1863_out(x30, x31, x32) :|: TRUE f1863_in(x33, x34, x35) -> f1_in(x33, x34) :|: TRUE f5_out(x36, x37) -> f1_out(x36, x37) :|: TRUE f1_in(x38, x39) -> f5_in(x38, x39) :|: TRUE Start term: f1_in(T1, T2) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f8_in(T16, T17) -> f1516_in(T17, T16) :|: TRUE f5_in(x2, x3) -> f8_in(x2, x3) :|: TRUE f1516_in(x14, x15) -> f1859_in(x15, x14) :|: x14 > 0 f1859_in(x20, x21) -> f1863_in(x21, x22, x20) :|: x22 = mod(x20, x21) f1863_in(x33, x34, x35) -> f1_in(x33, x34) :|: TRUE f1_in(x38, x39) -> f5_in(x38, x39) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f8_in(T16, T17) -> f1516_in(T17, T16) :|: TRUE f5_in(x2, x3) -> f8_in(x2, x3) :|: TRUE f1516_in(x14, x15) -> f1859_in(x15, x14) :|: x14 > 0 f1859_in(x20, x21) -> f1863_in(x21, x22, x20) :|: x22 = mod(x20, x21) f1863_in(x33, x34, x35) -> f1_in(x33, x34) :|: TRUE f1_in(x38, x39) -> f5_in(x38, x39) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f5_in(x2:0, x3:0) -> f5_in(x3:0, x22:0) :|: x3:0 > 0 && TRUE && x22:0 = mod(x2:0, x3:0) ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f5_in(x2:0, x3:0) -> f5_in(x3:0, x22:0) :|: x3:0 > 0 && TRUE && x22:0 = mod(x2:0, x3:0) ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f5_in(x2:0, x3:0) -> f5_in(x3:0, x22:0) :|: x3:0 > 0 && TRUE && x22:0 = mod(x2:0, x3:0) No arcs! This digraph is fully evaluated! ---------------------------------------- (10) TRUE