YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern goal() w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 34 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) TRUE ---------------------------------------- (0) Obligation: Clauses: even(s(s(X))) :- even(X). even(0). lte(s(X), s(Y)) :- lte(X, Y). lte(0, Y). goal :- ','(lte(X, s(s(s(s(0))))), even(X)). Query: goal() ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 2, "program": { "directives": [], "clauses": [ [ "(even (s (s X)))", "(even X)" ], [ "(even (0))", null ], [ "(lte (s X) (s Y))", "(lte X Y)" ], [ "(lte (0) Y)", null ], [ "(goal)", "(',' (lte X (s (s (s (s (0)))))) (even X))" ] ] }, "graph": { "nodes": { "44": { "goal": [ { "clause": 2, "scope": 4, "term": "(lte X56 (s (s (0))))" }, { "clause": 3, "scope": 4, "term": "(lte X56 (s (s (0))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X56"], "exprvars": [] } }, "23": { "goal": [{ "clause": 2, "scope": 2, "term": "(lte X5 (s (s (s (s (0))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X5"], "exprvars": [] } }, "45": { "goal": [{ "clause": 2, "scope": 4, "term": "(lte X56 (s (s (0))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X56"], "exprvars": [] } }, "46": { "goal": [{ "clause": 3, "scope": 4, "term": "(lte X56 (s (s (0))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X56"], "exprvars": [] } }, "25": { "goal": [{ "clause": 3, "scope": 2, "term": "(lte X5 (s (s (s (s (0))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X5"], "exprvars": [] } }, "28": { "goal": [{ "clause": -1, "scope": -1, "term": "(lte X32 (s (s (s (0)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X32"], "exprvars": [] } }, "29": { "goal": [ { "clause": 2, "scope": 3, "term": "(lte X32 (s (s (s (0)))))" }, { "clause": 3, "scope": 3, "term": "(lte X32 (s (s (s (0)))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X32"], "exprvars": [] } }, "type": "Nodes", "230": { "goal": [{ "clause": 1, "scope": 7, "term": "(even T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "231": { "goal": [{ "clause": -1, "scope": -1, "term": "(even T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [], "exprvars": [] } }, "232": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "134": { "goal": [{ "clause": -1, "scope": -1, "term": "(lte X104 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X104"], "exprvars": [] } }, "233": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "234": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "235": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "216": { "goal": [ { "clause": 2, "scope": 6, "term": "(lte X104 (0))" }, { "clause": 3, "scope": 6, "term": "(lte X104 (0))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X104"], "exprvars": [] } }, "217": { "goal": [{ "clause": 3, "scope": 6, "term": "(lte X104 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X104"], "exprvars": [] } }, "218": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "219": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "31": { "goal": [{ "clause": 2, "scope": 3, "term": "(lte X32 (s (s (s (0)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X32"], "exprvars": [] } }, "32": { "goal": [{ "clause": 3, "scope": 3, "term": "(lte X32 (s (s (s (0)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X32"], "exprvars": [] } }, "57": { "goal": [{ "clause": -1, "scope": -1, "term": "(lte X80 (s (0)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X80"], "exprvars": [] } }, "36": { "goal": [{ "clause": -1, "scope": -1, "term": "(lte X56 (s (s (0))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X56"], "exprvars": [] } }, "58": { "goal": [ { "clause": 2, "scope": 5, "term": "(lte X80 (s (0)))" }, { "clause": 3, "scope": 5, "term": "(lte X80 (s (0)))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X80"], "exprvars": [] } }, "15": { "goal": [{ "clause": -1, "scope": -1, "term": "(lte X5 (s (s (s (s (0))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X5"], "exprvars": [] } }, "59": { "goal": [{ "clause": 2, "scope": 5, "term": "(lte X80 (s (0)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X80"], "exprvars": [] } }, "16": { "goal": [{ "clause": -1, "scope": -1, "term": "(even T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "220": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "221": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(goal)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "222": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "223": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "224": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "5": { "goal": [{ "clause": 4, "scope": 1, "term": "(goal)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "225": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "226": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "227": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "228": { "goal": [ { "clause": 0, "scope": 7, "term": "(even T1)" }, { "clause": 1, "scope": 7, "term": "(even T1)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "9": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (lte X5 (s (s (s (s (0)))))) (even X5))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X5"], "exprvars": [] } }, "229": { "goal": [{ "clause": 0, "scope": 7, "term": "(even T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "60": { "goal": [{ "clause": 3, "scope": 5, "term": "(lte X80 (s (0)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X80"], "exprvars": [] } }, "21": { "goal": [ { "clause": 2, "scope": 2, "term": "(lte X5 (s (s (s (s (0))))))" }, { "clause": 3, "scope": 2, "term": "(lte X5 (s (s (s (s (0))))))" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X5"], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 5, "label": "CASE" }, { "from": 5, "to": 9, "label": "ONLY EVAL with clause\ngoal :- ','(lte(X5, s(s(s(s(0))))), even(X5)).\nand substitution" }, { "from": 9, "to": 15, "label": "SPLIT 1" }, { "from": 9, "to": 16, "label": "SPLIT 2\nnew knowledge:\nT1 is ground\nreplacements:X5 -> T1" }, { "from": 15, "to": 21, "label": "CASE" }, { "from": 16, "to": 228, "label": "CASE" }, { "from": 21, "to": 23, "label": "PARALLEL" }, { "from": 21, "to": 25, "label": "PARALLEL" }, { "from": 23, "to": 28, "label": "ONLY EVAL with clause\nlte(s(X30), s(X31)) :- lte(X30, X31).\nand substitutionX30 -> X32,\nX5 -> s(X32),\nX31 -> s(s(s(0)))" }, { "from": 25, "to": 226, "label": "ONLY EVAL with clause\nlte(0, X125).\nand substitutionX5 -> 0,\nX125 -> s(s(s(s(0))))" }, { "from": 28, "to": 29, "label": "CASE" }, { "from": 29, "to": 31, "label": "PARALLEL" }, { "from": 29, "to": 32, "label": "PARALLEL" }, { "from": 31, "to": 36, "label": "ONLY EVAL with clause\nlte(s(X54), s(X55)) :- lte(X54, X55).\nand substitutionX54 -> X56,\nX32 -> s(X56),\nX55 -> s(s(0))" }, { "from": 32, "to": 224, "label": "ONLY EVAL with clause\nlte(0, X122).\nand substitutionX32 -> 0,\nX122 -> s(s(s(0)))" }, { "from": 36, "to": 44, "label": "CASE" }, { "from": 44, "to": 45, "label": "PARALLEL" }, { "from": 44, "to": 46, "label": "PARALLEL" }, { "from": 45, "to": 57, "label": "ONLY EVAL with clause\nlte(s(X78), s(X79)) :- lte(X78, X79).\nand substitutionX78 -> X80,\nX56 -> s(X80),\nX79 -> s(0)" }, { "from": 46, "to": 222, "label": "ONLY EVAL with clause\nlte(0, X119).\nand substitutionX56 -> 0,\nX119 -> s(s(0))" }, { "from": 57, "to": 58, "label": "CASE" }, { "from": 58, "to": 59, "label": "PARALLEL" }, { "from": 58, "to": 60, "label": "PARALLEL" }, { "from": 59, "to": 134, "label": "ONLY EVAL with clause\nlte(s(X102), s(X103)) :- lte(X102, X103).\nand substitutionX102 -> X104,\nX80 -> s(X104),\nX103 -> 0" }, { "from": 60, "to": 220, "label": "ONLY EVAL with clause\nlte(0, X116).\nand substitutionX80 -> 0,\nX116 -> s(0)" }, { "from": 134, "to": 216, "label": "CASE" }, { "from": 216, "to": 217, "label": "BACKTRACK\nfor clause: lte(s(X), s(Y)) :- lte(X, Y)because of non-unification" }, { "from": 217, "to": 218, "label": "ONLY EVAL with clause\nlte(0, X113).\nand substitutionX104 -> 0,\nX113 -> 0" }, { "from": 218, "to": 219, "label": "SUCCESS" }, { "from": 220, "to": 221, "label": "SUCCESS" }, { "from": 222, "to": 223, "label": "SUCCESS" }, { "from": 224, "to": 225, "label": "SUCCESS" }, { "from": 226, "to": 227, "label": "SUCCESS" }, { "from": 228, "to": 229, "label": "PARALLEL" }, { "from": 228, "to": 230, "label": "PARALLEL" }, { "from": 229, "to": 231, "label": "EVAL with clause\neven(s(s(X131))) :- even(X131).\nand substitutionX131 -> T7,\nT1 -> s(s(T7))" }, { "from": 229, "to": 232, "label": "EVAL-BACKTRACK" }, { "from": 230, "to": 233, "label": "EVAL with clause\neven(0).\nand substitutionT1 -> 0" }, { "from": 230, "to": 234, "label": "EVAL-BACKTRACK" }, { "from": 231, "to": 16, "label": "INSTANCE with matching:\nT1 -> T7" }, { "from": 233, "to": 235, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f16_in(T1) -> f228_in(T1) :|: TRUE f228_out(x) -> f16_out(x) :|: TRUE f231_out(T7) -> f229_out(s(s(T7))) :|: TRUE f229_in(s(s(x1))) -> f231_in(x1) :|: TRUE f229_in(x2) -> f232_in :|: TRUE f232_out -> f229_out(x3) :|: TRUE f228_in(x4) -> f230_in(x4) :|: TRUE f229_out(x5) -> f228_out(x5) :|: TRUE f228_in(x6) -> f229_in(x6) :|: TRUE f230_out(x7) -> f228_out(x7) :|: TRUE f16_out(x8) -> f231_out(x8) :|: TRUE f231_in(x9) -> f16_in(x9) :|: TRUE f2_in -> f5_in :|: TRUE f5_out -> f2_out :|: TRUE f5_in -> f9_in :|: TRUE f9_out -> f5_out :|: TRUE f15_out -> f16_in(x10) :|: TRUE f9_in -> f15_in :|: TRUE f16_out(x11) -> f9_out :|: TRUE Start term: f2_in ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (4) TRUE