/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) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 22 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 1 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 31 ms] (10) TRUE ---------------------------------------- (0) Obligation: Clauses: test_fun(X, Y) :- loop(X, Y). loop(X, Y) :- ','(>(X, Y), ','(is(Tmp, X), ','(is(X1, Y), ','(is(Y1, Tmp), loop(X1, Y1))))). loop(X, Y) :- =<(X, Y). Query: test_fun(g,g) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 3, "program": { "directives": [], "clauses": [ [ "(test_fun X Y)", "(loop X Y)" ], [ "(loop X Y)", "(',' (> X Y) (',' (is Tmp X) (',' (is X1 Y) (',' (is Y1 Tmp) (loop X1 Y1)))))" ], [ "(loop X Y)", "(=< X Y)" ] ] }, "graph": { "nodes": { "23": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (> T21 T22) (',' (is X34 T21) (',' (is X35 T22) (',' (is X36 X34) (loop X35 X36)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T21", "T22" ], "free": [ "X34", "X35", "X36" ], "exprvars": [] } }, "13": { "goal": [{ "clause": 1, "scope": 2, "term": "(loop T9 T10)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10" ], "free": [], "exprvars": [] } }, "24": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "14": { "goal": [{ "clause": 2, "scope": 2, "term": "(loop T9 T10)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10" ], "free": [], "exprvars": [] } }, "280": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T22", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T21", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T22", "T21" ], "free": [ "X34", "X35", "X36" ], "exprvars": [ "T22", "T21" ] } }, "281": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X35 T22) (',' (is X36 T23) (loop X35 X36)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T23", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T21", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "name": "T22", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T21", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T23", "T22", "T21" ], "free": [ "X34", "X35", "X36" ], "exprvars": [ "T23", "T22", "T21" ] } }, "type": "Nodes", "282": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X36 T23) (loop T24 X36))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T23", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T21", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "name": "T24", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T22", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "name": "T22", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T21", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T24", "T23", "T22", "T21" ], "free": [ "X34", "X35", "X36" ], "exprvars": [ "T24", "T23", "T22", "T21" ] } }, "283": { "goal": [{ "clause": -1, "scope": -1, "term": "(loop T24 T25)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T23", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T21", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "name": "T24", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T22", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "name": "T25", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T23", "type": "PlainIntegerVariable" }, "operation": "=" }, { "lhs": { "name": "T22", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T21", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T25", "T24", "T23", "T22", "T21" ], "free": [ "X34", "X35", "X36" ], "exprvars": [ "T25", "T24", "T23", "T22", "T21" ] } }, "286": { "goal": [{ "clause": -1, "scope": -1, "term": "(=< T32 T33)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T32", "T33" ], "free": [], "exprvars": [] } }, "287": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "3": { "goal": [{ "clause": -1, "scope": -1, "term": "(test_fun T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "1664": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T32", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T33", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": [], "free": [], "exprvars": [ "T33", "T32" ] } }, "5": { "goal": [{ "clause": 0, "scope": 1, "term": "(test_fun T1 T2)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2" ], "free": [], "exprvars": [] } }, "269": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X34 T21) (',' (is X35 T22) (',' (is X36 X34) (loop X35 X36))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T22", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T21", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T22", "T21" ], "free": [ "X34", "X35", "X36" ], "exprvars": [ "T22", "T21" ] } }, "7": { "goal": [{ "clause": -1, "scope": -1, "term": "(loop T9 T10)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10" ], "free": [], "exprvars": [] } }, "1661": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T32", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T33", "type": "PlainIntegerVariable" }, "operation": ">" }] }, "ground": [ "T33", "T32" ], "free": [], "exprvars": [ "T33", "T32" ] } }, "10": { "goal": [ { "clause": 1, "scope": 2, "term": "(loop T9 T10)" }, { "clause": 2, "scope": 2, "term": "(loop T9 T10)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T9", "T10" ], "free": [], "exprvars": [] } }, "1658": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T32", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T33", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": [ "T33", "T32" ], "free": [], "exprvars": [ "T33", "T32" ] } } }, "edges": [ { "from": 3, "to": 5, "label": "CASE" }, { "from": 5, "to": 7, "label": "ONLY EVAL with clause\ntest_fun(X11, X12) :- loop(X11, X12).\nand substitutionT1 -> T9,\nX11 -> T9,\nT2 -> T10,\nX12 -> T10" }, { "from": 7, "to": 10, "label": "CASE" }, { "from": 10, "to": 13, "label": "PARALLEL" }, { "from": 10, "to": 14, "label": "PARALLEL" }, { "from": 13, "to": 23, "label": "ONLY EVAL with clause\nloop(X32, X33) :- ','(>(X32, X33), ','(is(X34, X32), ','(is(X35, X33), ','(is(X36, X34), loop(X35, X36))))).\nand substitutionT9 -> T21,\nX32 -> T21,\nT10 -> T22,\nX33 -> T22" }, { "from": 14, "to": 286, "label": "ONLY EVAL with clause\nloop(X46, X47) :- =<(X46, X47).\nand substitutionT9 -> T32,\nX46 -> T32,\nT10 -> T33,\nX47 -> T33" }, { "from": 23, "to": 24, "label": "IS ERROR" }, { "from": 23, "to": 269, "label": "ARITHCOMP SUCCESS" }, { "from": 23, "to": 280, "label": "ARITHCOMP FAIL" }, { "from": 269, "to": 281, "label": "\nX34 -> T23" }, { "from": 281, "to": 282, "label": "\nX35 -> T24" }, { "from": 282, "to": 283, "label": "\nX36 -> T25" }, { "from": 283, "to": 7, "label": "INSTANCE with matching:\nT9 -> T24\nT10 -> T25" }, { "from": 286, "to": 287, "label": "IS ERROR" }, { "from": 286, "to": 1658, "label": "ARITHCOMP SUCCESS" }, { "from": 286, "to": 1661, "label": "ARITHCOMP FAIL" }, { "from": 1658, "to": 1664, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f14_out(T9, T10) -> f10_out(T9, T10) :|: TRUE f10_in(x, x1) -> f14_in(x, x1) :|: TRUE f13_out(x2, x3) -> f10_out(x2, x3) :|: TRUE f10_in(x4, x5) -> f13_in(x4, x5) :|: TRUE f13_in(T21, T22) -> f23_in(T21, T22) :|: TRUE f23_out(x6, x7) -> f13_out(x6, x7) :|: TRUE f282_out(x8, x9, x10, x11) -> f281_out(x10, x8, x11) :|: TRUE f281_in(x12, x13, x14) -> f282_in(x13, x15, x12, x14) :|: x15 = x12 f280_out(x16, x17) -> f23_out(x17, x16) :|: x17 <= x16 f23_in(x18, x19) -> f269_in(x18, x19) :|: x18 > x19 f24_out -> f23_out(x20, x21) :|: TRUE f23_in(x22, x23) -> f280_in(x23, x22) :|: x22 <= x23 f23_in(x24, x25) -> f24_in :|: TRUE f269_out(x26, x27) -> f23_out(x26, x27) :|: x26 > x27 f7_out(x28, x29) -> f283_out(x28, x29, x30, x31, x32) :|: TRUE f283_in(x33, x34, x35, x36, x37) -> f7_in(x33, x34) :|: TRUE f7_in(x38, x39) -> f10_in(x38, x39) :|: TRUE f10_out(x40, x41) -> f7_out(x40, x41) :|: TRUE f269_in(x42, x43) -> f281_in(x43, x44, x42) :|: x44 = x42 f281_out(x45, x46, x47) -> f269_out(x47, x45) :|: TRUE f283_out(x48, x49, x50, x51, x52) -> f282_out(x50, x48, x51, x52) :|: TRUE f282_in(x53, x54, x55, x56) -> f283_in(x54, x57, x53, x55, x56) :|: x57 = x53 f3_in(T1, T2) -> f5_in(T1, T2) :|: TRUE f5_out(x58, x59) -> f3_out(x58, x59) :|: TRUE f5_in(x60, x61) -> f7_in(x60, x61) :|: TRUE f7_out(x62, x63) -> f5_out(x62, x63) :|: TRUE Start term: f3_in(T1, T2) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f10_in(x4, x5) -> f13_in(x4, x5) :|: TRUE f13_in(T21, T22) -> f23_in(T21, T22) :|: TRUE f281_in(x12, x13, x14) -> f282_in(x13, x15, x12, x14) :|: x15 = x12 f23_in(x18, x19) -> f269_in(x18, x19) :|: x18 > x19 f283_in(x33, x34, x35, x36, x37) -> f7_in(x33, x34) :|: TRUE f7_in(x38, x39) -> f10_in(x38, x39) :|: TRUE f269_in(x42, x43) -> f281_in(x43, x44, x42) :|: x44 = x42 f282_in(x53, x54, x55, x56) -> f283_in(x54, x57, x53, x55, x56) :|: x57 = x53 ---------------------------------------- (4) Obligation: Rules: f10_in(x4, x5) -> f13_in(x4, x5) :|: TRUE f13_in(T21, T22) -> f23_in(T21, T22) :|: TRUE f281_in(x12, x13, x14) -> f282_in(x13, x15, x12, x14) :|: x15 = x12 f23_in(x18, x19) -> f269_in(x18, x19) :|: x18 > x19 f283_in(x33, x34, x35, x36, x37) -> f7_in(x33, x34) :|: TRUE f7_in(x38, x39) -> f10_in(x38, x39) :|: TRUE f269_in(x42, x43) -> f281_in(x43, x44, x42) :|: x44 = x42 f282_in(x53, x54, x55, x56) -> f283_in(x54, x57, x53, x55, x56) :|: x57 = x53 ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f283_in(x33:0, x15:0, x35:0, x36:0, x37:0) -> f283_in(x15:0, x33:0, x33:0, x15:0, x33:0) :|: x33:0 > x15:0 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f283_in(x33:0, x15:0, x35:0, x36:0, x37:0) -> f283_in(x15:0, x33:0, x33:0, x15:0, x33:0) :|: x33:0 > x15:0 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f283_in(x33:0, x15:0, x35:0, x36:0, x37:0) -> f283_in(x15:0, x33:0, x33:0, x15:0, x33:0) :|: x33:0 > x15:0 No arcs! This digraph is fully evaluated! ---------------------------------------- (10) TRUE