/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: 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, 12 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": 52, "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": { "55": { "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": [] } }, "type": "Nodes", "150": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "120": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "121": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "133": { "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": [] } }, "123": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "145": { "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": [] } }, "135": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "146": { "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": [] } }, "127": { "goal": [{ "clause": 1, "scope": 1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "149": { "goal": [{ "clause": -1, "scope": -1, "term": "(p T30)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T30"], "free": [], "exprvars": [] } }, "128": { "goal": [{ "clause": 2, "scope": 1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "52": { "goal": [{ "clause": -1, "scope": -1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "53": { "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": [] } }, "54": { "goal": [{ "clause": 0, "scope": 1, "term": "(p T1)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 52, "to": 53, "label": "CASE" }, { "from": 53, "to": 54, "label": "PARALLEL" }, { "from": 53, "to": 55, "label": "PARALLEL" }, { "from": 54, "to": 120, "label": "EVAL with clause\np(cons(X5, nil)).\nand substitutionX5 -> T6,\nT1 -> cons(T6, nil)" }, { "from": 54, "to": 121, "label": "EVAL-BACKTRACK" }, { "from": 55, "to": 127, "label": "PARALLEL" }, { "from": 55, "to": 128, "label": "PARALLEL" }, { "from": 120, "to": 123, "label": "SUCCESS" }, { "from": 127, "to": 133, "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": 127, "to": 135, "label": "EVAL-BACKTRACK" }, { "from": 128, "to": 149, "label": "EVAL with clause\np(cons(0, X29)) :- p(X29).\nand substitutionX29 -> T30,\nT1 -> cons(0, T30)" }, { "from": 128, "to": 150, "label": "EVAL-BACKTRACK" }, { "from": 133, "to": 145, "label": "SPLIT 1" }, { "from": 133, "to": 146, "label": "SPLIT 2\nnew knowledge:\nT19 is ground\nT20 is ground\nT21 is ground" }, { "from": 145, "to": 52, "label": "INSTANCE with matching:\nT1 -> cons(T19, cons(T20, T21))" }, { "from": 146, "to": 52, "label": "INSTANCE with matching:\nT1 -> cons(s(s(s(s(T20)))), T21)" }, { "from": 149, "to": 52, "label": "INSTANCE with matching:\nT1 -> T30" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Rules: f146_out(T20, T21) -> f133_out(T19, T20, T21) :|: TRUE f133_in(x, x1, x2) -> f145_in(x, x1, x2) :|: TRUE f145_out(x3, x4, x5) -> f146_in(x4, x5) :|: TRUE f52_out(T30) -> f149_out(T30) :|: TRUE f149_in(x6) -> f52_in(x6) :|: TRUE f128_in(cons(0, x7)) -> f149_in(x7) :|: TRUE f128_in(T1) -> f150_in :|: TRUE f149_out(x8) -> f128_out(cons(0, x8)) :|: TRUE f150_out -> f128_out(x9) :|: TRUE f55_out(x10) -> f53_out(x10) :|: TRUE f53_in(x11) -> f54_in(x11) :|: TRUE f54_out(x12) -> f53_out(x12) :|: TRUE f53_in(x13) -> f55_in(x13) :|: TRUE f146_in(x14, x15) -> f52_in(cons(s(s(s(s(x14)))), x15)) :|: TRUE f52_out(cons(s(s(s(s(x16)))), x17)) -> f146_out(x16, x17) :|: TRUE f127_in(x18) -> f135_in :|: TRUE f135_out -> f127_out(x19) :|: TRUE f127_in(cons(s(s(x20)), cons(x21, x22))) -> f133_in(x20, x21, x22) :|: TRUE f133_out(x23, x24, x25) -> f127_out(cons(s(s(x23)), cons(x24, x25))) :|: TRUE f53_out(x26) -> f52_out(x26) :|: TRUE f52_in(x27) -> f53_in(x27) :|: TRUE f55_in(x28) -> f127_in(x28) :|: TRUE f55_in(x29) -> f128_in(x29) :|: TRUE f127_out(x30) -> f55_out(x30) :|: TRUE f128_out(x31) -> f55_out(x31) :|: TRUE f145_in(x32, x33, x34) -> f52_in(cons(x32, cons(x33, x34))) :|: TRUE f52_out(cons(x35, cons(x36, x37))) -> f145_out(x35, x36, x37) :|: TRUE Start term: f52_in(T1) ---------------------------------------- (3) IRSwTSimpleDependencyGraphProof (EQUIVALENT) Constructed simple dependency graph. Simplified to the following IRSwTs: intTRSProblem: f133_in(x, x1, x2) -> f145_in(x, x1, x2) :|: TRUE f149_in(x6) -> f52_in(x6) :|: TRUE f128_in(cons(0, x7)) -> f149_in(x7) :|: TRUE f53_in(x13) -> f55_in(x13) :|: TRUE f127_in(cons(s(s(x20)), cons(x21, x22))) -> f133_in(x20, x21, x22) :|: TRUE f52_in(x27) -> f53_in(x27) :|: TRUE f55_in(x28) -> f127_in(x28) :|: TRUE f55_in(x29) -> f128_in(x29) :|: TRUE f145_in(x32, x33, x34) -> f52_in(cons(x32, cons(x33, x34))) :|: TRUE ---------------------------------------- (4) Obligation: Rules: f133_in(x, x1, x2) -> f145_in(x, x1, x2) :|: TRUE f149_in(x6) -> f52_in(x6) :|: TRUE f128_in(cons(0, x7)) -> f149_in(x7) :|: TRUE f53_in(x13) -> f55_in(x13) :|: TRUE f127_in(cons(s(s(x20)), cons(x21, x22))) -> f133_in(x20, x21, x22) :|: TRUE f52_in(x27) -> f53_in(x27) :|: TRUE f55_in(x28) -> f127_in(x28) :|: TRUE f55_in(x29) -> f128_in(x29) :|: TRUE f145_in(x32, x33, x34) -> f52_in(cons(x32, cons(x33, x34))) :|: TRUE ---------------------------------------- (5) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (6) Obligation: Rules: f53_in(cons(s(s(x20:0)), cons(x21:0, x22:0))) -> f53_in(cons(x20:0, cons(x21:0, x22:0))) :|: TRUE f53_in(cons(cons_0, x7:0)) -> f53_in(x7: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: f53_in(cons(s(s(x20:0)), cons(x21:0, x22:0))) -> f53_in(cons(x20:0, cons(x21:0, x22:0))) :|: TRUE f53_in(cons(cons_0, x7:0)) -> f53_in(x7:0) :|: TRUE && cons_0 = 0 ---------------------------------------- (9) IRSwTTerminationDigraphProof (EQUIVALENT) Constructed termination digraph! Nodes: (1) f53_in(cons(s(s(x20:0)), cons(x21:0, x22:0))) -> f53_in(cons(x20:0, cons(x21:0, x22:0))) :|: TRUE (2) f53_in(cons(cons_0, x7:0)) -> f53_in(x7:0) :|: TRUE && cons_0 = 0 Arcs: (1) -> (1), (2) (2) -> (1), (2) This digraph is fully evaluated! ---------------------------------------- (10) Obligation: Termination digraph: Nodes: (1) f53_in(cons(s(s(x20:0)), cons(x21:0, x22:0))) -> f53_in(cons(x20:0, cons(x21:0, x22:0))) :|: TRUE (2) f53_in(cons(cons_0, x7:0)) -> f53_in(x7: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: f53_in(cons(cons_0, x7:0:0)) -> f53_in(x7:0:0) :|: TRUE && cons_0 = 0 f53_in(cons(s(s(x20:0:0)), cons(x21:0:0, x22:0:0))) -> f53_in(cons(x20:0:0, cons(x21:0:0, x22:0:0))) :|: TRUE ---------------------------------------- (13) TempFilterProof (SOUND) Used the following sort dictionary for filtering: f53_in(VARIABLE) cons(VARIABLE, VARIABLE) s(VARIABLE) Removed predefined arithmetic. ---------------------------------------- (14) Obligation: Rules: f53_in(cons(predef, x7:0:0)) -> f53_in(x7:0:0) f53_in(cons(s(s(x20:0:0)), cons(x21:0:0, x22:0:0))) -> f53_in(cons(x20:0:0, cons(x21:0:0, x22: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: f53_in(cons(predef, x7:0:0)) -> f53_in(x7:0:0) f53_in(cons(s(s(x20:0:0)), cons(x21:0:0, x22:0:0))) -> f53_in(cons(x20:0:0, cons(x21:0:0, x22: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: f53_in(cons(predef, x7:0:0)) -> f53_in(x7:0:0) f53_in(cons(s(s(x20:0:0)), cons(x21:0:0, x22:0:0))) -> f53_in(cons(x20:0:0, cons(x21:0:0, x22:0:0))) No rules are removed from R. Used ordering: POLO with Polynomial interpretation [POLO]: POL(cons(x_1, x_2)) = x_1 + 2*x_2 POL(f53_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