YES proof of /export/starexec/sandbox/benchmark/theBenchmark.pl # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Left Termination of the query pattern delmin(g,a,a) 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(g,a,a) ---------------------------------------- (1) PrologToDTProblemTransformerProof (SOUND) Built DT problem from termination graph DT10. { "root": 39, "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": { "39": { "goal": [{ "clause": -1, "scope": -1, "term": "(delmin T1 T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T1"], "free": [], "exprvars": [] } }, "191": { "goal": [ { "clause": -1, "scope": -1, "term": "(true)" }, { "clause": 6, "scope": 1, "term": "(delmin (tree T6 (void) T7) T2 T3)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": [], "exprvars": [] } }, "290": { "goal": [{ "clause": 6, "scope": 2, "term": "(delmin (void) T18 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "type": "Nodes", "282": { "goal": [ { "clause": 5, "scope": 2, "term": "(delmin (void) T18 T19)" }, { "clause": 6, "scope": 2, "term": "(delmin (void) T18 T19)" } ], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "263": { "goal": [{ "clause": -1, "scope": -1, "term": "(delmin (void) T18 T19)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "275": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "320": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "310": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "311": { "goal": [{ "clause": -1, "scope": -1, "term": "(delmin T27 T32 T33)" }], "kb": { "nonunifying": [[ "(delmin (tree T26 T27 T28) T2 T3)", "(delmin (tree X6 (void) X7) X6 X7)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T26", "T27", "T28" ], "free": [ "X6", "X7" ], "exprvars": [] } }, "202": { "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": ["T1"], "free": [ "X6", "X7" ], "exprvars": [] } }, "312": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "313": { "goal": [ { "clause": 5, "scope": 3, "term": "(delmin T27 T32 T33)" }, { "clause": 6, "scope": 3, "term": "(delmin T27 T32 T33)" } ], "kb": { "nonunifying": [[ "(delmin (tree T26 T27 T28) T2 T3)", "(delmin (tree X6 (void) X7) X6 X7)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T26", "T27", "T28" ], "free": [ "X6", "X7" ], "exprvars": [] } }, "314": { "goal": [{ "clause": 5, "scope": 3, "term": "(delmin T27 T32 T33)" }], "kb": { "nonunifying": [[ "(delmin (tree T26 T27 T28) T2 T3)", "(delmin (tree X6 (void) X7) X6 X7)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T26", "T27", "T28" ], "free": [ "X6", "X7" ], "exprvars": [] } }, "315": { "goal": [{ "clause": 6, "scope": 3, "term": "(delmin T27 T32 T33)" }], "kb": { "nonunifying": [[ "(delmin (tree T26 T27 T28) T2 T3)", "(delmin (tree X6 (void) X7) X6 X7)" ]], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T26", "T27", "T28" ], "free": [ "X6", "X7" ], "exprvars": [] } }, "206": { "goal": [{ "clause": 6, "scope": 1, "term": "(delmin (tree T6 (void) T7) T2 T3)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [ "T6", "T7" ], "free": [], "exprvars": [] } }, "316": { "goal": [{ "clause": -1, "scope": -1, "term": "(true)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "317": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "318": { "goal": [], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": [], "free": [], "exprvars": [] } }, "319": { "goal": [{ "clause": -1, "scope": -1, "term": "(delmin T57 T62 T63)" }], "kb": { "nonunifying": [], "intvars": {}, "arithmetic": { "type": "PlainIntegerRelationState", "relations": [] }, "ground": ["T57"], "free": [], "exprvars": [] } }, "40": { "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": ["T1"], "free": [], "exprvars": [] } } }, "edges": [ { "from": 39, "to": 40, "label": "CASE" }, { "from": 40, "to": 191, "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": 40, "to": 202, "label": "EVAL-BACKTRACK" }, { "from": 191, "to": 206, "label": "SUCCESS" }, { "from": 202, "to": 311, "label": "EVAL with clause\ndelmin(tree(X34, X35, X36), X37, tree(X34, X38, X39)) :- delmin(X35, X37, X38).\nand substitutionX34 -> T26,\nX35 -> T27,\nX36 -> T28,\nT1 -> tree(T26, T27, T28),\nT2 -> T32,\nX37 -> T32,\nX38 -> T33,\nX39 -> T31,\nT3 -> tree(T26, T33, T31),\nT29 -> T32,\nT30 -> T33" }, { "from": 202, "to": 312, "label": "EVAL-BACKTRACK" }, { "from": 206, "to": 263, "label": "EVAL with clause\ndelmin(tree(X14, X15, X16), X17, tree(X14, X18, X19)) :- delmin(X15, X17, X18).\nand substitutionT6 -> T13,\nX14 -> T13,\nX15 -> void,\nT7 -> T14,\nX16 -> T14,\nT2 -> T18,\nX17 -> T18,\nX18 -> T19,\nX19 -> T17,\nT3 -> tree(T13, T19, T17),\nT15 -> T18,\nT16 -> T19" }, { "from": 206, "to": 275, "label": "EVAL-BACKTRACK" }, { "from": 263, "to": 282, "label": "CASE" }, { "from": 282, "to": 290, "label": "BACKTRACK\nfor clause: delmin(tree(Y, void, Right), Y, Right)because of non-unification" }, { "from": 290, "to": 310, "label": "BACKTRACK\nfor clause: delmin(tree(X, Left, X1), Y, tree(X, Left1, X2)) :- delmin(Left, Y, Left1)because of non-unification" }, { "from": 311, "to": 313, "label": "CASE" }, { "from": 313, "to": 314, "label": "PARALLEL" }, { "from": 313, "to": 315, "label": "PARALLEL" }, { "from": 314, "to": 316, "label": "EVAL with clause\ndelmin(tree(X48, void, X49), X48, X49).\nand substitutionX48 -> T42,\nX49 -> T43,\nT27 -> tree(T42, void, T43),\nT32 -> T42,\nT33 -> T43" }, { "from": 314, "to": 317, "label": "EVAL-BACKTRACK" }, { "from": 315, "to": 319, "label": "EVAL with clause\ndelmin(tree(X62, X63, X64), X65, tree(X62, X66, X67)) :- delmin(X63, X65, X66).\nand substitutionX62 -> T56,\nX63 -> T57,\nX64 -> T58,\nT27 -> tree(T56, T57, T58),\nT32 -> T62,\nX65 -> T62,\nX66 -> T63,\nX67 -> T61,\nT33 -> tree(T56, T63, T61),\nT59 -> T62,\nT60 -> T63" }, { "from": 315, "to": 320, "label": "EVAL-BACKTRACK" }, { "from": 316, "to": 318, "label": "SUCCESS" }, { "from": 319, "to": 39, "label": "INSTANCE with matching:\nT1 -> T57\nT2 -> T62\nT3 -> T63" } ], "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). 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). Afs: delminA(x1, x2, x3) = delminA(x1) ---------------------------------------- (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: (b,f,f) Transforming TRIPLES into the following Term Rewriting System: Pi DP problem: The TRS P consists of the following rules: DELMINA_IN_GAA(tree(X1, tree(X2, X3, X4), X5), X6, tree(X1, tree(X2, X7, X8), X9)) -> U1_GAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, delminA_in_gaa(X3, X6, X7)) DELMINA_IN_GAA(tree(X1, tree(X2, X3, X4), X5), X6, tree(X1, tree(X2, X7, X8), X9)) -> DELMINA_IN_GAA(X3, X6, X7) R is empty. The argument filtering Pi contains the following mapping: delminA_in_gaa(x1, x2, x3) = delminA_in_gaa(x1) tree(x1, x2, x3) = tree(x1, x2, x3) DELMINA_IN_GAA(x1, x2, x3) = DELMINA_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = U1_GAA(x1, x2, x3, x4, x5, 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_GAA(tree(X1, tree(X2, X3, X4), X5), X6, tree(X1, tree(X2, X7, X8), X9)) -> U1_GAA(X1, X2, X3, X4, X5, X6, X7, X8, X9, delminA_in_gaa(X3, X6, X7)) DELMINA_IN_GAA(tree(X1, tree(X2, X3, X4), X5), X6, tree(X1, tree(X2, X7, X8), X9)) -> DELMINA_IN_GAA(X3, X6, X7) R is empty. The argument filtering Pi contains the following mapping: delminA_in_gaa(x1, x2, x3) = delminA_in_gaa(x1) tree(x1, x2, x3) = tree(x1, x2, x3) DELMINA_IN_GAA(x1, x2, x3) = DELMINA_IN_GAA(x1) U1_GAA(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) = U1_GAA(x1, x2, x3, x4, x5, 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_GAA(tree(X1, tree(X2, X3, X4), X5), X6, tree(X1, tree(X2, X7, X8), X9)) -> DELMINA_IN_GAA(X3, X6, X7) R is empty. The argument filtering Pi contains the following mapping: tree(x1, x2, x3) = tree(x1, x2, x3) DELMINA_IN_GAA(x1, x2, x3) = DELMINA_IN_GAA(x1) 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_GAA(tree(X1, tree(X2, X3, X4), X5)) -> DELMINA_IN_GAA(X3) 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_GAA(tree(X1, tree(X2, X3, X4), X5)) -> DELMINA_IN_GAA(X3) The graph contains the following edges 1 > 1 ---------------------------------------- (10) YES