YES proof of /export/starexec/sandbox/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, 56 ms] (6) IRSwT (7) IRSFormatTransformerProof [EQUIVALENT, 0 ms] (8) IRSwT (9) IRSwTTerminationDigraphProof [EQUIVALENT, 20 ms] (10) IRSwT (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IRSwT (13) TempFilterProof [SOUND, 9 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(.(X, [])). p(.(s(s(X)), .(Y, Xs))) :- ','(p(.(X, .(Y, Xs))), p(.(s(s(s(s(Y)))), Xs))). p(.(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 (. X ([])))", null ], [ "(p (. (s (s X)) (. Y Xs)))", "(',' (p (. X (. Y Xs))) (p (. (s (s (s (s Y)))) Xs)))" ], [ "(p (. (0) Xs))", "(p Xs)" ] ] }, "graph": { "nodes": { "22": { "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": [] } }, "26": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "27": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "29": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "120": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "110": { "goal": [{ "clause": -1, "scope": -1, "term": "(p (. (s (s (s (s T20)))) T21))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T20", "T21" ], "free": [], "exprvars": [] } }, "100": { "goal": [{ "clause": -1, "scope": -1, "term": "(',' (p (. T19 (. T20 T21))) (p (. (s (s (s (s T20)))) T21)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T19", "T20", "T21" ], "free": [], "exprvars": [] } }, "2": { "goal": [{ "clause": -1, "scope": -1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "101": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "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": [] } }, "119": { "goal": [{ "clause": -1, "scope": -1, "term": "(p T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T30"], "free": [], "exprvars": [] } }, "109": { "goal": [{ "clause": -1, "scope": -1, "term": "(p (. T19 (. T20 T21)))" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T19", "T20", "T21" ], "free": [], "exprvars": [] } }, "97": { "goal": [{ "clause": 1, "scope": 1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "21": { "goal": [{ "clause": 0, "scope": 1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "98": { "goal": [{ "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": 21, "label": "PARALLEL" }, { "from": 4, "to": 22, "label": "PARALLEL" }, { "from": 21, "to": 26, "label": "EVAL with clause\np(.(X5, [])).\nand substitutionX5 -> T6,\nT1 -> .(T6, [])" }, { "from": 21, "to": 27, "label": "EVAL-BACKTRACK" }, { "from": 22, "to": 97, "label": "PARALLEL" }, { "from": 22, "to": 98, "label": "PARALLEL" }, { "from": 26, "to": 29, "label": "SUCCESS" }, { "from": 97, "to": 100, "label": "EVAL with clause\np(.(s(s(X18)), .(X19, X20))) :- ','(p(.(X18, .(X19, X20))), p(.(s(s(s(s(X19)))), X20))).\nand substitutionX18 -> T19,\nX19 -> T20,\nX20 -> T21,\nT1 -> .(s(s(T19)), .(T20, T21))" }, { "from": 97, "to": 101, "label": "EVAL-BACKTRACK" }, { "from": 98, "to": 119, "label": "EVAL with clause\np(.(0, X29)) :- p(X29).\nand substitutionX29 -> T30,\nT1 -> .(0, T30)" }, { "from": 98, "to": 120, "label": "EVAL-BACKTRACK" }, { "from": 100, "to": 109, "label": "SPLIT 1" }, { "from": 100, "to": 110, "label": "SPLIT 2\nnew knowledge:\nT19 is ground\nT20 is ground\nT21 is ground" }, { "from": 109, "to": 2, "label": "INSTANCE with matching:\nT1 -> .(T19, .(T20, T21))" }, { "from": 110, "to": 2, "label": "INSTANCE with matching:\nT1 -> .(s(s(s(s(T20)))), T21)" }, { "from": 119, "to": 2, "label": "INSTANCE with matching:\nT1 -> T30" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f2_in(T1) -> f4_in(T1) :|: TRUE f4_out(x) -> f2_out(x) :|: TRUE f97_in(.(s(s(T19)), .(T20, T21))) -> f100_in(T19, T20, T21) :|: TRUE f100_out(x1, x2, x3) -> f97_out(.(s(s(x1)), .(x2, x3))) :|: TRUE f101_out -> f97_out(x4) :|: TRUE f97_in(x5) -> f101_in :|: TRUE f2_out(T30) -> f119_out(T30) :|: TRUE f119_in(x6) -> f2_in(x6) :|: TRUE f21_out(x7) -> f4_out(x7) :|: TRUE f4_in(x8) -> f22_in(x8) :|: TRUE f4_in(x9) -> f21_in(x9) :|: TRUE f22_out(x10) -> f4_out(x10) :|: TRUE f100_in(x11, x12, x13) -> f109_in(x11, x12, x13) :|: TRUE f109_out(x14, x15, x16) -> f110_in(x15, x16) :|: TRUE f110_out(x17, x18) -> f100_out(x19, x17, x18) :|: TRUE f98_in(x20) -> f120_in :|: TRUE f98_in(.(0, x21)) -> f119_in(x21) :|: TRUE f119_out(x22) -> f98_out(.(0, x22)) :|: TRUE f120_out -> f98_out(x23) :|: TRUE f98_out(x24) -> f22_out(x24) :|: TRUE f97_out(x25) -> f22_out(x25) :|: TRUE f22_in(x26) -> f98_in(x26) :|: TRUE f22_in(x27) -> f97_in(x27) :|: TRUE f2_out(.(s(s(s(s(x28)))), x29)) -> f110_out(x28, x29) :|: TRUE f110_in(x30, x31) -> f2_in(.(s(s(s(s(x30)))), x31)) :|: TRUE f109_in(x32, x33, x34) -> f2_in(.(x32, .(x33, x34))) :|: TRUE f2_out(.(x35, .(x36, x37))) -> f109_out(x35, x36, x37) :|: TRUE Start term: f2_in(T1) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f2_in(T1) -> f4_in(T1) :|: TRUE f97_in(.(s(s(T19)), .(T20, T21))) -> f100_in(T19, T20, T21) :|: TRUE f119_in(x6) -> f2_in(x6) :|: TRUE f4_in(x8) -> f22_in(x8) :|: TRUE f100_in(x11, x12, x13) -> f109_in(x11, x12, x13) :|: TRUE f98_in(.(0, x21)) -> f119_in(x21) :|: TRUE f22_in(x26) -> f98_in(x26) :|: TRUE f22_in(x27) -> f97_in(x27) :|: TRUE f109_in(x32, x33, x34) -> f2_in(.(x32, .(x33, x34))) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f2_in(T1) -> f4_in(T1) :|: TRUE f97_in(.(s(s(T19)), .(T20, T21))) -> f100_in(T19, T20, T21) :|: TRUE f119_in(x6) -> f2_in(x6) :|: TRUE f4_in(x8) -> f22_in(x8) :|: TRUE f100_in(x11, x12, x13) -> f109_in(x11, x12, x13) :|: TRUE f98_in(.(0, x21)) -> f119_in(x21) :|: TRUE f22_in(x26) -> f98_in(x26) :|: TRUE f22_in(x27) -> f97_in(x27) :|: TRUE f109_in(x32, x33, x34) -> f2_in(.(x32, .(x33, x34))) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f22_in(.(s(s(T19:0)), .(T20:0, T21:0))) -> f22_in(.(T19:0, .(T20:0, T21:0))) :|: TRUE f22_in(.(cons_0, x21:0)) -> f22_in(x21: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: f22_in(.(s(s(T19:0)), .(T20:0, T21:0))) -> f22_in(.(T19:0, .(T20:0, T21:0))) :|: TRUE f22_in(.(cons_0, x21:0)) -> f22_in(x21:0) :|: TRUE && cons_0 = 0 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f22_in(.(s(s(T19:0)), .(T20:0, T21:0))) -> f22_in(.(T19:0, .(T20:0, T21:0))) :|: TRUE (2) f22_in(.(cons_0, x21:0)) -> f22_in(x21:0) :|: TRUE && cons_0 = 0 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f22_in(.(s(s(T19:0)), .(T20:0, T21:0))) -> f22_in(.(T19:0, .(T20:0, T21:0))) :|: TRUE (2) f22_in(.(cons_0, x21:0)) -> f22_in(x21: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: f22_in(.(s(s(T19:0:0)), .(T20:0:0, T21:0:0))) -> f22_in(.(T19:0:0, .(T20:0:0, T21:0:0))) :|: TRUE f22_in(.(cons_0, x21:0:0)) -> f22_in(x21:0:0) :|: TRUE && cons_0 = 0 ---------------------------------------- (13) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f22_in(VARIABLE) .(VARIABLE, VARIABLE) s(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (14) Obligation: Rules: f22_in(.(s(s(T19:0:0)), .(T20:0:0, T21:0:0))) -> f22_in(.(T19:0:0, .(T20:0:0, T21:0:0))) f22_in(.(predef, x21:0:0)) -> f22_in(x21: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: f22_in(.(s(s(T19:0:0)), .(T20:0:0, T21:0:0))) -> f22_in(.(T19:0:0, .(T20:0:0, T21:0:0))) f22_in(.(predef, x21:0:0)) -> f22_in(x21: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: f22_in(.(s(s(T19:0:0)), .(T20:0:0, T21:0:0))) -> f22_in(.(T19:0:0, .(T20:0:0, T21:0:0))) f22_in(.(predef, x21:0:0)) -> f22_in(x21:0:0) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(.(x_1, x_2)) = x_1 + x_2 POL(f22_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