/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 between(g,g,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 9 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 0 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 27 ms] (10) IRSwT (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IRSwT (13) IntTRSUnneededArgumentFilterProof [EQUIVALENT, 0 ms] (14) IRSwT (15) TempFilterProof [SOUND, 39 ms] (16) IntTRS (17) RankingReductionPairProof [EQUIVALENT, 0 ms] (18) YES ---------------------------------------- (0) Obligation: Clauses: between(I, J, I) :- =<(I, J). between(I, J, K) :- ','(<(I, J), ','(is(I1, +(I, 1)), between(I1, J, K))). Query: between(g,g,g) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 1, "program": { "directives": [], "clauses": [ [ "(between I J I)", "(=< I J)" ], [ "(between I J K)", "(',' (< I J) (',' (is I1 (+ I (1))) (between I1 J K)))" ] ] }, "graph": { "nodes": { "12": { "goal": [{ "clause": -1, "scope": -1, "term": "(=< T12 T13)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T12", "T13" ], "free": [], "exprvars": [] } }, "16": { "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", "1613": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T12", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T13", "type": "PlainIntegerVariable" }, "operation": ">" }] }, "ground": [ "T13", "T12" ], "free": [], "exprvars": [ "T13", "T12" ] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(between T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "1612": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T12", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T13", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": [ "T13", "T12" ], "free": [], "exprvars": [ "T13", "T12" ] } }, "1688": { "goal": [{ "clause": -1, "scope": -1, "term": "(between T23 T21 T22)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [ { "lhs": { "name": "T23", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "arguments": [ { "name": "T20", "type": "PlainIntegerVariable" }, { "type": "PlainIntegerConstant", "value": "1" } ], "type": "PlainIntegerOperation", "operation": "+" }, "operation": "=" }, { "lhs": { "name": "T20", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T21", "type": "PlainIntegerVariable" }, "operation": "<" } ] }, "ground": [ "T20", "T23", "T22", "T21" ], "free": ["X21"], "exprvars": [ "T20", "T23", "T21" ] } }, "1686": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T20", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T21", "type": "PlainIntegerVariable" }, "operation": ">=" }] }, "ground": [ "T20", "T22", "T21" ], "free": ["X21"], "exprvars": [ "T20", "T21" ] } }, "1685": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (is X21 (+ T20 (1))) (between X21 T21 T22))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T20", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T21", "type": "PlainIntegerVariable" }, "operation": "<" }] }, "ground": [ "T20", "T22", "T21" ], "free": ["X21"], "exprvars": [ "T20", "T21" ] } }, "6": { "goal": [ { "clause": 0, "scope": 1, "term": "(between T1 T2 T3)" }, { "clause": 1, "scope": 1, "term": "(between T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "9": { "goal": [{ "clause": 0, "scope": 1, "term": "(between T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "1616": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1615": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (< T20 T21) (',' (is X21 (+ T20 (1))) (between X21 T21 T22)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21", "T22" ], "free": ["X21"], "exprvars": [] } }, "10": { "goal": [{ "clause": 1, "scope": 1, "term": "(between T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T1", "T2", "T3" ], "free": [], "exprvars": [] } }, "1614": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T12", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "name": "T13", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": [], "free": [], "exprvars": [ "T13", "T12" ] } } }, "edges": [ { "from": 1, "to": 6, "label": "CASE" }, { "from": 6, "to": 9, "label": "PARALLEL" }, { "from": 6, "to": 10, "label": "PARALLEL" }, { "from": 9, "to": 12, "label": "EVAL with clause\nbetween(X9, X10, X9) :- =<(X9, X10).\nand substitutionT1 -> T12,\nX9 -> T12,\nT2 -> T13,\nX10 -> T13,\nT3 -> T12" }, { "from": 9, "to": 16, "label": "EVAL-BACKTRACK" }, { "from": 10, "to": 1615, "label": "ONLY EVAL with clause\nbetween(X18, X19, X20) :- ','(<(X18, X19), ','(is(X21, +(X18, 1)), between(X21, X19, X20))).\nand substitutionT1 -> T20,\nX18 -> T20,\nT2 -> T21,\nX19 -> T21,\nT3 -> T22,\nX20 -> T22" }, { "from": 12, "to": 19, "label": "IS ERROR" }, { "from": 12, "to": 1612, "label": "ARITHCOMP SUCCESS" }, { "from": 12, "to": 1613, "label": "ARITHCOMP FAIL" }, { "from": 1612, "to": 1614, "label": "SUCCESS" }, { "from": 1615, "to": 1616, "label": "IS ERROR" }, { "from": 1615, "to": 1685, "label": "ARITHCOMP SUCCESS" }, { "from": 1615, "to": 1686, "label": "ARITHCOMP FAIL" }, { "from": 1685, "to": 1688, "label": "\nX21 -> T23" }, { "from": 1688, "to": 1, "label": "INSTANCE with matching:\nT1 -> T23\nT2 -> T21\nT3 -> T22" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f10_out(T1, T2, T3) -> f6_out(T1, T2, T3) :|: TRUE f9_out(x, x1, x2) -> f6_out(x, x1, x2) :|: TRUE f6_in(x3, x4, x5) -> f9_in(x3, x4, x5) :|: TRUE f6_in(x6, x7, x8) -> f10_in(x6, x7, x8) :|: TRUE f1688_out(T23, T21, T22, T20) -> f1685_out(T20, T21, T22) :|: TRUE f1685_in(x9, x10, x11) -> f1688_in(x12, x10, x11, x9) :|: x12 = x9 + 1 f1_in(x13, x14, x15) -> f6_in(x13, x14, x15) :|: TRUE f6_out(x16, x17, x18) -> f1_out(x16, x17, x18) :|: TRUE f10_in(x19, x20, x21) -> f1615_in(x19, x20, x21) :|: TRUE f1615_out(x22, x23, x24) -> f10_out(x22, x23, x24) :|: TRUE f1615_in(x25, x26, x27) -> f1616_in :|: TRUE f1686_out(x28, x29, x30) -> f1615_out(x28, x30, x29) :|: x28 >= x30 f1615_in(x31, x32, x33) -> f1685_in(x31, x32, x33) :|: x31 < x32 f1615_in(x34, x35, x36) -> f1686_in(x34, x36, x35) :|: x34 >= x35 f1616_out -> f1615_out(x37, x38, x39) :|: TRUE f1685_out(x40, x41, x42) -> f1615_out(x40, x41, x42) :|: x40 < x41 f1_out(x43, x44, x45) -> f1688_out(x43, x44, x45, x46) :|: TRUE f1688_in(x47, x48, x49, x50) -> f1_in(x47, x48, x49) :|: TRUE Start term: f1_in(T1, T2, T3) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f6_in(x6, x7, x8) -> f10_in(x6, x7, x8) :|: TRUE f1685_in(x9, x10, x11) -> f1688_in(x12, x10, x11, x9) :|: x12 = x9 + 1 f1_in(x13, x14, x15) -> f6_in(x13, x14, x15) :|: TRUE f10_in(x19, x20, x21) -> f1615_in(x19, x20, x21) :|: TRUE f1615_in(x31, x32, x33) -> f1685_in(x31, x32, x33) :|: x31 < x32 f1688_in(x47, x48, x49, x50) -> f1_in(x47, x48, x49) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f6_in(x6, x7, x8) -> f10_in(x6, x7, x8) :|: TRUE f1685_in(x9, x10, x11) -> f1688_in(x12, x10, x11, x9) :|: x12 = x9 + 1 f1_in(x13, x14, x15) -> f6_in(x13, x14, x15) :|: TRUE f10_in(x19, x20, x21) -> f1615_in(x19, x20, x21) :|: TRUE f1615_in(x31, x32, x33) -> f1685_in(x31, x32, x33) :|: x31 < x32 f1688_in(x47, x48, x49, x50) -> f1_in(x47, x48, x49) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f1_in(x13:0, x14:0, x15:0) -> f1_in(x13:0 + 1, x14:0, x15:0) :|: x14:0 > x13:0 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f1_in(x13:0, x14:0, x15:0) -> f1_in(arith, x14:0, x15:0) :|: x14:0 > x13:0 && arith = x13:0 + 1 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1_in(x13:0, x14:0, x15:0) -> f1_in(arith, x14:0, x15:0) :|: x14:0 > x13:0 && arith = x13:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f1_in(x13:0, x14:0, x15:0) -> f1_in(arith, x14:0, x15:0) :|: x14:0 > x13:0 && arith = x13:0 + 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f1_in(x13:0:0, x14:0:0, x15:0:0) -> f1_in(x13:0:0 + 1, x14:0:0, x15:0:0) :|: x14:0:0 > x13:0:0 ---------------------------------------- (13) IntTRSUnneededArgumentFilterProof (EQUIVALENT) Some arguments are removed because they cannot influence termination. We removed arguments according to the following replacements: f1_in(x1, x2, x3) -> f1_in(x1, x2) ---------------------------------------- (14) Obligation: Rules: f1_in(x13:0:0, x14:0:0) -> f1_in(x13:0:0 + 1, x14:0:0) :|: x14:0:0 > x13:0:0 ---------------------------------------- (15) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1_in(INTEGER, INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (16) Obligation: Rules: f1_in(x13:0:0, x14:0:0) -> f1_in(c, x14:0:0) :|: c = x13:0:0 + 1 && x14:0:0 > x13:0:0 ---------------------------------------- (17) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f1_in ] = f1_in_2 + -1*f1_in_1 The following rules are decreasing: f1_in(x13:0:0, x14:0:0) -> f1_in(c, x14:0:0) :|: c = x13:0:0 + 1 && x14:0:0 > x13:0:0 The following rules are bounded: f1_in(x13:0:0, x14:0:0) -> f1_in(c, x14:0:0) :|: c = x13:0:0 + 1 && x14:0:0 > x13:0:0 ---------------------------------------- (18) YES