YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern p(g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToIRSwTTransformerProof [SOUND, 0 ms] (2) IRSwT (3) IRSwTSimpleDependencyGraphProof [EQUIVALENT, 0 ms] (4) IRSwT (5) IntTRSCompressionProof [EQUIVALENT, 58 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 18 ms] (10) IRSwT (11) IntTRSCompressionProof [EQUIVALENT, 2 ms] (12) IRSwT (13) TempFilterProof [SOUND, 10 ms] (14) IRSwT (15) IRSwTToQDPProof [SOUND, 0 ms] (16) QDP (17) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (18) QDP (19) PisEmptyProof [EQUIVALENT, 0 ms] (20) YES ---------------------------------------- (0) Obligation: Clauses: p(cons(X, nil)). p(cons(s(s(X)), cons(Y, Xs))) :- ','(p(cons(X, cons(Y, Xs))), p(cons(s(s(s(s(Y)))), Xs))). p(cons(0, Xs)) :- p(Xs). Query: p(g) ---------------------------------------- (1) PrologToIRSwTTransformerProof (SOUND) Transformed Prolog program to IRSwT according to method in Master Thesis of A. Weinert { "root": 2, "program": { "directives": [], "clauses": [ [ "(p (cons X (nil)))", null ], [ "(p (cons (s (s X)) (cons Y Xs)))", "(',' (p (cons X (cons Y Xs))) (p (cons (s (s (s (s Y)))) Xs)))" ], [ "(p (cons (0) Xs))", "(p Xs)" ] ] }, "graph": { "nodes": { "11": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "22": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p (cons T19 (cons T20 T21))) (p (cons (s (s (s (s T20)))) T21)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T19", "T20", "T21" ], "free": [], "exprvars": [] } }, "99": { "goal": [{ "clause": -1, "scope": -1, "term": "(p (cons T19 (cons T20 T21)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T19", "T20", "T21" ], "free": [], "exprvars": [] } }, "23": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "13": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "15": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "18": { "goal": [{ "clause": 1, "scope": 1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "19": { "goal": [{ "clause": 2, "scope": 1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "type": "Nodes", "100": { "goal": [{ "clause": -1, "scope": -1, "term": "(p (cons (s (s (s (s T20)))) T21))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21" ], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "4": { "goal": [ { "clause": 0, "scope": 1, "term": "(p T1)" }, { "clause": 1, "scope": 1, "term": "(p T1)" }, { "clause": 2, "scope": 1, "term": "(p T1)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "103": { "goal": [{ "clause": -1, "scope": -1, "term": "(p T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T30"], "free": [], "exprvars": [] } }, "104": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "9": { "goal": [{ "clause": 0, "scope": 1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "10": { "goal": [ { "clause": 1, "scope": 1, "term": "(p T1)" }, { "clause": 2, "scope": 1, "term": "(p T1)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 2, "to": 4, "label": "CASE" }, { "from": 4, "to": 9, "label": "PARALLEL" }, { "from": 4, "to": 10, "label": "PARALLEL" }, { "from": 9, "to": 11, "label": "EVAL with clause\np(cons(X5, nil)).\nand substitutionX5 -> T6,\nT1 -> cons(T6, nil)" }, { "from": 9, "to": 13, "label": "EVAL-BACKTRACK" }, { "from": 10, "to": 18, "label": "PARALLEL" }, { "from": 10, "to": 19, "label": "PARALLEL" }, { "from": 11, "to": 15, "label": "SUCCESS" }, { "from": 18, "to": 22, "label": "EVAL with clause\np(cons(s(s(X18)), cons(X19, X20))) :- ','(p(cons(X18, cons(X19, X20))), p(cons(s(s(s(s(X19)))), X20))).\nand substitutionX18 -> T19,\nX19 -> T20,\nX20 -> T21,\nT1 -> cons(s(s(T19)), cons(T20, T21))" }, { "from": 18, "to": 23, "label": "EVAL-BACKTRACK" }, { "from": 19, "to": 103, "label": "EVAL with clause\np(cons(0, X29)) :- p(X29).\nand substitutionX29 -> T30,\nT1 -> cons(0, T30)" }, { "from": 19, "to": 104, "label": "EVAL-BACKTRACK" }, { "from": 22, "to": 99, "label": "SPLIT 1" }, { "from": 22, "to": 100, "label": "SPLIT 2\nnew knowledge:\nT19 is ground\nT20 is ground\nT21 is ground" }, { "from": 99, "to": 2, "label": "INSTANCE with matching:\nT1 -> cons(T19, cons(T20, T21))" }, { "from": 100, "to": 2, "label": "INSTANCE with matching:\nT1 -> cons(s(s(s(s(T20)))), T21)" }, { "from": 103, "to": 2, "label": "INSTANCE with matching:\nT1 -> T30" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f99_out(T19, T20, T21) -> f100_in(T20, T21) :|: TRUE f100_out(x, x1) -> f22_out(x2, x, x1) :|: TRUE f22_in(x3, x4, x5) -> f99_in(x3, x4, x5) :|: TRUE f18_in(cons(s(s(x6)), cons(x7, x8))) -> f22_in(x6, x7, x8) :|: TRUE f18_in(T1) -> f23_in :|: TRUE f22_out(x9, x10, x11) -> f18_out(cons(s(s(x9)), cons(x10, x11))) :|: TRUE f23_out -> f18_out(x12) :|: TRUE f104_out -> f19_out(x13) :|: TRUE f19_in(cons(0, T30)) -> f103_in(T30) :|: TRUE f19_in(x14) -> f104_in :|: TRUE f103_out(x15) -> f19_out(cons(0, x15)) :|: TRUE f4_in(x16) -> f9_in(x16) :|: TRUE f4_in(x17) -> f10_in(x17) :|: TRUE f9_out(x18) -> f4_out(x18) :|: TRUE f10_out(x19) -> f4_out(x19) :|: TRUE f19_out(x20) -> f10_out(x20) :|: TRUE f18_out(x21) -> f10_out(x21) :|: TRUE f10_in(x22) -> f19_in(x22) :|: TRUE f10_in(x23) -> f18_in(x23) :|: TRUE f99_in(x24, x25, x26) -> f2_in(cons(x24, cons(x25, x26))) :|: TRUE f2_out(cons(x27, cons(x28, x29))) -> f99_out(x27, x28, x29) :|: TRUE f2_in(x30) -> f4_in(x30) :|: TRUE f4_out(x31) -> f2_out(x31) :|: TRUE f2_out(cons(s(s(s(s(x32)))), x33)) -> f100_out(x32, x33) :|: TRUE f100_in(x34, x35) -> f2_in(cons(s(s(s(s(x34)))), x35)) :|: TRUE f2_out(x36) -> f103_out(x36) :|: TRUE f103_in(x37) -> f2_in(x37) :|: TRUE Start term: f2_in(T1) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f22_in(x3, x4, x5) -> f99_in(x3, x4, x5) :|: TRUE f18_in(cons(s(s(x6)), cons(x7, x8))) -> f22_in(x6, x7, x8) :|: TRUE f19_in(cons(0, T30)) -> f103_in(T30) :|: TRUE f4_in(x17) -> f10_in(x17) :|: TRUE f10_in(x22) -> f19_in(x22) :|: TRUE f10_in(x23) -> f18_in(x23) :|: TRUE f99_in(x24, x25, x26) -> f2_in(cons(x24, cons(x25, x26))) :|: TRUE f2_in(x30) -> f4_in(x30) :|: TRUE f103_in(x37) -> f2_in(x37) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f22_in(x3, x4, x5) -> f99_in(x3, x4, x5) :|: TRUE f18_in(cons(s(s(x6)), cons(x7, x8))) -> f22_in(x6, x7, x8) :|: TRUE f19_in(cons(0, T30)) -> f103_in(T30) :|: TRUE f4_in(x17) -> f10_in(x17) :|: TRUE f10_in(x22) -> f19_in(x22) :|: TRUE f10_in(x23) -> f18_in(x23) :|: TRUE f99_in(x24, x25, x26) -> f2_in(cons(x24, cons(x25, x26))) :|: TRUE f2_in(x30) -> f4_in(x30) :|: TRUE f103_in(x37) -> f2_in(x37) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f4_in(cons(s(s(x6:0)), cons(x7:0, x8:0))) -> f4_in(cons(x6:0, cons(x7:0, x8:0))) :|: TRUE f4_in(cons(cons_0, T30:0)) -> f4_in(T30:0) :|: TRUE && cons_0 = 0 ---------------------------------------- (7) IRSFormatTransformerProof (EQUIVALENT) Reformatted IRS to match normalized format (transformed away non-linear left-hand sides, !=, / and %). ---------------------------------------- (8) Obligation: Rules: f4_in(cons(s(s(x6:0)), cons(x7:0, x8:0))) -> f4_in(cons(x6:0, cons(x7:0, x8:0))) :|: TRUE f4_in(cons(cons_0, T30:0)) -> f4_in(T30:0) :|: TRUE && cons_0 = 0 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f4_in(cons(s(s(x6:0)), cons(x7:0, x8:0))) -> f4_in(cons(x6:0, cons(x7:0, x8:0))) :|: TRUE (2) f4_in(cons(cons_0, T30:0)) -> f4_in(T30:0) :|: TRUE && cons_0 = 0 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f4_in(cons(s(s(x6:0)), cons(x7:0, x8:0))) -> f4_in(cons(x6:0, cons(x7:0, x8:0))) :|: TRUE (2) f4_in(cons(cons_0, T30:0)) -> f4_in(T30:0) :|: TRUE && cons_0 = 0 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f4_in(cons(s(s(x6:0:0)), cons(x7:0:0, x8:0:0))) -> f4_in(cons(x6:0:0, cons(x7:0:0, x8:0:0))) :|: TRUE f4_in(cons(cons_0, T30:0:0)) -> f4_in(T30:0:0) :|: TRUE && cons_0 = 0 ---------------------------------------- (13) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f4_in(VARIABLE) cons(VARIABLE, VARIABLE) s(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (14) Obligation: Rules: f4_in(cons(s(s(x6:0:0)), cons(x7:0:0, x8:0:0))) -> f4_in(cons(x6:0:0, cons(x7:0:0, x8:0:0))) f4_in(cons(predef, T30:0:0)) -> f4_in(T30:0:0) ---------------------------------------- (15) IRSwTToQDPProof (SOUND) Removed the integers and created a QDP-Problem. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: f4_in(cons(s(s(x6:0:0)), cons(x7:0:0, x8:0:0))) -> f4_in(cons(x6:0:0, cons(x7:0:0, x8:0:0))) f4_in(cons(predef, T30:0:0)) -> f4_in(T30:0:0) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (17) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. The following dependency pairs can be deleted: f4_in(cons(s(s(x6:0:0)), cons(x7:0:0, x8:0:0))) -> f4_in(cons(x6:0:0, cons(x7:0:0, x8:0:0))) f4_in(cons(predef, T30:0:0)) -> f4_in(T30:0:0) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(cons(x_1, x_2)) = x_1 + x_2 POL(f4_in(x_1)) = 2*x_1 POL(predef) = 0 POL(s(x_1)) = 2*x_1 ---------------------------------------- (18) Obligation: Q DP problem: P is empty. R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (19) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (20) YES