/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 desc(g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 24 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 18 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 25 ms] (10) IRSwT (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IRSwT (13) TempFilterProof [SOUND, 36 ms] (14) IntTRS (15) RankingReductionPairProof [EQUIVALENT, 20 ms] (16) YES ---------------------------------------- (0) Obligation: Clauses: desc(X) :- =<(X, 0). desc(X) :- ','(>=(X, 0), desc(-(X, 1))). Query: desc(g) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 1, "program": { "directives": [], "clauses": [ [ "(desc X)", "(=< X (0))" ], [ "(desc X)", "(',' (>= X (0)) (desc (- X (1))))" ] ] }, "graph": { "nodes": { "13": { "goal": [{ "clause": 0, "scope": 1, "term": "(desc T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "14": { "goal": [{ "clause": 1, "scope": 1, "term": "(desc T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "15": { "goal": [{ "clause": -1, "scope": -1, "term": "(=< T6 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T6"], "free": [], "exprvars": [] } }, "16": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(desc T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "530": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T6", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": "<=" }] }, "ground": ["T6"], "free": [], "exprvars": ["T6"] } }, "585": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T6", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": "<=" }] }, "ground": [], "free": [], "exprvars": ["T6"] } }, "1434": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": ">" }] }, "ground": ["T9"], "free": [], "exprvars": ["T9"] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(desc T1)" }, { "clause": 1, "scope": 1, "term": "(desc T1)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "576": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "name": "T6", "type": "PlainIntegerVariable" }, "type": "PlainIntegerRelation", "rhs": { "type": "PlainIntegerConstant", "value": "0" }, "operation": ">" }] }, "ground": ["T6"], "free": [], "exprvars": ["T6"] } }, "675": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "1433": { "goal": [{ "clause": -1, "scope": -1, "term": "(desc (- T9 (1)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [{ "lhs": { "type": "PlainIntegerConstant", "value": "0" }, "type": "PlainIntegerRelation", "rhs": { "name": "T9", "type": "PlainIntegerVariable" }, "operation": "<=" }] }, "ground": ["T9"], "free": [], "exprvars": ["T9"] } }, "667": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (>= T9 (0)) (desc (- T9 (1))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T9"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 4, "label": "CASE" }, { "from": 4, "to": 13, "label": "PARALLEL" }, { "from": 4, "to": 14, "label": "PARALLEL" }, { "from": 13, "to": 15, "label": "ONLY EVAL with clause\ndesc(X5) :- =<(X5, 0).\nand substitutionT1 -> T6,\nX5 -> T6" }, { "from": 14, "to": 667, "label": "ONLY EVAL with clause\ndesc(X8) :- ','(>=(X8, 0), desc(-(X8, 1))).\nand substitutionT1 -> T9,\nX8 -> T9" }, { "from": 15, "to": 16, "label": "IS ERROR" }, { "from": 15, "to": 530, "label": "ARITHCOMP SUCCESS" }, { "from": 15, "to": 576, "label": "ARITHCOMP FAIL" }, { "from": 530, "to": 585, "label": "SUCCESS" }, { "from": 667, "to": 675, "label": "IS ERROR" }, { "from": 667, "to": 1433, "label": "ARITHCOMP SUCCESS" }, { "from": 667, "to": 1434, "label": "ARITHCOMP FAIL" }, { "from": 1433, "to": 1, "label": "INSTANCE with matching:\nT1 -> -(T9, 1)" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f4_out(T1) -> f1_out(T1) :|: TRUE f1_in(x) -> f4_in(x) :|: TRUE f667_in(T9) -> f675_in :|: TRUE f1433_out(x1) -> f667_out(x1) :|: x1 >= 0 f667_in(x2) -> f1434_in(x2) :|: x2 < 0 f675_out -> f667_out(x3) :|: TRUE f1434_out(x4) -> f667_out(x4) :|: x4 < 0 f667_in(x5) -> f1433_in(x5) :|: x5 >= 0 f14_in(x6) -> f667_in(x6) :|: TRUE f667_out(x7) -> f14_out(x7) :|: TRUE f4_in(x8) -> f14_in(x8) :|: TRUE f4_in(x9) -> f13_in(x9) :|: TRUE f13_out(x10) -> f4_out(x10) :|: TRUE f14_out(x11) -> f4_out(x11) :|: TRUE f1_out(x12 - 1) -> f1433_out(x12) :|: TRUE f1433_in(x13) -> f1_in(x13 - 1) :|: TRUE Start term: f1_in(T1) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f1_in(x) -> f4_in(x) :|: TRUE f667_in(x5) -> f1433_in(x5) :|: x5 >= 0 f14_in(x6) -> f667_in(x6) :|: TRUE f4_in(x8) -> f14_in(x8) :|: TRUE f1433_in(x13) -> f1_in(x13 - 1) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f1_in(x) -> f4_in(x) :|: TRUE f667_in(x5) -> f1433_in(x5) :|: x5 >= 0 f14_in(x6) -> f667_in(x6) :|: TRUE f4_in(x8) -> f14_in(x8) :|: TRUE f1433_in(x13) -> f1_in(x13 - 1) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f1_in(x:0) -> f1_in(x:0 - 1) :|: x:0 > -1 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f1_in(x:0) -> f1_in(arith) :|: x:0 > -1 && arith = x:0 - 1 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f1_in(x:0) -> f1_in(arith) :|: x:0 > -1 && arith = x:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f1_in(x:0) -> f1_in(arith) :|: x:0 > -1 && arith = x:0 - 1 Arcs: (1) -> (1) This digraph is fully evaluated! ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f1_in(x:0:0) -> f1_in(x:0:0 - 1) :|: x:0:0 > -1 ---------------------------------------- (13) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f1_in(INTEGER) Replaced non-predefined constructor symbols by 0. ---------------------------------------- (14) Obligation: Rules: f1_in(x:0:0) -> f1_in(c) :|: c = x:0:0 - 1 && x:0:0 > -1 ---------------------------------------- (15) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f1_in ] = f1_in_1 The following rules are decreasing: f1_in(x:0:0) -> f1_in(c) :|: c = x:0:0 - 1 && x:0:0 > -1 The following rules are bounded: f1_in(x:0:0) -> f1_in(c) :|: c = x:0:0 - 1 && x:0:0 > -1 ---------------------------------------- (16) YES