/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: 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, 38 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": 1, "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": { "192": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "171": { "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": [] } }, "193": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "172": { "goal": [{ "clause": 3, "scope": 6, "term": "(lte X104 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X104"], "exprvars": [] } }, "194": { "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": [] } }, "250": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "196": { "goal": [{ "clause": 0, "scope": 7, "term": "(even T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "131": { "goal": [{ "clause": -1, "scope": -1, "term": "(lte X32 (s (s (s (0)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X32"], "exprvars": [] } }, "175": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "197": { "goal": [{ "clause": 1, "scope": 7, "term": "(even T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "132": { "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": [] } }, "176": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "199": { "goal": [{ "clause": -1, "scope": -1, "term": "(even T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [], "exprvars": [] } }, "156": { "goal": [{ "clause": -1, "scope": -1, "term": "(lte X80 (s (0)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X80"], "exprvars": [] } }, "135": { "goal": [{ "clause": 2, "scope": 3, "term": "(lte X32 (s (s (s (0)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X32"], "exprvars": [] } }, "157": { "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": [] } }, "179": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "136": { "goal": [{ "clause": 3, "scope": 3, "term": "(lte X32 (s (s (s (0)))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X32"], "exprvars": [] } }, "158": { "goal": [{ "clause": 2, "scope": 5, "term": "(lte X80 (s (0)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X80"], "exprvars": [] } }, "159": { "goal": [{ "clause": 3, "scope": 5, "term": "(lte X80 (s (0)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X80"], "exprvars": [] } }, "139": { "goal": [{ "clause": -1, "scope": -1, "term": "(lte X56 (s (s (0))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X56"], "exprvars": [] } }, "119": { "goal": [{ "clause": 4, "scope": 1, "term": "(goal)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "181": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "140": { "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": [] } }, "184": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "185": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "120": { "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": [] } }, "121": { "goal": [{ "clause": -1, "scope": -1, "term": "(lte X5 (s (s (s (s (0))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X5"], "exprvars": [] } }, "143": { "goal": [{ "clause": 2, "scope": 4, "term": "(lte X56 (s (s (0))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X56"], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(goal)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "122": { "goal": [{ "clause": -1, "scope": -1, "term": "(even T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "144": { "goal": [{ "clause": 3, "scope": 4, "term": "(lte X56 (s (s (0))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X56"], "exprvars": [] } }, "188": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "123": { "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": [] } }, "189": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "200": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "169": { "goal": [{ "clause": -1, "scope": -1, "term": "(lte X104 (0))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X104"], "exprvars": [] } }, "246": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "126": { "goal": [{ "clause": 2, "scope": 2, "term": "(lte X5 (s (s (s (s (0))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X5"], "exprvars": [] } }, "127": { "goal": [{ "clause": 3, "scope": 2, "term": "(lte X5 (s (s (s (s (0))))))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": ["X5"], "exprvars": [] } }, "248": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 119, "label": "CASE" }, { "from": 119, "to": 120, "label": "ONLY EVAL with clause\ngoal :- ','(lte(X5, s(s(s(s(0))))), even(X5)).\nand substitution" }, { "from": 120, "to": 121, "label": "SPLIT 1" }, { "from": 120, "to": 122, "label": "SPLIT 2\nnew knowledge:\nT1 is ground\nreplacements:X5 -> T1" }, { "from": 121, "to": 123, "label": "CASE" }, { "from": 122, "to": 194, "label": "CASE" }, { "from": 123, "to": 126, "label": "PARALLEL" }, { "from": 123, "to": 127, "label": "PARALLEL" }, { "from": 126, "to": 131, "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": 127, "to": 192, "label": "ONLY EVAL with clause\nlte(0, X125).\nand substitutionX5 -> 0,\nX125 -> s(s(s(s(0))))" }, { "from": 131, "to": 132, "label": "CASE" }, { "from": 132, "to": 135, "label": "PARALLEL" }, { "from": 132, "to": 136, "label": "PARALLEL" }, { "from": 135, "to": 139, "label": "ONLY EVAL with clause\nlte(s(X54), s(X55)) :- lte(X54, X55).\nand substitutionX54 -> X56,\nX32 -> s(X56),\nX55 -> s(s(0))" }, { "from": 136, "to": 188, "label": "ONLY EVAL with clause\nlte(0, X122).\nand substitutionX32 -> 0,\nX122 -> s(s(s(0)))" }, { "from": 139, "to": 140, "label": "CASE" }, { "from": 140, "to": 143, "label": "PARALLEL" }, { "from": 140, "to": 144, "label": "PARALLEL" }, { "from": 143, "to": 156, "label": "ONLY EVAL with clause\nlte(s(X78), s(X79)) :- lte(X78, X79).\nand substitutionX78 -> X80,\nX56 -> s(X80),\nX79 -> s(0)" }, { "from": 144, "to": 184, "label": "ONLY EVAL with clause\nlte(0, X119).\nand substitutionX56 -> 0,\nX119 -> s(s(0))" }, { "from": 156, "to": 157, "label": "CASE" }, { "from": 157, "to": 158, "label": "PARALLEL" }, { "from": 157, "to": 159, "label": "PARALLEL" }, { "from": 158, "to": 169, "label": "ONLY EVAL with clause\nlte(s(X102), s(X103)) :- lte(X102, X103).\nand substitutionX102 -> X104,\nX80 -> s(X104),\nX103 -> 0" }, { "from": 159, "to": 179, "label": "ONLY EVAL with clause\nlte(0, X116).\nand substitutionX80 -> 0,\nX116 -> s(0)" }, { "from": 169, "to": 171, "label": "CASE" }, { "from": 171, "to": 172, "label": "BACKTRACK\nfor clause: lte(s(X), s(Y)) :- lte(X, Y)because of non-unification" }, { "from": 172, "to": 175, "label": "ONLY EVAL with clause\nlte(0, X113).\nand substitutionX104 -> 0,\nX113 -> 0" }, { "from": 175, "to": 176, "label": "SUCCESS" }, { "from": 179, "to": 181, "label": "SUCCESS" }, { "from": 184, "to": 185, "label": "SUCCESS" }, { "from": 188, "to": 189, "label": "SUCCESS" }, { "from": 192, "to": 193, "label": "SUCCESS" }, { "from": 194, "to": 196, "label": "PARALLEL" }, { "from": 194, "to": 197, "label": "PARALLEL" }, { "from": 196, "to": 199, "label": "EVAL with clause\neven(s(s(X131))) :- even(X131).\nand substitutionX131 -> T7,\nT1 -> s(s(T7))" }, { "from": 196, "to": 200, "label": "EVAL-BACKTRACK" }, { "from": 197, "to": 246, "label": "EVAL with clause\neven(0).\nand substitutionT1 -> 0" }, { "from": 197, "to": 248, "label": "EVAL-BACKTRACK" }, { "from": 199, "to": 122, "label": "INSTANCE with matching:\nT1 -> T7" }, { "from": 246, "to": 250, "label": "SUCCESS" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f197_out(T1) -> f194_out(T1) :|: TRUE f196_out(x) -> f194_out(x) :|: TRUE f194_in(x1) -> f196_in(x1) :|: TRUE f194_in(x2) -> f197_in(x2) :|: TRUE f196_in(s(s(T7))) -> f199_in(T7) :|: TRUE f200_out -> f196_out(x3) :|: TRUE f196_in(x4) -> f200_in :|: TRUE f199_out(x5) -> f196_out(s(s(x5))) :|: TRUE f122_in(x6) -> f194_in(x6) :|: TRUE f194_out(x7) -> f122_out(x7) :|: TRUE f199_in(x8) -> f122_in(x8) :|: TRUE f122_out(x9) -> f199_out(x9) :|: TRUE f119_out -> f1_out :|: TRUE f1_in -> f119_in :|: TRUE f119_in -> f120_in :|: TRUE f120_out -> f119_out :|: TRUE f121_out -> f122_in(x10) :|: TRUE f122_out(x11) -> f120_out :|: TRUE f120_in -> f121_in :|: TRUE Start term: f1_in ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: ---------------------------------------- (4) TRUE