/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 coprime(g,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 32 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 26 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 0 ms] (10) TRUE ---------------------------------------- (0) Obligation: Clauses: coprime(X, Y) :- gcd(X, Y, 1). gcd(X, 0, X) :- >(X, 0). gcd(X, Y, G) :- ','(>(Y, 0), ','(is(Z, mod(X, Y)), gcd(Y, Z, G))). Query: coprime(g,g) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(coprime X Y)", "(gcd X Y (1))" ], [ "(gcd X (0) X)", "(> X (0))" ], [ "(gcd X Y G)", "(',' (> Y (0)) (',' (is Z (mod X Y)) (gcd Y Z G)))" ] ] }, "graph": { "nodes": { "22": { "goal": [{ "clause": 2, "scope": 2, "term": "(gcd T8 T9 (1))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T8", "T9" ], "free": [], "exprvars": [] } }, "23": { "goal": [{ "clause": -1, "scope": -1, "term": "(> (1) (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "24": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2133": { "goal": [{ "clause": -1, "scope": -1, "term": "(gcd T21 T22 (1))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T22", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T20", "type": "PlainIntegerVariable" }, { "name": "T21", "type": "PlainIntegerVariable" } ], "type": "PlainIntegerOperation", "operation": "mod" }, "operation": "=" }, { "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T21", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T20", "T22", "T21" ], "free": ["X24"], "exprvars": [ "T20", "T22", "T21" ] } }, "type": "Nodes", "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(coprime T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "2126": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2125": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T21", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T20", "T21" ], "free": ["X24"], "exprvars": ["T21"] } }, "6": { "goal": [{ "clause": 0, "scope": 1, "term": "(coprime T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "2124": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X24 (mod T20 T21)) (gcd T21 X24 (1)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T21", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T20", "T21" ], "free": ["X24"], "exprvars": ["T21"] } }, "9": { "goal": [{ "clause": -1, "scope": -1, "term": "(gcd T8 T9 (1))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T8", "T9" ], "free": [], "exprvars": [] } }, "1937": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1936": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T21 (0)) (',' (is X24 (mod T20 T21)) (gcd T21 X24 (1))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21" ], "free": ["X24"], "exprvars": [] } }, "1935": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": "<" }] }, "ground": [], "free": [], "exprvars": [] } }, "20": { "goal": [ { "clause": 1, "scope": 2, "term": "(gcd T8 T9 (1))" }, { "clause": 2, "scope": 2, "term": "(gcd T8 T9 (1))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T8", "T9" ], "free": [], "exprvars": [] } }, "1934": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "1" }, "operation": "<" }] }, "ground": [], "free": [], "exprvars": [] } }, "21": { "goal": [{ "clause": 1, "scope": 2, "term": "(gcd T8 T9 (1))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T8", "T9" ], "free": [], "exprvars": [] } } }, "edges": [ { "from": 3, "to": 6, "label": "CASE" }, { "from": 6, "to": 9, "label": "ONLY EVAL with clause\ncoprime(X6, X7) :- gcd(X6, X7, 1).\nand substitutionT1 -> T8,\nX6 -> T8,\nT2 -> T9,\nX7 -> T9" }, { "from": 9, "to": 20, "label": "CASE" }, { "from": 20, "to": 21, "label": "PARALLEL" }, { "from": 20, "to": 22, "label": "PARALLEL" }, { "from": 21, "to": 23, "label": "EVAL with clause\ngcd(X13, 0, X13) :- >(X13, 0).\nand substitutionT8 -> 1,\nX13 -> 1,\nT9 -> 0,\nT15 -> 1" }, { "from": 21, "to": 24, "label": "EVAL-BACKTRACK" }, { "from": 22, "to": 1936, "label": "ONLY EVAL with clause\ngcd(X21, X22, X23) :- ','(>(X22, 0), ','(is(X24, mod(X21, X22)), gcd(X22, X24, X23))).\nand substitutionT8 -> T20,\nX21 -> T20,\nT9 -> T21,\nX22 -> T21,\nX23 -> 1" }, { "from": 23, "to": 1934, "label": "ARITHCOMP SUCCESS" }, { "from": 1934, "to": 1935, "label": "SUCCESS" }, { "from": 1936, "to": 1937, "label": "IS ERROR" }, { "from": 1936, "to": 2124, "label": "ARITHCOMP SUCCESS" }, { "from": 1936, "to": 2125, "label": "ARITHCOMP FAIL" }, { "from": 2124, "to": 2126, "label": "IS ERROR" }, { "from": 2124, "to": 2133, "label": "\nX24 -> T22" }, { "from": 2133, "to": 9, "label": "INSTANCE with matching:\nT8 -> T21\nT9 -> T22" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f20_out(T8, T9) -> f9_out(T8, T9) :|: TRUE f9_in(x, x1) -> f20_in(x, x1) :|: TRUE f22_in(T20, T21) -> f1936_in(T21, T20) :|: TRUE f1936_out(x2, x3) -> f22_out(x3, x2) :|: TRUE f2124_out(x4, x5) -> f1936_out(x5, x4) :|: x5 > 0 f1936_in(x6, x7) -> f2125_in(x7, x6) :|: x6 <= 0 f2125_out(x8, x9) -> f1936_out(x9, x8) :|: x9 <= 0 f1937_out -> f1936_out(x10, x11) :|: TRUE f1936_in(x12, x13) -> f2124_in(x13, x12) :|: x12 > 0 f1936_in(x14, x15) -> f1937_in :|: TRUE f21_out(x16, x17) -> f20_out(x16, x17) :|: TRUE f22_out(x18, x19) -> f20_out(x18, x19) :|: TRUE f20_in(x20, x21) -> f21_in(x20, x21) :|: TRUE f20_in(x22, x23) -> f22_in(x22, x23) :|: TRUE f2133_out(x24, x25, x26) -> f2124_out(x26, x24) :|: TRUE f2124_in(x27, x28) -> f2126_in :|: TRUE f2126_out -> f2124_out(x29, x30) :|: TRUE f2124_in(x31, x32) -> f2133_in(x32, x33, x31) :|: x33 = mod(x31, x32) f2133_in(x34, x35, x36) -> f9_in(x34, x35) :|: TRUE f9_out(x37, x38) -> f2133_out(x37, x38, x39) :|: TRUE f6_out(T1, T2) -> f3_out(T1, T2) :|: TRUE f3_in(x40, x41) -> f6_in(x40, x41) :|: TRUE f9_out(x42, x43) -> f6_out(x42, x43) :|: TRUE f6_in(x44, x45) -> f9_in(x44, x45) :|: TRUE Start term: f3_in(T1, T2) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f9_in(x, x1) -> f20_in(x, x1) :|: TRUE f22_in(T20, T21) -> f1936_in(T21, T20) :|: TRUE f1936_in(x12, x13) -> f2124_in(x13, x12) :|: x12 > 0 f20_in(x22, x23) -> f22_in(x22, x23) :|: TRUE f2124_in(x31, x32) -> f2133_in(x32, x33, x31) :|: x33 = mod(x31, x32) f2133_in(x34, x35, x36) -> f9_in(x34, x35) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f9_in(x, x1) -> f20_in(x, x1) :|: TRUE f22_in(T20, T21) -> f1936_in(T21, T20) :|: TRUE f1936_in(x12, x13) -> f2124_in(x13, x12) :|: x12 > 0 f20_in(x22, x23) -> f22_in(x22, x23) :|: TRUE f2124_in(x31, x32) -> f2133_in(x32, x33, x31) :|: x33 = mod(x31, x32) f2133_in(x34, x35, x36) -> f9_in(x34, x35) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f9_in(x:0, x1:0) -> f9_in(x1:0, x33:0) :|: x1:0 > 0 && TRUE && x33:0 = mod(x:0, x1:0) ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f9_in(x:0, x1:0) -> f9_in(x1:0, x33:0) :|: x1:0 > 0 && TRUE && x33:0 = mod(x:0, x1:0) ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f9_in(x:0, x1:0) -> f9_in(x1:0, x33:0) :|: x1:0 > 0 && TRUE && x33:0 = mod(x:0, x1:0) No arcs! This digraph is fully evaluated! ---------------------------------------- (10) TRUE