YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern delmin(a,a,g) w.r.t. the given Prolog program could successfully be proven: (0) Prolog (1) PrologToDTProblemTransformerProof [SOUND, 0 ms] (2) TRIPLES (3) TriplesToPiDPProof [SOUND, 0 ms] (4) PiDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) PiDP (7) PiDPToQDPProof [SOUND, 0 ms] (8) QDP (9) QDPSizeChangeProof [EQUIVALENT, 0 ms] (10) YES ---------------------------------------- (0) Obligation: Clauses: delete(X, tree(X, void, Right), Right). delete(X, tree(X, Left, void), Left). delete(X, tree(X, Left, Right), tree(Y, Left, Right1)) :- delmin(Right, Y, Right1). delete(X, tree(Y, Left, Right), tree(Y, Left1, Right)) :- ','(less(X, Y), delete(X, Left, Left1)). delete(X, tree(Y, Left, Right), tree(Y, Left, Right1)) :- ','(less(Y, X), delete(X, Right, Right1)). delmin(tree(Y, void, Right), Y, Right). delmin(tree(X, Left, X1), Y, tree(X, Left1, X2)) :- delmin(Left, Y, Left1). less(0, s(X3)). less(s(X), s(Y)) :- less(X, Y). Query: delmin(a,a,g) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 1, "program": { "directives": [], "clauses": [ [ "(delete X (tree X (void) Right) Right)", null ], [ "(delete X (tree X Left (void)) Left)", null ], [ "(delete X (tree X Left Right) (tree Y Left Right1))", "(delmin Right Y Right1)" ], [ "(delete X (tree Y Left Right) (tree Y Left1 Right))", "(',' (less X Y) (delete X Left Left1))" ], [ "(delete X (tree Y Left Right) (tree Y Left Right1))", "(',' (less Y X) (delete X Right Right1))" ], [ "(delmin (tree Y (void) Right) Y Right)", null ], [ "(delmin (tree X Left X1) Y (tree X Left1 X2))", "(delmin Left Y Left1)" ], [ "(less (0) (s X3))", null ], [ "(less (s X) (s Y))", "(less X Y)" ] ] }, "graph": { "nodes": { "68": { "goal": [{ "clause": -1, "scope": -1, "term": "(delmin T68 T69 T66)" }], "kb": { "nonunifying": [[ "(delmin T1 T2 (tree T62 T66 T67))", "(delmin (tree X6 (void) X7) X6 X7)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T62", "T66", "T67" ], "free": [ "X6", "X7" ], "exprvars": [] } }, "69": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "152": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "114": { "goal": [{ "clause": -1, "scope": -1, "term": "(delmin T98 T99 T96)" }], "kb": { "nonunifying": [[ "(delmin T1 T2 (tree T62 (tree T92 T96 T97) T67))", "(delmin (tree X6 (void) X7) X6 X7)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T62", "T67", "T92", "T96", "T97" ], "free": [ "X6", "X7" ], "exprvars": [] } }, "70": { "goal": [ { "clause": 5, "scope": 3, "term": "(delmin T68 T69 T66)" }, { "clause": 6, "scope": 3, "term": "(delmin T68 T69 T66)" } ], "kb": { "nonunifying": [[ "(delmin T1 T2 (tree T62 T66 T67))", "(delmin (tree X6 (void) X7) X6 X7)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T62", "T66", "T67" ], "free": [ "X6", "X7" ], "exprvars": [] } }, "71": { "goal": [{ "clause": 5, "scope": 3, "term": "(delmin T68 T69 T66)" }], "kb": { "nonunifying": [[ "(delmin T1 T2 (tree T62 T66 T67))", "(delmin (tree X6 (void) X7) X6 X7)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T62", "T66", "T67" ], "free": [ "X6", "X7" ], "exprvars": [] } }, "72": { "goal": [{ "clause": 6, "scope": 3, "term": "(delmin T68 T69 T66)" }], "kb": { "nonunifying": [[ "(delmin T1 T2 (tree T62 T66 T67))", "(delmin (tree X6 (void) X7) X6 X7)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T62", "T66", "T67" ], "free": [ "X6", "X7" ], "exprvars": [] } }, "73": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "74": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "75": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "54": { "goal": [{ "clause": -1, "scope": -1, "term": "(delmin T20 T21 T18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T18"], "free": [], "exprvars": [] } }, "56": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "13": { "goal": [{ "clause": 6, "scope": 1, "term": "(delmin T1 T2 T3)" }], "kb": { "nonunifying": [[ "(delmin T1 T2 T3)", "(delmin (tree X6 (void) X7) X6 X7)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": [ "X6", "X7" ], "exprvars": [] } }, "35": { "goal": [{ "clause": 6, "scope": 1, "term": "(delmin T1 T2 T7)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [], "exprvars": [] } }, "57": { "goal": [ { "clause": 5, "scope": 2, "term": "(delmin T20 T21 T18)" }, { "clause": 6, "scope": 2, "term": "(delmin T20 T21 T18)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T18"], "free": [], "exprvars": [] } }, "58": { "goal": [{ "clause": 5, "scope": 2, "term": "(delmin T20 T21 T18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T18"], "free": [], "exprvars": [] } }, "59": { "goal": [{ "clause": 6, "scope": 2, "term": "(delmin T20 T21 T18)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T18"], "free": [], "exprvars": [] } }, "1": { "goal": [{ "clause": -1, "scope": -1, "term": "(delmin T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": [], "exprvars": [] } }, "4": { "goal": [ { "clause": 5, "scope": 1, "term": "(delmin T1 T2 T3)" }, { "clause": 6, "scope": 1, "term": "(delmin T1 T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T3"], "free": [], "exprvars": [] } }, "9": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 6, "scope": 1, "term": "(delmin T1 T2 T7)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T7"], "free": [], "exprvars": [] } }, "60": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "61": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "62": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "63": { "goal": [{ "clause": -1, "scope": -1, "term": "(delmin T50 T51 T48)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T48"], "free": [], "exprvars": [] } }, "64": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } } }, "edges": [ { "from": 1, "to": 4, "label": "CASE" }, { "from": 4, "to": 9, "label": "EVAL with clause\ndelmin(tree(X6, void, X7), X6, X7).\nand substitutionX6 -> T6,\nX7 -> T7,\nT1 -> tree(T6, void, T7),\nT2 -> T6,\nT3 -> T7" }, { "from": 4, "to": 13, "label": "EVAL-BACKTRACK" }, { "from": 9, "to": 35, "label": "SUCCESS" }, { "from": 13, "to": 68, "label": "EVAL with clause\ndelmin(tree(X58, X59, X60), X61, tree(X58, X62, X63)) :- delmin(X59, X61, X62).\nand substitutionX58 -> T62,\nX59 -> T68,\nX60 -> T64,\nT1 -> tree(T62, T68, T64),\nT2 -> T69,\nX61 -> T69,\nX62 -> T66,\nX63 -> T67,\nT3 -> tree(T62, T66, T67),\nT63 -> T68,\nT65 -> T69" }, { "from": 13, "to": 69, "label": "EVAL-BACKTRACK" }, { "from": 35, "to": 54, "label": "EVAL with clause\ndelmin(tree(X14, X15, X16), X17, tree(X14, X18, X19)) :- delmin(X15, X17, X18).\nand substitutionX14 -> T14,\nX15 -> T20,\nX16 -> T16,\nT1 -> tree(T14, T20, T16),\nT2 -> T21,\nX17 -> T21,\nX18 -> T18,\nX19 -> T19,\nT7 -> tree(T14, T18, T19),\nT15 -> T20,\nT17 -> T21" }, { "from": 35, "to": 56, "label": "EVAL-BACKTRACK" }, { "from": 54, "to": 57, "label": "CASE" }, { "from": 57, "to": 58, "label": "PARALLEL" }, { "from": 57, "to": 59, "label": "PARALLEL" }, { "from": 58, "to": 60, "label": "EVAL with clause\ndelmin(tree(X28, void, X29), X28, X29).\nand substitutionX28 -> T30,\nX29 -> T31,\nT20 -> tree(T30, void, T31),\nT21 -> T30,\nT18 -> T31" }, { "from": 58, "to": 61, "label": "EVAL-BACKTRACK" }, { "from": 59, "to": 63, "label": "EVAL with clause\ndelmin(tree(X42, X43, X44), X45, tree(X42, X46, X47)) :- delmin(X43, X45, X46).\nand substitutionX42 -> T44,\nX43 -> T50,\nX44 -> T46,\nT20 -> tree(T44, T50, T46),\nT21 -> T51,\nX45 -> T51,\nX46 -> T48,\nX47 -> T49,\nT18 -> tree(T44, T48, T49),\nT45 -> T50,\nT47 -> T51" }, { "from": 59, "to": 64, "label": "EVAL-BACKTRACK" }, { "from": 60, "to": 62, "label": "SUCCESS" }, { "from": 63, "to": 1, "label": "INSTANCE with matching:\nT1 -> T50\nT2 -> T51\nT3 -> T48" }, { "from": 68, "to": 70, "label": "CASE" }, { "from": 70, "to": 71, "label": "PARALLEL" }, { "from": 70, "to": 72, "label": "PARALLEL" }, { "from": 71, "to": 73, "label": "EVAL with clause\ndelmin(tree(X72, void, X73), X72, X73).\nand substitutionX72 -> T78,\nX73 -> T79,\nT68 -> tree(T78, void, T79),\nT69 -> T78,\nT66 -> T79" }, { "from": 71, "to": 74, "label": "EVAL-BACKTRACK" }, { "from": 72, "to": 114, "label": "EVAL with clause\ndelmin(tree(X86, X87, X88), X89, tree(X86, X90, X91)) :- delmin(X87, X89, X90).\nand substitutionX86 -> T92,\nX87 -> T98,\nX88 -> T94,\nT68 -> tree(T92, T98, T94),\nT69 -> T99,\nX89 -> T99,\nX90 -> T96,\nX91 -> T97,\nT66 -> tree(T92, T96, T97),\nT93 -> T98,\nT95 -> T99" }, { "from": 72, "to": 152, "label": "EVAL-BACKTRACK" }, { "from": 73, "to": 75, "label": "SUCCESS" }, { "from": 114, "to": 1, "label": "INSTANCE with matching:\nT1 -> T98\nT2 -> T99\nT3 -> T96" } ], "type": "Graph" } } ---------------------------------------- (2) Obligation: Triples: delminA(tree(X1, tree(X2, X3, X4), X5), X6, tree(X1, tree(X2, X7, X8), X9)) :- delminA(X3, X6, X7). delminA(tree(X1, tree(X2, X3, X4), X5), X6, tree(X1, tree(X2, X7, X8), X9)) :- delminA(X3, X6, X7). Clauses: delmincA(tree(X1, void, X2), X1, X2). delmincA(tree(X1, tree(X2, void, X3), X4), X2, tree(X1, X3, X5)). delmincA(tree(X1, tree(X2, X3, X4), X5), X6, tree(X1, tree(X2, X7, X8), X9)) :- delmincA(X3, X6, X7). delmincA(tree(X1, tree(X2, void, X3), X4), X2, tree(X1, X3, X5)). delmincA(tree(X1, tree(X2, X3, X4), X5), X6, tree(X1, tree(X2, X7, X8), X9)) :- delmincA(X3, X6, X7). Afs: delminA(x1, x2, x3) = delminA(x3) ---------------------------------------- (3) TriplesToPiDPProof (SOUND) We use the technique of [DT09]. With regard to the inferred argument filtering the predicates were used in the following modes: delminA_in_3: (f,f,b) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: DELMINA_IN_AAG(tree(X1, tree(X2, X3, X4), X5), X6, tree(X1, tree(X2, X7, X8), X9)) -> U1_AAG(X1, X2, X3, X4, X5, X6, X7, X8, X9, delminA_in_aag(X3, X6, X7)) DELMINA_IN_AAG(tree(X1, tree(X2, X3, X4), X5), X6, tree(X1, tree(X2, X7, X8), X9)) -> DELMINA_IN_AAG(X3, X6, X7) R is empty. The argument filtering Pi contains the following mapping: delminA_in_aag(x1, x2, x3) = delminA_in_aag(x3) tree(x1, x2, x3) = tree(x1, x2, x3) DELMINA_IN_AAG(x1, x2, x3) = DELMINA_IN_AAG(x3) U1_AAG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = U1_AAG(x1, x2, x7, x8, x9, x10) We have to consider all (P,R,Pi)-chains Infinitary Constructor Rewriting Termination of PiDP implies Termination of TRIPLES ---------------------------------------- (4) Obligation: Pi DP problem: The TRS P consists of the following rules: DELMINA_IN_AAG(tree(X1, tree(X2, X3, X4), X5), X6, tree(X1, tree(X2, X7, X8), X9)) -> U1_AAG(X1, X2, X3, X4, X5, X6, X7, X8, X9, delminA_in_aag(X3, X6, X7)) DELMINA_IN_AAG(tree(X1, tree(X2, X3, X4), X5), X6, tree(X1, tree(X2, X7, X8), X9)) -> DELMINA_IN_AAG(X3, X6, X7) R is empty. The argument filtering Pi contains the following mapping: delminA_in_aag(x1, x2, x3) = delminA_in_aag(x3) tree(x1, x2, x3) = tree(x1, x2, x3) DELMINA_IN_AAG(x1, x2, x3) = DELMINA_IN_AAG(x3) U1_AAG(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = U1_AAG(x1, x2, x7, x8, x9, x10) We have to consider all (P,R,Pi)-chains ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LOPSTR] contains 1 SCC with 1 less node. ---------------------------------------- (6) Obligation: Pi DP problem: The TRS P consists of the following rules: DELMINA_IN_AAG(tree(X1, tree(X2, X3, X4), X5), X6, tree(X1, tree(X2, X7, X8), X9)) -> DELMINA_IN_AAG(X3, X6, X7) R is empty. The argument filtering Pi contains the following mapping: tree(x1, x2, x3) = tree(x1, x2, x3) DELMINA_IN_AAG(x1, x2, x3) = DELMINA_IN_AAG(x3) We have to consider all (P,R,Pi)-chains ---------------------------------------- (7) PiDPToQDPProof (SOUND) Transforming (infinitary) constructor rewriting Pi-DP problem [LOPSTR] into ordinary QDP problem [LPAR04] by application of Pi. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: DELMINA_IN_AAG(tree(X1, tree(X2, X7, X8), X9)) -> DELMINA_IN_AAG(X7) R is empty. Q is empty. We have to consider all (P,Q,R)-chains. ---------------------------------------- (9) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *DELMINA_IN_AAG(tree(X1, tree(X2, X7, X8), X9)) -> DELMINA_IN_AAG(X7) The graph contains the following edges 1 > 1 ---------------------------------------- (10) YES